プロローグ
@drken さんの記事 AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ にて紹介されている過去問精選 10 問を、論理型プログラミング言語 Prolog で解いてみました。
問題はこちらから見られます。
AtCoder Beginners Selection
さらに、AtCoder Beginners Selection、通称 ABS は有志たちによって既に 40 以上の言語で解かれており、そちらを見ても楽しめると思います。
百花繚乱！なないろ言語で競技プログラミングをする資料まとめ
注意点
2019 年 2 月現在、Prolog は AtCoder の使用可能言語に含まれていません。
ファイル一つにまとまったインタプリタも見つからなかったので、提出によるテストはしておらず、サンプルケースをこちら側で試すだけとなっています。
動作確認には Try It Online の Prolog (SWI) を使用しています。
ケース漏れについては問題ないとは思いますが、大きな入力に対して時間内に動作するか、スタックオーバーフローを起こさないかなどは確認できていません。ご了承ください。
あと自分は Prolog をちゃんと書いたことがないので作法や推奨される書き方といったものがわかっておらず、この記事は自分の勉強も兼ねています。
追記
@sym_num さんの指摘により以下を修正しました。
- 条件分岐のため
if(Test, Then, _) :- Test, !, Then. if(_ , _ , Else) :- Else.という述語を定義していたが、既にIf -> Then ; Elseという述語が用意されていたためそちらを使うように変更 - ダブルクオートは処理系やモードによって意味が変わりうるので、常に atom となるシングルクオートを使用
0. PracticeA - はじめてのあっとこーだー（Welcome to AtCoder）
他の言語版でも言われている通り、大抵はじめにつまずくのは入出力です。Prolog はクエリを投げるとそれに対して返答があるというイメージがありますが、ググったり、ドキュメントを読んだりすると、read/1 や write/1 といった標準入出力用の述語も存在することがわかります。（Prolog の述語は引数の数によって異なる実装にできるので、述語名/引数の数 という書き方をするのが良いようです。）
しかし read/1 の問題として、入力そのものも Prolog のシンタックスに従っていなければならないという点があります。つまり、数や文字列を受け取るにしても、それらは Prolog における区切り記号である . によって区切られていなければ正しく動作しないのです。
そこで入力を文字列としてそのまま受け取る read_string/5 を使用します。
get_string(String) :-
current_input(Input),
read_string(Input, ' \n', '', _, String).
get_number(Number) :-
get_string(String),
number_string(Number, String).
main :-
get_number(A),
get_number(B),
get_number(C),
get_string(S),
Sum is A + B + C,
write(Sum),
write(' '),
write(S).
:- main.
read_string/5 は read_string(ストリーム、区切り文字、トリムする文字、実際に区切られた文字、結果) という形をとり、色々な形の入力に対応できて便利です。
number_string/2 は数値と文字列を結びつける述語で、双方向の変換に使用できます。
is/2 は中置できる述語で、右側の数値を評価したものと等しくなるよう、左側を合わせます。一見似ている比較の仕方が後々色々と出てくるので、逐一解説していきます。
:- main. は実行を表しますが、これはどういうことなのでしょうか。この記事は Prolog 自体を解説するものではないので詳しい説明は省きますが、Prolog における :- の使い方として「事実 A.」「規則 A :- B.」「質問 :- B.」の３つがあり、質問の形で記述することでようやくインタプリタは論理式がどうすれば真になるかを探索できるようになります。ここで初めて入出力などの実行も行われます。理論的な説明は「ホーン節」「導出原理」といった言葉で調べてください。
1. ABC086A - Product
get_string(String) :-
current_input(Input),
read_string(Input, ' \n', '', _, String).
get_number(Number) :-
get_string(String),
number_string(Number, String).
main :-
get_number(A),
get_number(B),
A * B mod 2 =:= 0 ->
write('Even');
write('Odd').
:- main.
さて、条件 -> 成功のとき ; 失敗のとき という書き方が出てきましたが、これは何なのでしょうか。
;/2 は論理和で、どちらかが成功したときに成功する述語なのですが、さらにこれを利用した ->/2 という述語があります。定義を見てみましょう。
If -> Then; _Else :- If, !, Then.
If -> _Then; Else :- !, Else.
If -> Then :- If, !, Then.
! というものが出てきました。これはカットと呼ばれます。そもそも Prolog には、解を見つけようとして（単一化しようとして）失敗したとき、他の解を探しに行くバックトラックという動作があります。しかし実用上、そういう動作を制御したいということがあり、このカットはバックトラックを防ぐために使われます。論理学の観点からは良くないそうですが。
つまり上記の定義によれば If が成功して Then に進めば、Else は実行しないということになります。（If が失敗したら２つ目の定義に移るので Else が実行されます。）これを用いて、手続き型言語の if 文のような動作を書くことができます。（ちょっとインデントに迷いますね。）
=:=/2 というのも出てきました。これは、左側と右側の評価結果が等しいと成功になります。is/2 との違いは、is/2 は左側にこれから決めたい変項を持ってきて、=:=/2 は既に決まっている式を持ってくるというところにあります。
2. ABC081A - Placing Marbles
main :-
get_char(S1),
get_char(S2),
get_char(S3),
findall(_, (
member(S, [S1, S2, S3]),
S == '1'
), Found),
length(Found, Count),
write(Count).
:- main.
get_char/1 によって入力を１文字受け取ります。（AtCoder の問題の入出力は基本的に ASCII コードに収まるので、１文字が何を指すのかは気にしなくて良いと思います。）
findall/3 という述語が出てきて、これが重要です。findall(ほしい形, 満たすべき条件, 結果のリスト) とすると、条件を満たすすべての組み合わせをリストで得ることができます。今回は数だけ知りたいので１つ目は省略し、２つ目に、「S1, S2, S3 のどれかに含まれる」かつ「'1' に等しい」という条件を与えています。Prolog に量化などはないので、この条件の中に、探したい範疇も指定してやります。
==/2 は左辺と右辺が値として等しいと成功になります。さきほど出てきた =:=/2 は両辺が数式である必要があるという点で異なります。
3. ABC081B - Shift only
get_string(String) :-
current_input(Input),
read_string(Input, ' \n', '', _, String).
get_number(Number) :-
get_string(String),
number_string(Number, String).
get_numbers(0, []).
get_numbers(N, [X|Xs]) :-
get_number(X),
N1 is N - 1,
get_numbers(N1, Xs).
solve([], inf).
solve([X|Xs], Ans) :-
Lsb1 is lsb(X),
solve(Xs, Lsb2),
Ans is min(Lsb1, Lsb2).
main :-
get_number(N),
get_numbers(N, A),
solve(A, Ans),
write(Ans).
:- main.
さて、入力の長さが可変になりました。N 個の数の入力をリストにする、get_numbers/2 という述語を作ってみましょう。
Prolog でリストを扱うには、再帰的定義が基本です。ということで、N = 0 なら空リストを返し、そうでなければ数を一つ読み込み、N - 1 について同じことを繰り返して結果を合わせる、という方法をとっています。Prolog ではリストを [Head|Tail] のように分割し、単一化することができます。
問題を解く述語 solve/2 も考え方は同様ですが、こちらは逆に最小値をリストから導き出します。Prolog にも流れの方向のようなものがあり、意識する必要があるときもあります。
4. ABC087B - Coins
get_string(String) :-
current_input(Input),
read_string(Input, ' \n', '', _, String).
get_number(Number) :-
get_string(String),
number_string(Number, String).
satisfy(U, V, W, A, B, C, X) :-
between(0, A, U),
between(0, B, V),
between(0, C, W),
500 * U + 100 * V + 50 * W =:= X.
main :-
get_number(A),
get_number(B),
get_number(C),
get_number(X),
findall(_, satisfy(U, V, W, A, B, C, X), Patterns),
length(Patterns, Length),
write(Length).
:- main.
between/3 は、between(最小, 最大, 値) という形をとり、値が 「最小 $\le$ 値 $\le$ 最大」を満たすかどうかを確認する役割と、逆にそれを満たすように値を割り当てる役割とがあります。今回は後者を使っていて、これを満たす全ての A、B、C の組み合わせの中から、さらに等式を満たすものを探し出します。
5. ABC083B - Some Sums
さて、ここまでがわかっていたら、ここからは何も問題ないと思います。
get_string(String) :-
current_input(Input),
read_string(Input, ' \n', '', _, String).
get_number(Number) :-
get_string(String),
number_string(Number, String).
digit_sum(0, 0) :- !.
digit_sum(Number, Res1) :-
divmod(Number, 10, Q, R),
digit_sum(Q, Res2),
Res1 is R + Res2.
satisfy(K, N, A, B) :-
between(1, N, K),
digit_sum(K, Ds),
between(A, B, Ds).
main :-
get_number(N),
get_number(A),
get_number(B),
findall(K, satisfy(K, N, A, B), List),
sum_list(List, Sum),
write(Sum).
:- main.
divmod/4 は divmod(割られる数, 割る数, 商, あまり) としたときに 商 is 割られる数 div 割る数, あまり is 割られる数 mod 割る数. と等価です。
6. ABC088B - Card Game for Two
get_string(String) :-
current_input(Input),
read_string(Input, ' \n', '', _, String).
get_number(Number) :-
get_string(String),
number_string(Number, String).
get_numbers(0, []).
get_numbers(N, [X|Xs]) :-
get_number(X),
N1 is N - 1,
get_numbers(N1, Xs).
solve([], 0).
solve([X], X).
solve([X|[Y|Xs]], Ans1) :-
solve(Xs, Ans2),
Ans1 is X - Y + Ans2.
main :-
get_number(N),
get_numbers(N, A),
sort(0, @>=, A, Sorted),
solve(Sorted, Ans),
write(Ans).
:- main.
注意点として、sort/2 は重複が取り除かれてソートされてしまいます。ということで、sort/4 によって重複は残しつつ、降順であるようなソートをしています。詳しくはドキュメントを読んでください。
7. ABC085B - Kagami Mochi
get_string(String) :-
current_input(Input),
read_string(Input, ' \n', '', _, String).
get_number(Number) :-
get_string(String),
number_string(Number, String).
get_numbers(0, []).
get_numbers(N, [X|Xs]) :-
get_number(X),
N1 is N - 1,
get_numbers(N1, Xs).
main :-
get_number(N),
get_numbers(N, List),
sort(List, Unique),
length(Unique, Length),
write(Length).
:- main.
逆に sort/2 を利用して重複を除いたカウントをしています。
8. ABC085C - Otoshidama
get_string(String) :-
current_input(Input),
read_string(Input, ' \n', '', _, String).
get_number(Number) :-
get_string(String),
number_string(Number, String).
main :-
get_number(N),
get_number(Y),
findnsols(1, [A, B, C], (
between(0, N, A),
between(0, N, B),
between(0, N, C),
A + B + C =:= N,
10000 * A + 5000 * B + 1000 * C =:= Y
), Res),
[[A, B, C]] = Res ->
write(A), write(' '), write(B), write(' '), write(C);
write('-1 -1 -1').
:- main.
=/2 は、単なる比較である ==/2 と違って単一化を起こすので、==/2 より強いです。
問題として、この解法はおそらく $O(N^3)$ なので遅いです。AtCoder に Prolog が追加されたらちゃんと考えてみます。
9. ABC049C - 白昼夢 / Daydream
get_string(String) :-
current_input(Input),
read_string(Input, ' \n', '', _, String).
satisfy([]).
satisfy([d, r, e, a, m | Rest]) :- satisfy(Rest).
satisfy([d, r, e, a, m, e, r | Rest]) :- satisfy(Rest).
satisfy([e, r, a, s, e | Rest]) :- satisfy(Rest).
satisfy([e, r, a, s, e, r | Rest]) :- satisfy(Rest).
main :-
get_string(S),
string_chars(S, Chars),
satisfy(Chars) ->
write('YES');
write('NO').
:- main.
文字のリストを dream, dreamer, erase, eraser で消費していって、空になったら成功します。Prolog の探索の強さが現れています。
ただしこの解法では探索に幅が生じていて、どのくらいの速さになるのかはわからないです。想定解は逆から消費していっています。
10. ABC086C - Traveling
get_string(String) :-
current_input(Input),
read_string(Input, ' \n', '', _, String).
get_number(Number) :-
get_string(String),
number_string(Number, String).
possible(0, _, _, _).
possible(N, T0, X0, Y0) :-
get_number(T1),
get_number(X1),
get_number(Y1),
T is T1 - T0,
X is abs(X1 - X0) + abs(Y1 - Y0),
T >= X,
T mod 2 =:= X mod 2,
N1 is N - 1,
possible(N1, T1, X1, Y1).
main :-
get_number(N),
possible(N, 0, 0, 0) ->
write('Yes');
write('No').
:- main.
面倒だったので、入力とループを同時に行っています。この問題は入力を行ごとに見ながら前回の行と比較していき、すべて条件を満たしていれば Yes、そうでなければ No となります。
すべて問題なく終われば (N = 0) 成功です。成功か失敗かをそのまま記述できるのも Prolog の強みです。
エピローグ
次回の AtCoder の言語アップデートで Prolog が追加される可能性が浮上してきています。もし Prolog が追加されれば色々な問題が Prolog で解かれるようになり、計算量やベストプラクティスなどの考察も栄えていくことでしょう。楽しみですね。