トップページに戻る    次の競技プログラミングの問題へ    前の競技プログラミングの問題へ

ARC-024-A くつがくっつく

■■■問題■■■

ARCマートは土曜日だけに営業する靴屋さんです。
扱う靴は1種類だけで、サイズ以外の見分けはつきません。
残念なことに、1週間ぶりに店を開けると空き巣に入られてしまったらしく、
靴がめちゃくちゃに散乱していました。

残っている靴を全部かき集めると、左足の靴がL足、右足の靴がR足みつかりました。
ただ、靴を売るには同じサイズを両足分そろえてペアにしなければなりません。
靴の種類はすべて同じなので、ペアを作るときはサイズだけを気にすれば良さそうです。

もう開店まで時間がないので、
店長のために、最大で何組のペアを作ることができるか求めてください。

■■■入力■■■

L R
l1 l2 ・・・ lL
r1 r2 ・・・ rR

●1行目にみつかった左足の靴の数 L(1 <= L <= 100)、右足の靴の数 R(1 <= R <= 100)が
  空白区切りで与えられる。
●2行目にはL個の整数が空白区切りで与えられる。
  i番目にはi番目の左足の靴のサイズ li(10 <= li <= 40) が与えられる。
●3行目にはR個の整数が空白区切りで与えられる。
  i番目にはi番目の右足の靴のサイズ ri(10 <= ri <= 40) が与えられる。

■■■出力■■■

作成可能な靴のペア数の最大値を1行で出力せよ。


C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3 3");
            WillReturn.Add("20 21 22");
            WillReturn.Add("30 22 15");
            //1
            //サイズ22のペアが1つだけ作れます
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 4");
            WillReturn.Add("10 11 10");
            WillReturn.Add("12 10 11 25");
            //2
            //サイズ10、サイズ11のペアがそれぞれ1つずつ作れます
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("5 5");
            WillReturn.Add("10 10 10 10 10");
            WillReturn.Add("10 10 10 10 10");
            //5
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("5 5");
            WillReturn.Add("10 11 12 13 14");
            WillReturn.Add("30 31 32 33 34");
            //0
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] LArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray();
        int[] RArr = InputList[2].Split(' ').Select(X => int.Parse(X)).ToArray();

        int UB_L = LArr.GetUpperBound(0);
        int UB_R = RArr.GetUpperBound(0);

        Array.Sort(LArr); Array.Sort(RArr);

        int LInd = 0, RInd = 0;
        int Answer = 0;
        while (LInd <= UB_L && RInd <= UB_R) {
            if (LArr[LInd] == RArr[RInd]) {
                Answer++;
                LInd++; RInd++;
            }
            else if (LArr[LInd] < RArr[RInd]) {
                LInd++;
            }
            else if (LArr[LInd] > RArr[RInd]) {
                RInd++;
            }
        }
        Console.WriteLine(Answer);
    }
}


解説

マージソートの要領で解いてます。