ABC-030-C 飛行機乗り

■■■問題■■■

ウナギの高橋くんは飛行機に乗ることが趣味です。
今回は空港Aと空港Bを往復することにしました。

空港Aから空港Bの飛行機にはX時間かかり、
空港Bから空港Aへの飛行機にはY時間かかります。
空港Aから空港Bへの飛行機はN本あり、i番目の便はai時に出発します。
空港Bから空港Aへの飛行機はM本あり、j番目の便はbj時に出発します。

ある飛行機には、出発する空港に出発する時刻以前にいれば乗ることができます。
出発する時刻ちょうどに到着した場合も、すぐに飛行機に乗って出発できます。
高橋くんははじめ空港Aに0時にいます。
空港Aと空港Bの間を最大何往復できるか調べてください。

■■■入力■■■

N M
X Y
a1 a2 ・・・ aN
b1 b2 ・・・ bM

●1行目には、空港Aから空港Bへの本数 N(1 <= N <= 10万)、
             空港Bから空港Aへの本数 M(1 <= M <= 10万) が空白区切りで与えられる。
●2行目には、空港Aから空港Bへの飛行機にかかる時間 X(1 <= X <= 10億)、
             空港Bから空港Aへの飛行機にかかる時間 Y(1 <= Y <= 10億) が空白区切りで与えられる。
●3行目には、N個の空港Aから飛行機が出発する時刻を表す整数aiが空白を区切りとして与えられる。
●4行目には、M個の空港Bから飛行機が出発する時刻を表す整数bjが空白を区切りとして与えられる。
●1 <= ai <= 10億(1 <= i <= N) であることが保証される。
●1 <= bj <= 10億(1 <= j <= M) であることが保証される。
●ai<ai+1(1 <= i <= N-1) であることが保証される。
●bi<bj+1(1 <= j <= M-1) であることが保証される。

■■■出力■■■

高橋くんが空港Aと空港Bの間を最大何往復できるかを1行に出力せよ。
末尾の改行を忘れないこと。

C#のソース

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

class Program
{
    static string InputPattern = "Input1";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("3 4");
            WillReturn.Add("2 3");
            WillReturn.Add("1 5 7");
            WillReturn.Add("3 8 12 13");
            //2
            //1時の空港Aを出発する飛行機に乗り、3時に到着しますが、
            //すぐに3時の空港Bを出発する飛行機に乗り、6時に空港Aに到着します。
            //次に、7時の空港Aを出発する飛行機に乗り、9時に到着、
            //12時の空港Bを出発する飛行機に乗ると、合計2往復できます。3往復する手段はありません。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1 1");
            WillReturn.Add("1 1");
            WillReturn.Add("1");
            WillReturn.Add("1");
            //0
            //空港Bに行くと空港Aに帰れないので、1度も往復できません
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("6 7");
            WillReturn.Add("5 3");
            WillReturn.Add("1 7 12 19 20 26");
            WillReturn.Add("4 9 15 23 24 31 33");
            //3
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] wkArr = InputList[1].Split(' ').Select(A => int.Parse(A)).ToArray();
        int X = wkArr[0];
        int Y = wkArr[1];

        int[] AArr = InputList[2].Split(' ').Select(A => int.Parse(A)).ToArray();
        int[] BArr = InputList[3].Split(' ').Select(A => int.Parse(A)).ToArray();
        int AMax = AArr[AArr.Length - 1];
        int BMax = BArr[BArr.Length - 1];

        int CurrT = 1;
        int MoveCnt = 0;

        while (true) {
            //空港Aから空港Bに移動
            if (AMax < CurrT) break;
            int wkInd1 = Array.BinarySearch(AArr, CurrT);
            if (wkInd1 < 0) wkInd1 = ~wkInd1;
            CurrT = AArr[wkInd1] + X;

            //空港Bから空港Aに移動
            if (BMax < CurrT) break;
            int wkInd2 = Array.BinarySearch(BArr, CurrT);
            if (wkInd2 < 0) wkInd2 = ~wkInd2;
            CurrT = BArr[wkInd2] + Y;

            MoveCnt++;
        }
        Console.WriteLine(MoveCnt);
    }
}

解説

貪欲法を使って、シミュレーションしてます。