AOJ 0568 Pasta

AOJ0568をErlangで解いてみたのでBlogを書きます。
問題の概要については省略します。

前回と同様に JOI 2011-2012 予選 問題・採点用入力 から正答することを確認しています。

-module(aoj0568).
-export([main/0]).

main() ->
  {N, K} = get_pair(),
  Fixed = lists:reverse(lists:sort([get_pair() || _ <- lists:seq(1, K)])),
  io:format("~p~n", [pasta(N + 1, Fixed, {0, -1, -2})]),
  init:stop().

to_i(S) ->
  {I, _} = string:to_integer(S),
  I.

get_pair() ->
  [First, Second] = [to_i(V) || V <- string:tokens(io:get_line(""), " ")],
  {First, Second}.

pasta(N, [{N, P}|_], {Q, _, _}) when P /= Q -> 0;
pasta(N, [{N, P}|T], S={P, _, _}) -> pasta(N, T, S);
pasta(_, _, {P, P, P}) -> 0;
pasta(1, _, _) -> 1;
pasta(N, L, S={P, Q, _}) ->
  case get({N, S}) of
    undefined ->
      Ret = lists:foldl(fun(X, Acc) ->
                            Acc + pasta(N - 1, L, {X, P, Q})
                        end, 0, lists:seq(1, 3)) rem 10000,
      put({N, S}, Ret),
      Ret;
    Memo -> Memo
  end.

コードの概要

入力を受け取って、逆順にソートします。
逆順にソートする理由は引数を減らせるというだけの理由です。
基本的には全探索でパターンマッチにより遷移できない状態排除しています。
本来であれば過去2日分の情報を持つだけで遷移先を決定できるのですが、
過去3日分の情報を持つことでパターンマッチを容易にしています。
遷移する際に過去の情報をスライドさせるだけで良いのでとてもシンプルになります。

終わりに

やっぱりErlangだとプロセス辞書を使ってメモ化再帰が楽に綺麗にかけるので好きです。