AtCoder AGC029 D Grid game - メモ@inudaisho

　書くほどでもないかもしれないがちょっと違ったやりかたで解いたので書いとく。

(20181217追記解説PDFもようやく出たけどこの解法に近いものが言及されてた)

AGC029 D Grid game
Python と辞書

AGC029 D Grid game

問題

　(1,1)からひたすら落ちる高橋君を青木君が右へ1づつ操作してなるべく高いところのブロックに乗せて落下距離を短くする

オレオレ解法

　模範解法では各行毎に最も左のブロックを入れた配列をつくってるようだが、ここではブロックの系列に着目する。系列というのは x-y (x=4,y=3 なら 1)の数字で代表する系列で、下の画像で斜めに線を引いたのがそれになる。 (系列という術語があるわけではなく勝手語)

(20181217追記解説PDFだと(x,x-y)に座標変換と書いてある)

f:id:inudaisho:20181216210055p:plain — 入力例2

　高橋君と青木君は交互に打つので最大で斜めにしか進めない。このx-yの系列で一番距離が近いのをその系列のブロックの代表とする。図でいうと○がついてるのがその代表ブロックになる。こうすると何がよいかというと、行けるか行けないかがすぐわかる。上の図では(1,1)から斜めに進んで行ける一番近いところにAがあるが、その下のブロック(4,3)は1(=4-3)系列の先頭のブロックになる。しかし図からわかるように(2,2)にある0系列のブロックが邪魔で実際には行けない。しかし0系列の先頭が(4,4)だと行けることになる。この違いはマンハッタン距離(x+y)で持っておくとすぐに比較できる。(2,2)は4,(4,3)は7,(4,4)は8。系列が隣接しているとき、その一つ前の系列の距離が小さいときはその後ろの系列の先頭のブロックの上に高橋君を置くことはできなくなる。という具合に系列別に先頭のブロックを出し、系列順に並べて一つ前の系列にブロックがあるか、あるときその距離が小さいか大きいかを見ておくとそのブロックに高橋君を置けるか判定できる。そうして出した到達可能なブロックが図の場合、B,Cの下の(7,3)、(8,1)になる。今度はその配列のxの最小を出せばよい。0系列は実際には高橋君を置けないのだが、到達可能かどうかを判定するのに必要なので入れておき、最後に0系列を除く。もしこれでブロックが残らなければ高橋君を置けるブロックはないので盤面の下まで落ちてもらうことになる。

AtCoderで提出したの(事後)

わりと整理したのがこれ。

beta.atcoder.jp

高橋 = H
if N:
   # ( 略 )
print(高橋)

　Python3 だとこんなふうに変数を置くこともできます。

Python と辞書

　Python は遅い遅いと書いてるが、遅いというより高機能なだけである。だから高機能なのを必要なときにジャンジャン使っていけばよい。この場合は辞書で、C++ だと行毎の配列にした方が速いのかもしれないが(よく知らない)、そのやりかたをPython で書いたものと、この解法を辞書で実装したものと実行速度的には大差ない。実行速度順に並べたときの上位の常連というのがあるが、その人らが書いてもこれと同じくらいの実行速度なのでまぁそうまちがいはないとおもう。Pythonの辞書は便利、計算量もO(1)、すぐリストなどに変換できるのでデータをいじりまわすときに便利。

　(ちなみに実行速度はAtCoderの点数にはまったく関係ないが、実用的には気になるところ。どうせ早解きはかなわないのでそこだけ気にしてAtCoderをやってる。とはいえあらゆる局面で実行速度を削ってるわけではなくある程度複雑なロジックのもので気にしている)