=> が組み合わさったらハッシュリテラルしか解釈のしようがないやろと期待したのだけど。しかもエラーが Hash の 'key'=>'value' の 'value' の部分を指して「syntax error, unexpected string literal, expecting local variable or method」と出るから意味がわからなかった。'key'=>'value' を 'key'=>value に書き換えたからって有効な構文にはならんやろ。なんかよくわからん => がある、というエラーなら解釈違いだと理解できたのだけど。■B 問題「Binary Alchemy」。1-indexed なのがやっかいといえばやっかい。Ruby での提出を見ると WA がちらほらと、B 問題にしては多い目に確認できて、だいたいどれも元素１に対して元素２から N を作用させているようだった。無視できないレベルでパターン化できそうな間違え方だと思った。■C 問題「Word Ladder」。要素数最小が最初に求められているので、S の各文字を T の各文字に一致させていく操作しかできない。操作には S の文字を大きくする操作と小さくする操作がある。前から小さくし、後ろから大きくする。■D 問題「Cross Explosion」。BIT を使ったけど本当は D 問題に BIT は使いたくない。Ruby での他の人の提出を見ると、同じように BIT を使っている人のほかに UnionFind を使っている人がいた。これはまったく想像がつかない。ほかに BIT より効率的な実装をしている人もいた(#57555275)。■E 問題「Avoid K Partition」。わりと途方に暮れる制約。DP がしたいんだけど、K がでかいし A もでかいので、この２つで状態数を抑え込むことはできない。数列を左から見ていって現在の要素を終端とする全累積和を列挙することはできるけど……。自分が解けなくて４年のあいだ問題を開いて考えて実装しては答えが合わなくて閉じるということを繰り返していた ABC017-D サプリメントに似てるのかな。この問題を思い出して、似てるなら時間内には解けないだろうなと恐れていた。A 数列の２番目以降の要素について、直前に区切りを入れた場合と入れない場合を考えていく。制約を乗り越えるポイントは、区切りを入れない場合に DP 配列をそのまま次の要素にパスできるように状態を記録すること。全体に一律に加算するなら、実際には加算せず加算する値だけを記録する。初期値を決めるところで手間取った。どう初期値を決めても N 個の A 数列を処理すると答えが合わなかったので、最初の１要素を取り出して初期値とした。■F 問題「Cake Division」。完全に途方に暮れる制約。答えの形式から何か手がかりが得られたりしないかな。しないか。■D 問題。BIT より効率的な実装をしようとしたら UnionFind の Find 関数みたいなものを書いていた。UnionFind 解ってつまりそういうこと？ 提出 #57562030 (AC)。各マスに上(下左右)にある壁の位置を記録しておき、このマスに壁がある、というところまでマスを辿る。辿った結果を書き込むことで経路圧縮になる。■■■精進。F 問題。二分探索はわかる。その中で、N 個の切れ目のそれぞれを１カット目とする N 個の累積和について解の判定をするのもコンテスト中にやっていた。そのとき気付かなかったのは、ある切れ目を１カット目とする累積和が最適解を満たさない場合、その切れ目は最適解を満たすどの切り方においてもカットされないということ。つまり答えの２項目目がこのようにして数えられる。そしてもうひとつわからなかったのがダブリング。コンテスト終了後に目に入ってきていた。あとは実装するだけだけど、他の部分が Nlog^2 だからと尺取りできるところで２つ目の log を付けると TLE になるので、オーダーに影響しない定数倍の改善にも励む。■提出 #57605764 (AC / 480 Byte / 4781 ms)。これはコンテスト中には通せません。オーダー的には問題ないはずの提出 #57604731 (TLE×60) がサンプル以外通らなかった。これをコードテストで９秒、７秒と改善していった結果がさっきの AC。定数倍改善に１時間近くかけた。やったことは主に３つ。１．二分探索を尺取りで置き換え。２．N 回のコールバック(ブロック実行)を伴うメソッド呼び出しを N 引数のメソッド呼び出しで置き換え。３．判定関数をこころを込めてインライン展開。コピペをしたくないからペナルティを承知で関数化していたので、代わりにトリッキーなことをしてる(lastcut 変数)。■この問題を DP 的な状態をたたみ込む視点で眺めると、ある切れ目でカットするというとき、それが何カット目であろうとも以降に起こることは同じであり予め計算して結果を流用できるということ。ややこしいのは円環であることから、１カット目の位置に応じてありうる最終カットの位置が変わるということと、１カット目の位置を変えた N 通りを並行して考えないといけないあたり。だけど２周分だけ考えれば間に合う。