🎃

AtCoderの過去問精選 10 問をElmで解いてみる

21 min read

AtCoder に登録したら次にやること ~ これだけ解けば十分闘える!過去問精選 10 問 ~の10問をElmで解いてみました。元の手続き型の解き方と比べてみたり、写経したりしてみると面白いかもしれません。

今回のAtCoderの提出環境は以下の記事で紹介しているものを使っています。

Elmで競技プログラミング(AtCoder)を解いてみよう!(簡単に始められる環境アリ!)

テストケース付き回答リポジトリもここに載せておきます。

解いてみた感想

私自身は普段、競技プログラミングを嗜まない人間ですが、ABCぐらいの問題であれば、Elmで十分解くことが可能であることが今回わかりました(D問題は解いていませんが)。それ以上の問題は解いていませが、お世辞にも競技プログラミング向きの言語ではないと思います。シビアに計算量が求められるような問題は、かなり力技のコードが必要になると思います。しかし、今回それ以上にElm(純粋関数型プログラミング言語)の基礎力を付けるにはABCの問題はとても良い練習になると思いました。今回の記事のコードがElmで競技プログラミング問題を解くための参考になったり、より良いコードに昇華するためのきっかけになれば幸いです。

それでは、10問のコードをご覧ください。

第 1 問: ABC 086 A - Product (100 点)

このようにロジックが簡単な問題で入力取り方を学んでいくと良いと思います。

solveA : List String -> String
solveA inputs =
    case Maybe.map (List.filterMap String.toInt << String.split " ") <| List.head <| inputs of
        Just (a :: b :: []) ->
            if modBy 2 (a * b) == 0 then
                "Even"

            else
                "Odd"

        _ ->
            "fail"

1行に空白区切りの2つの数値が入力として与えられます。これを整数に変換し、a, bと取り出せれば後は解くのは簡単です。

List.headで先頭を取得します。空の場合も考慮して、Maybe型となります。中の値を加工するには、Maybe.mapを使います。String.splitで空白区切りにし、List.filterMapString.toIntすることで整数に変換できたもののみが残ります。後はパターンマッチをして先頭の2つの整数をa, bとして取り出せば成功です。

入力値を加工しながら取り出すのは慣れるまで難しいですが、コンパイルエラーが取り出したい型になるまで叱ってくれるので、叱られながら頑張りましょう。テストコードを書きながらやるとトライアンドエラーが素早くできて楽です。(テストであれば、Debugモジュールの関数を使いながら確認できます)

 describe "solveA"
            [ test "case1" <|
                \_ ->
                    [ "3 4" ]
                        |> solveA
                        |> Expect.equal "Even"
            , test "case2" <|
                \_ ->
                    [ "1 21" ]
                        |> solveA
                        |> Expect.equal "Odd"
            ]

第 2 問: ABC 081 A - Placing Marbles (100 点)

1問目に続き、入力から欲しい値に加工していくことに慣れていきましょう。

solveB : List String -> String
solveB inputs =
    String.fromInt <|
        Maybe.withDefault 0 <|
            Maybe.map (String.length << String.filter ((==) '1')) <|
                List.head <|
                    inputs

下から読んでいきます。1問目と同じで先頭の要素を取ってMaybe.mapで加工していきます。1の文字がいくつあるか数えたいので、filterして、lengthを取ります。入力値がないことはないので、Maybe.withDefaultにテキトーなデフォルトの値として0を渡して、String.fromIntで解答用に文字列型に変換して終わりです。

describe "solveB"
            [ test "case1" <|
                \_ ->
                    [ "101" ]
                        |> solveB
                        |> Expect.equal "2"
            , test "case2" <|
                \_ ->
                    [ "000" ]
                        |> solveB
                        |> Expect.equal "0"
            ]

第 3 問: ABC 081 B - Shift Only (200 点)

入力に慣れてきたところで、少しだけロジックの難易度が上がります。再帰がキーワードです。

