脳log[20230418]

2023年04月18日 (火) [AtCoder] 精進２。ABC146-F「Sugoroku」(水 diff)。Sugoroku という名前の問題は、調べて予想の倍あって驚いたんだけど、２、３、４まであって、前回の ABC でもちょっと変化球で Unfair Sugoroku という名前の問題があった。いずれも確率と期待値の問題。だから初代が最短(辞書順)最小の手順を答える問題だったのが意外。■１手につき１から M マスまで進める。最短であることが第一だから、まずは M マス進めるときは M マス進んでしまう。無理なら M-1 マス、M-2 マス……。いっぱい進みすぎてしまうことで誤って到達不可と判断してしまうおそれはない。それはつまり M マス連続してゲームオーバーマスがあるということであり、どう手順を刻んでも結果は変わらない。次に、同じ手数のなかでは辞書順最小の手順を答えにしなければいけない。このために最短手順を求めるときはゴールから貪欲に最大歩幅で移動を繰り返し、最小手順を求めるためにはスタートから逆向きの移動を繰り返した。結局、最初の１手を最小限に小さく刻んだ後は最大歩幅での移動を繰り返すことになるのだね。■提出 #40753539 (AC / 203 Byte / 113 ms)。すんなり AC できたわけではない。最初は DP のつもりで各マスに最小手数と最小手数の中での最小出目の２つを記録していった。答えは合うけど TLE。次は各手数において到達可能な範囲を表す２つの数を記録していった。M が大きい場合に DP 配列を１マスずつ埋める手間が節約できたけど、これも２ケースは TLE が避けられなかった。最終的に各手数において可能な移動先の先端だけを記録するようにした。■■■精進１。ABC141-E「Who Says a Pun?」(水 diff)。これまでも何回か読んだことがある問題だけど実装には至っていなかった。■提出 #40750806 (AC / 218 Byte / 1688 ms)。N 個の各添え字について、長さ１のプリフィックスが共通するもの、長さ２のプリフィックスが……、と順番にグループを細分化していった。その過程で同じグループの中で最小の添字と最大の添字の差がプリフィックスの長さより大きいことを確かめる。■Ruby によるすべての提出を見ると最速は 87 ms なので 1688 ms は２桁遅い。見ると、添字と長さを０から開始して、見つかれば長さを伸ばす、見つからなければ添字を増やして再検索する、という手順を繰り返すみたい。じっくり見ても混乱するややこしさ。