AtCoderの過去問精選 10 問をElmで解いてみる
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.filterMapでString.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.allでisEvenかどうかを確かめて、割れそうならカウントを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