脳log[20220627]

2022年06月27日 (月) [AtCoder] 精進。前回の ABC-E に関連して「既視感がある問題。それも WA がいつまでも取れなかったことで記憶に残っている」と書いていた問題。ABC118-D「Match Matching」(ギリギリ青 diff)。16 個の WA/RE 提出の末に 4 WA(#13237877) まではいっていたのだけど行き詰まっていた。それから２年を経て改めて問題を読めば、DP だろうなあと嗅覚が働く。３年前も２年前も謎の貪欲法(バックトラック付き。つまり打ち切りありの再帰)でやっていたみたいだけど。■提出 #32816278 (AC / 361 Byte / 71 ms)。マッチの本数に対して桁数の最大値を記録する DP をやって、なんとなーく経路の復元をして答えとした。DP の復元という比較的最近仕入れた概念は『典型90問』の成果。限られたパラメータを広範囲に展開して書き込むよりもっと上手い方法があるんじゃないかと思いつつ、ループの中で DP 配列を右へ左へ全長に渡ってなめなめ更新しても許されているのでまあいいか。■他の提出を見ると Ruby なら桁数でなく作った数そのものの最大値を記録するのでも良かったらしい。だけどこの問題を連想させた問題で Bignum に起因して TLE になっているので、そういう選択はできなかったな。最大で 5000 桁になるのを確認して避けたもんな。■Ruby で最速の提出はいずれも答えの数字を３つの部分に分けて考えているようだった。２年前の自分が 4 WA を解消できなかったのはこの構造が見抜けていなかったせいだろう。貪欲さが足りなかった。