AtCoder に登録したら解くべき精選過去問 10 問を Erlang で解いてみた #競技プログラミング

始めに

AtCoder に登録したら解くべき精選 10 問を、Erlang で解きました。¹

対象

Erlang と競プロをどちらも知っていて、競プロを通じて Erlang のスキルを高めたい方。

テンプレート

-module('Main').
-export([main/1]).

solve() ->
    ok.

main(_) ->
    solve(),
    halt().

input(Pat) ->
    {ok, L} = io:fread("", Pat),
    L.

基本的に solve/0 の中に実装を書けば良いです。以降 module, export, main/1, input/1 は省略します。

入出力

io:fread を使うことで、 C の scanf と似た形式 (単語ごとに読む) で入力を取ることができます。
例えば、整数 N とその後に続く N 個の整数を読みたい場合は以下のようにします。

solve() ->
    [N] = input("~d"),
    % 遅い
    A = [input("~d") || _ <- lists:seq(1, N)],
    % 速い
    Pat = lists:flatten(lists:duplicate(N, "~d")),
    A = input(Pat),

    ok.

基本的に io:fread を何回も呼ぶと遅いので、パターン文字列を連結して1回の呼び出しで済ませた方が速いです。なにこれ

出力は io:format(Pattern, [Args...]) という関数呼び出しで行うことができます。例えば整数 A を出力したい場合は以下のようにすれば良いです:

solve() ->
    A = 42,
    io:format("~B~n", [A]),
    ok.

型	フォーマット文字列
整数	`~B` (`~p` も可)
文字列	`~s`
Erlang 式表記 (型は何でもよい)	`~p`

実行方法

escript ファイル名.erl

問題と解法の詳細について

解法の詳細については、この記事では一切書きません。そもそもこれは入門用の記事ではありません。

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

A, B を受け取り、AB が偶数ならば "Even" を、奇数ならば "Odd" を出力せよ。

提出

solve() ->
    [A, B] = input("~d~d"),
    io:format("~s~n", [case A * B rem 2 of
        0 -> "Even"; 1 -> "Odd" end]),
    ok.

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

3 文字の文字列が与えられる。その中に含まれる '1' の個数は?

提出

solve() ->
    [S] = input("~s"),
    Len = length(lists:filter(fun (Elem) -> Elem =:= $1 end, S)),
    io:format("~B~n", [Len]),
    ok.

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

数列 A の要素が全て偶数の場合、全て 2 で割る。この操作は何回できる?

提出

rec(A, N) when A rem 2 =:= 0 -> rec(A div 2, N + 1);
rec(_, N) -> N.

solve() ->
    [N] = input("~d"),
    A = input(lists:flatten(["~d" || _ <- lists:seq(1, N)])),
    And = lists:foldl(fun (Elem, Acc) -> Elem bor Acc end, 0, A),
    io:format("~B~n", [rec(And, 0)]),
    ok.

ループが使えないので、lists:foldl などを使う必要があります。

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

提出

solve() ->
    [A, B, C, X] = input("~d~d~d~d"),
    io:format("~B~n", [length(
        [ ok || I <- lists:seq(0, A), J <- lists:seq(0, B), K <- lists:seq(0, C), 500 * I + 100 * J + 50 * K =:= X]
    )]),
    ok.

何重ループであろうとループする範囲が決まっているのであれば、リストの内包表記でサクッと書けます。

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

提出

sum(N) when N =< 0 -> 0;
sum(N) -> sum(N div 10) + N rem 10.

solve() ->
    [N, A, B] = input("~d~d~d"),
    io:format("~B~n", [lists:sum(
        [I || I <- lists:seq(1, N), A =< sum(I), sum(I) =< B]
    )]),
    ok.

桁和みたいなのは再帰関数でサクッと書けます。

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

提出

rec([]) -> 0;
rec([A | Rest]) -> A - rec(Rest).

solve() ->
    [N] = input("~d"),
    A = input(lists:flatten(["~d" || _ <- lists:seq(1, N)])),
    ASorted = lists:reverse(lists:sort(A)), % 逆順ソート
    io:format("~B~n", [rec(ASorted)]),
    ok.

普通の配列のソートが $O(N \log N)$ 時間でできるのは有名ですが、連結リストでも (マージソートで) $O(N \log N)$ 時間が達成できるのは面白いですね。

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

提出

solve() ->
    [N] = input("~d"),
    A = input(lists:flatten(["~d" || _ <- lists:seq(1, N)])),
    io:format("~B~n", [length(lists:usort(A))]),
    ok.

lists:usort で重複除去 + ソートができます。なんで (いろいろな関数が足りていないのに) こんなピンポイントな関数だけ用意してあるんだ…?

以下から計算量の意識が必要な C 問題になるので、難易度が跳ね上がります。

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

提出

check(A, B, C, N) ->
    case 10000 * A + 5000 * B + 1000 * C =:= N of
        true -> throw({A, B, C});
        false -> ok
    end.

solve() ->
    [N, Y] = input("~d~d"),
    {A, B, C} = try
        lists:foreach(fun (I) ->
            lists:foreach(fun (J) -> check(I, J, N - I - J, Y) end, lists:seq(0, N - I)) end,
            lists:seq(0, N)),
        {-1, -1, -1}
    catch
        throw:E -> E
    end,
    io:format("~B ~B ~B~n", [A, B, C]),

escript c.erl で実行したら 40 秒近くかかりましたが、AtCoder のコードテストで実行したら 300ms 以内に終わりました。

第 9 問: ABC 049 C - 白昼夢 / Daydream (300 点)

提出

calc("maerd" ++ S) -> calc(S);
calc("remaerd" ++ S) -> calc(S);
calc("esare" ++ S) -> calc(S);
calc("resare" ++ S) -> calc(S);
calc([]) -> true;
calc(_) -> false.

solve() ->
    [S] = input("~s"),
    SRev = lists:reverse(S),
    io:format("~s~n", [case calc(SRev) of
        true -> "YES";
        false -> "NO"
    end]),
    ok.

リストに対する先頭のマッチングは定数時間なので、このコードは $O(|S|)$ 時間で動作します。

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

提出

calc([T1, X1, Y1 | L = [T2, X2, Y2 | _]]) ->
    T = T2 - T1,
    Dist = abs(X2 - X1) + abs(Y2 - Y1),
    case Dist =< T andalso (Dist + T) rem 2 =:= 0 of
        true -> calc(L);
        false -> false
    end;
calc(_) -> true.

solve() ->
    [N] = input("~d"),
    List = input(lists:flatten(lists:duplicate(3 * N, "~d"))),
    io:format("~s~n", [case calc([0, 0, 0 | List]) of
        true -> "Yes";
        false -> "No"
    end]),
    ok.

いわゆる $10^5$ 系問題の入力は、Erlang だと注意する必要があります。なるべく io:format を呼ぶ回数を減らすことが大切です。

こういう先頭から順に見ていくタイプの問題は、連結リストでも問題なく書けますね。

終わりに

Erlang で競プロは、しちゃダメだろ。

体裁は AtCoder に登録したら解くべき精選過去問 10 問を Rust で解いてみたを参考にさせていただきました。 ↩