solveC : List String -> String
solveC inputs =
    let
        loop : List Int -> Int -> Int
        loop nums c =
            let
                isEven num =
                    modBy 2 num == 0

                divide2 =
                    List.map (\x -> x // 2)
            in
            if List.all isEven nums then
                loop (divide2 nums) c + 1

            else
                c
    in
    case inputs of
        _ :: numStrs :: [] ->
            let
                nums =
                    List.filterMap String.toInt <| String.split " " numStrs
            in
            String.fromInt <| loop nums 0

        _ ->
            "fail"

1行目の文字列は数列の長さなので、無視して2行目だけをnumStrsとして取り出します。後は、いつも通り加工してnumsとして扱います。数列を取り出せたら、loop関数で再帰処理をします。初期値は0として、何回2で割ることができるか、つまり全ての数字が偶数かどうかを判断します。この手の便利関数はElmに用意されています。List.allisEvenかどうかを確かめて、割れそうならカウントを1増やし全て2で割った数列を再びloopに渡します。もう割れないなら、カウントを返します。

describe "solveC"
            [ test "case1" <|
                \_ ->
                    [ "3", "8 12 40" ]
                        |> solveC
                        |> Expect.equal "2"
            , test "case2" <|
                \_ ->
                    [ "4", "5 6 8 10" ]
                        |> solveC
                        |> Expect.equal "0"
            , test "case3" <|
                \_ ->
                    [ "6", "382253568 723152896 37802240 379425024 404894720 471526144" ]
                        |> solveC
                        |> Expect.equal "8"
            ]

第 4 問: ABC 087 B - Coins (200 点)

組み合わせの数を手続き型なら3重ループで記述します。今回は、ライブラリを使って3つのリストの組み合わせの数を求めて問題を解きます。

solveD : List String -> String
solveD inputs =
    case List.filterMap String.toInt <| inputs of
        a :: b :: c :: x :: [] ->
            String.fromInt <|
                List.length <|
                    List.filter ((==) x) <|
                        List.lift3
                            (\aa bb cc -> aa * 500 + bb * 100 + cc * 50)
                            (List.range 0 a)
                            (List.range 0 b)
                            (List.range 0 c)

        _ ->
            "fail"

入力を加工して、4つの数値を取り出します。List.lift3で3つのリストの組み合わせの数を作ります。List.rangeを使えば、任意の範囲の数列を用意できます。最後は、filterして長さを出すだけですね。

describe "solveD"
            [ test "case1" <|
                \_ ->
                    [ "2", "2", "2", "100" ]
                        |> solveD
                        |> Expect.equal "2"
            , test "case2" <|
                \_ ->
                    [ "5", "1", "0", "150" ]
                        |> solveD
                        |> Expect.equal "0"
            , test "case3" <|
                \_ ->
                    [ "30", "40", "50", "6000" ]
                        |> solveD
                        |> Expect.equal "213"
            ]

第 5 問: ABC 083 B - Some Sums (200 点)

難しい処理は関数として切り出しておくと解きやすいです。

solveE : List String -> String
solveE inputs =
    let
        sumDigit : Int -> Int
        sumDigit n =
            String.fromInt n
                |> String.toList
                |> List.map String.fromChar
                |> List.filterMap String.toInt
                |> List.sum
    in
    case Maybe.map (String.split " " >> List.filterMap String.toInt) <| List.head inputs of
        Just (n :: a :: b :: []) ->
            String.fromInt <|
                (List.range 1 n
                    |> List.filterMap
                        (\x ->
                            let
                                sum =
                                    sumDigit x
                            in
                            if a <= sum && sum <= b then
                                Just x

                            else
                                Nothing
                        )
                    |> List.sum
                )

        _ ->
            "fail"

1からnまで条件に合う桁の合計値を足し合わせていきます。桁の合計を計算するのがsumDigit関数です。数字を文字列に変換して、文字列を文字のリストに変換して、全てを文字を整数に変換して、その合計を求めます。説明通りの加工をパイプで繋ぎ合わせれば完成です。

describe "solveE"
            [ test "case1" <|
                \_ ->
                    [ "20 2 5" ]
                        |> solveE
                        |> Expect.equal "84"
            , test "case2" <|
                \_ ->
                    [ "10 1 2" ]
                        |> solveE
                        |> Expect.equal "13"
            , test "case3" <|
                \_ ->
                    [ "100 4 16" ]
                        |> solveE
                        |> Expect.equal "4554"
            ]

第 6 問: ABC 088 B - Card Game for Two (200 点)

添字が重要になる問題も競技プログラミングには多いです。関数型ではどのように解くでしょうか?

solveF : List String -> String
solveF inputs =
    case inputs of
        _ :: aStrs :: [] ->
            let
                isEven num =
                    modBy 2 num == 0

                isOdd =
                    not << isEven

                cards =
                    (String.split " " >> List.filterMap String.toInt >> List.sort >> List.reverse >> List.indexedMap Tuple.pair) aStrs

                aliceCard =
                    cards
                        |> List.filterMap
                            (\( index, x ) ->
                                if isEven index then
                                    Just x

                                else
                                    Nothing
                            )

                bobCard =
                    cards
                        |> List.filterMap
                            (\( index, x ) ->
                                if isOdd index then
                                    Just x

                                else
                                    Nothing
                            )
            in
            String.fromInt <| List.sum aliceCard - List.sum bobCard

        _ ->
            "fail"

今回で重要な箇所は以下の部分です。いつも通りの加工までは大丈夫だと思われます。その後、sortしreverse(つまり降順に並び替えています) List.indexedMapをすることで、添字(index)を扱うことができます。

cards = (String.split " " >> List.filterMap String.toInt >> List.sort >> List.reverse >> List.indexedMap Tuple.pair) aStrs

後は、Aliceなら偶数番目のカード、Bobなら奇数番目のカードを配ることで、各々の最善手が完成するので合計を求めて差分を取れば答えになります。

describe "solveF"
            [ test "case1" <|
                \_ ->
                    [ "2", "3 1" ]
                        |> solveF
                        |> Expect.equal "2"
            , test "case2" <|
                \_ ->
                    [ "3", "2 7 4" ]
                        |> solveF
                        |> Expect.equal "5"
            , test "case3" <|
                \_ ->
                    [ "4", "20 18 2 18" ]
                        |> solveF
                        |> Expect.equal "18"
            ]

第 7 問: ABC 085 B - Kagami Mochi (200 点)

重複を取り除くには何を使えば良いでしょうか?

solveG : List String -> String
solveG inputs =
    case inputs of
        _ :: numStrs ->
            let
                nums =
                    numStrs |> List.filterMap String.toInt
            in
            String.fromInt <| Set.size <| Set.fromList nums

        _ ->
            "fail"

Set(集合)に変換し、そのサイズが答えになります。シンプルな問題でした。

describe "solveG"
            [ test "case1" <|
                \_ ->
                    [ "4", "10", "8", "8", "6" ]
                        |> solveG
                        |> Expect.equal "3"
            , test "case2" <|
                \_ ->
                    [ "3", "15", "15", "15" ]
                        |> solveG
                        |> Expect.equal "1"
            , test "case3" <|
                \_ ->
                    [ "7"
                    , "50"
                    , "30"
                    , "50"
                    , "100"
                    , "50"
                    , "80"
                    , "30"
                    ]
                        |> solveG
                        |> Expect.equal "4"
            ]

第 8 問: ABC 085 C - Otoshidama (300 点)

ネストが深いですが、さほど難しくはありません。

solveH : List String -> String
solveH inputs =
    case Maybe.map (String.split " " >> List.filterMap String.toInt) <| List.head inputs of
        Just (n :: y :: []) ->
            let
                candidateAnswer =
                    List.head <|
                        (List.range 0 n
                            |> List.concatMap
                                (\manN ->
                                    List.range 0 (n - manN)
                                        |> List.filterMap
                                            (\gosenN ->
                                                if y == manN * 10000 + gosenN * 5000 + (n - manN - gosenN) * 1000 then
                                                    Just <|
                                                        String.fromInt manN
                                                            ++ " "
                                                            ++ String.fromInt gosenN
                                                            ++ " "
                                                            ++ String.fromInt (n - manN - gosenN)

                                                else
                                                    Nothing
                                            )
                                )
                        )
            in
            Maybe.withDefault "-1 -1 -1" candidateAnswer

        _ ->
            "fail"

List.range 0 nで1万円の枚数の候補、1万円の枚数からnを引いて5千円の枚数の候補、残りが1000円の枚数の候補として、計算式に当てはめて、成功した組み合わせだけを取ります。後は先頭の組み合わせを出力しておしまいです。

describe "solveH"
            [ test "case1" <|
                \_ ->
                    [ "9 45000" ]
                        |> solveH
                        |> Expect.equal "0 9 0"
            , test "case2" <|
                \_ ->
                    [ "20 196000" ]
                        |> solveH
                        |> Expect.equal "-1 -1 -1"
            ]

第 9 問: ABC 049 C - Daydream (300 点)

元の記事と同じ解き方です。後ろから候補を絞って、消費して無くなるまで再帰でやっていきます。

solveI : List String -> String
solveI inputs =
    let
        divide =
            [ "dream", "dreamer", "erase", "eraser" ] |> List.map String.reverse

        loop : String -> Bool
        loop str =
            let
                dd =
                    divide
                        |> List.filterMap
                            (\d ->
                                let
                                    subStr =
                                        String.slice 0 (String.length d) str
                                in
                                if subStr == d then
                                    Just d

                                else
                                    Nothing
                            )
            in
            case dd of
                d :: [] ->
                    let
                        rest =
                            (String.slice (String.length d) <| String.length str) str
                    in
                    if String.length rest == 0 then
                        True

                    else
                        loop rest

                _ ->
                    False
    in
    case List.head inputs of
        Just s ->
            if loop <| String.reverse s then
                "YES"

            else
                "NO"

        Nothing ->
            "fail"

比較対象のsを反転させて、再帰関数loopに渡します。あらかじめ、付け足していく候補の文字列も反転させて、divideと言う名前にしておきます。後は、一致したら残りを再帰して、残りが空文字になったらTrue、失敗したらFalseです。

describe "solveI"
            [ test "case1" <|
                \_ ->
                    [ "erasedream" ]
                        |> solveI
                        |> Expect.equal "YES"
            , test "case2" <|
                \_ ->
                    [ "dreameraser" ]
                        |> solveI
                        |> Expect.equal "YES"
            , test "case3" <|
                \_ ->
                    [ "dreamerer" ]
                        |> solveI
                        |> Expect.equal "NO"
            ]

第 10 問: ABC 086 C - Traveling (300 点)

いつも通り入力を扱っていきますが、現在と次を見る、添字アクセスではなくリストのパターンマッチで見ていくのが工夫のポイントです。

solveJ : List String -> String
solveJ inputs =
    case inputs of
        _ :: rest ->
            let
                txys =
                    rest |> List.map (String.split " " >> List.filterMap String.toInt)

                loop : List (List Int) -> Bool
                loop txyss =
                    case txyss of
                        crnt :: next :: txyRest ->
                            case ( crnt, next ) of
                                ( crntT :: crntX :: crntY :: [], nextT :: nextX :: nextY :: [] ) ->
                                    let
                                        dt =
                                            nextT - crntT

                                        dist =
                                            abs (nextX - crntX) + abs (nextY - crntY)
                                    in
                                    if dt >= dist && (modBy 2 dist == modBy 2 dt) then
                                        if List.isEmpty txyRest then
                                            True

                                        else
                                            loop (next :: txyRest)

                                    else
                                        False

                                _ ->
                                    False

                        _ ->
                            False
            in
            if loop ([ 0, 0, 0 ] :: txys) then
                "Yes"

            else
                "No"

        _ ->
            "fail"

また再帰問題です。意外と忘れがちなのが初期値の[0, 0, 0] これを頭にくっつけてから再帰関数に渡してあげましょう、loop ([ 0, 0, 0 ] :: txys) 。個人的に面白いポイントが、パターンマッチで、現在・次(比較対象)・残りで取り出してあげましょう。

case txyss of
	crnt :: next :: txyRest ->

これは正直面倒!って思ってしまいましたが、現在のt, x, y、次の t, x, yをこんな感じで取り出してあげます。あとの解き方は、元記事通り。

case ( crnt, next ) of
   ( crntT :: crntX :: crntY :: [], nextT :: nextX :: nextY :: [] ) ->

再帰関数がまだ終わらない場合には、nextも忘れずに渡してあげましょうloop (next :: txyRest)

describe "solveJ"
            [ test "case1" <|
                \_ ->
                    [ "2", "3 1 2", "6 1 1" ]
                        |> solveJ
                        |> Expect.equal "Yes"
            , test "case2" <|
                \_ ->
                    [ "1", "2 100 100" ]
                        |> solveJ
                        |> Expect.equal "No"
            , test "case3" <|
                \_ ->
                    [ "2", "5 1 1", "100 1 1" ]
                        |> solveJ
                        |> Expect.equal "No"
            ]

10問終わりです!ちょっと時間掛かりましたが、とても楽しかったです。もしここまで見てくれたり、写経してくださった方がいればありがとうございました。リファクタリング報告お待ちしております。

Discussion

ログインするとコメントできます