うにゅーん、って感じだ

SRM highest:1959. C#を書きます.

Advent Calendar Contest 2017 Move on grid 雑記

解説 Advent Calendar 2017

これは解説 Advent Calendar 2017 の 13日目の記事です。
adventar.org
ちゃんとここまで埋まってきていてすごい!


問題の解説ページにわりとちゃんとした解説を書いたので、こちらはどちらかというと雑記という感じです。

ひとこと

この問題、わかっちゃえば簡単だからみんな解いて!!!!!!

雑記

問題はこちら。
No.612 Move on grid - yukicoder


解説の方にも書きましたが、これは今年の東大の入試問題を参考に作成しました。
当時ほんのちょっとだけ twitter で話題に上がったので、覚えている人もいるかもしれません。

今回の問題は、それを少しだけパワーアップしたものになります。
おそらく解説が上がるまでに通した人数は(writer/tester 除き)16 人で、これは想定よりだいぶ少ないなぁと思いました。

多分 {d \leq ax + by + cz \leq e} という条件をうまく噛み砕けなかったのだろうと思うのですが、元々は「平面 {ax + by + cz = d} と平面 {ax + by + cz = e} に挟まれた領域」みたいな感じに表現しようかなと思っていて(こちらよりはわかりやすいんじゃないかなぁと思っていたのですがどうでしょう…)。ただそれだと、そもそもこの平面がどんなものか想像するのに数学能力とコストを要しそうだなぁと思い、領域の概形がわからなくても式変形してれば解ける、みたいな大学受験数学にありがちな感じになりました(でもこんだけ解かれないなら難しくしちゃえばよかった……)。


上に書いた通り、この問題で出てくる {d \leq ax + by + cz \leq e} という条件は、3次元空間上の無限に広い分厚い板みたいなものを表しています。パラメータの値によって、その板がすごく分厚くなったりするわけですが。

それがわかった上で、どうすればこの問題の解法に行き着くかですが、まず単純に、以下の問題を考えてみましょう。

~~~~~~~~~~~~~~~~~~~~~~~~~
2次元平面上の原点に点Pがいて、1秒ごとに隣接する格子点にそれぞれ 1/4 の確率で移動する
そのとき、6秒後に直線 y = x 上にいる確率は?
~~~~~~~~~~~~~~~~~~~~~~~~~
(これは元ネタの東大の入試問題そのままです)


この問題の解法はいろいろありますが、自分が考えたのは以下のようなものです。

~~~~~~~~~~~~~~~~~~~~~~~~~
x の正方向、y の負方向に動くのは両方とも直線から見て右下方向に動いていて、
x の負方向、y の正方向に動くのは両方とも直線から見て左上方向に動いている。
よって、右下方向に 3 回、左上方向に 3 回動けば良いので、...
~~~~~~~~~~~~~~~~~~~~~~~~~

つまり何を言っているかというと、(1, 0) にいる状態と (0, -1) にいる状態は、どちらも上か左に 1 だけ移動すれば y = x に戻れるので、同一視できるよね、という話です。動的計画法みがあふれてきました。
より一般的に言うと、今いる点の座標じゃなくて、 y = x + k の k の値さえわかっていれば良い、k が同じだったら同一視できる! というものです。


と、この話が、もちろん今回の問題にも利用できます。

条件式 {d \leq ax + by + cz \leq e} を見ると、x, y, z の値は重要でなく、 {ax + by + cz} の値さえあれば良い、ということがわかるような気がします。
実際、解説にもあるように、6方向の移動は、全て {ax + by + cz} の値の増減(x, y, z の値に依らない)で書き表せます。
(これがこの条件式をなるべく書きたくなかった理由です。強い人が見たらもう答えが書いてあるようなものだと思うので…)


というわけで、1次元の DP に落ちたので、これを解けば ok、という話でした。


個人的な動的計画法の話

個人的に、動的計画法の本質は

  • 部分問題に落とす
  • 複数の状態を同一視もしくは最適なものを選別し、状態数を減らす

だと思っていて、特に重要なのが 2 番目だと思っています。


例えば、いくつかの問題の配点が与えられて、これらで合計 P 点を取る方法は何通りあるか、みたいな問題だったら、
「i 問目まで見て、合計点が j 点」という状態が同一視できるので、これにより状態数が減らせます。

また、ナップサック問題だったら、「i 番目の荷物まで見て、重さの合計が j」という状態の中では、価値が最大のものが(その後どのような選び方をしたとしても)最適である、ということがわかるので、状態数を減らせます。


このように、動的計画法はどのような方法で問題を解けるようにしているのか、という本質が見えると、例えば今回のような問題でも、どこか状態を同一視できないかな……と考えるきっかけになりますし、色々な DP 問題を解けるようになると思います。