読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

AOJ2538 Stack Maze

勉強会の問題がICPCっぽく(悪い意味で)なってまいりました.

問題文

Stack Maze | Aizu Online Judge
日本語訳が欲しい方は「mayoko stack maze」とかで検索するとよいです.

解法

最初に思いつくのはdp(r,c,今持っている宝石のスタック)というDPだと思いますが,多分間に合いません.

書くのが面倒なのでN=HWとします.
すると,次に思いつくのはO(N^3)の次のようなDPだと思います.

dp( (r_s,c_s) ,(r_t,c_t) ) :=(r_s,c_s)からスタートして(r_t,c_t)までスタート時点で積まれているスタックに影響を与えずに稼ぐことのできる得点の最大値
とすると全体O(N^3)で全ての長方形で取得できるスコアを計算でき,最終的にdp( (1,1),(H,W) )が答えになります.
これのやり方については(r_s,c_s),(r_t,c_t)が宝石と穴の対になっているかで場合分けをしてごにょごにょします.

上記の解法では間に合わないのでもう少し考えます.
宝石と穴の関係について,一つのデータセットには同じアルファベットが最大10までしか存在しないので,宝石,穴の組み合わせについては10*10*26=2600でほぼNの最大値と一致します.先ほどのDPについて考えると,考えるべき座標の対( (r_s,c_s),(r_t,c_t) )は宝石と穴のペアとスタート,ゴールだけでよさそうです.
よって状態数がO(N)に落ちて,各状態の更新をO(N)でやれば全体O(N^2)ぐらいでできるはずです.

具体的にどういう実装をしたかというと,メモ化再帰を行いました.
f(S,T)について,始点Sから終点Tまでいくつスコアを稼ぐことができるかという配るDPを行います.
今見ているマスが通常マスならそのまま右下への遷移を行い,宝石マスなら長方形内の穴との対f(S_c,T_c)を全探索し,DPの表に反映させます.
これをメモ化再帰によってO(N^2)で求めています.
実際は宝石と穴とのペアの探索で高々10回のループを回しているので,5*10^7ぐらいの計算回数になると思います.