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 の値に依らない）で書き表せます。
（これがこの条件式をなるべく書きたくなかった理由です。強い人が見たらもう答えが書いてあるようなものだと思うので…）