脳log[20220617]

2022年06月17日 (金) [AtCoder] 精進。第６回PAST-L「都市計画」と第１回PAST-L「グラデーション」。都市計画を解いたら以前解けなかったグラデーションと同じ問題だったのでそちらもついでに解けた。都市計画自体も以前解けなかった問題だけど、それは 20211031 に Cosmic Rays を解いていたから。初見で解けなかった Cosmic Rays が解けたのは日を空けて問題文を２回読んだから。解けるまで挑戦すれば必ず解ける！(ただし期限が有限とは限らないが生は有限)■すべての頂点が同じ扱いなら迷わず UnionFind でクラスカル法なんだけど、必須ではないオプションの頂点があるせいで困ってしまう問題。全探索するならオプションを仮にいくつか必須扱いにしてそれが最適ではなかったとしても他の試行でカバーできるから問題ないんだよね。先日「難しいなこれ。ある時点のループにおいてベストを求めなくていいし不正確でもいいということを見極めて受け入れるのは」と書いたけど、自分はこの手の見極めが苦手みたいだ。■提出 #32497250 (都市計画 / AC / 721 Byte / 176 ms)。提出 #32497605 (グラデーション / AC / 527 Byte / 67 ms)。■■■精進２。第５回PAST-L「T消し」。曲者の T が ABA 型だろうということは以前からわかっていたが、ではそのときの最適な消し方をどう組み立てればいいかがさっぱりわからない。■提出 #32506171 (AC / 341 Byte / 63 ms)。解法ガチャを何度も引きました。AC は偶然との説あり(乱択というわけではない)。■当たりを引いたガチャ解法について。T=ABA のときに S から (A+B)+A+ というパターンにマッチする部分文字列(複数)を抽出してこれを対象にして考えた。それ以外を考えなくていい理由は、A に左右を挟まれていなければ反応が起こらないことと、B が連続していたり A と B 以外の異物が存在している部分を超えては反応が広がらないこと。次にこの (A+B)+A+ 型の文字列で反応が停止する条件が何か。１.A を使い尽くした。２.B を使い尽くした。３.B と B のあいだの A を使い尽くした。１と２は反応物の一方を限界まで使い尽くしているので問題ないが、３のケースでは A と B が A+BB+A+ という形で残っている可能性があり、ここには最適化の余地がなくはない。ここから、A と B を使い尽くすための B を消費する戦略を貪欲法で実装した。貪欲にやって局所最適に陥る危険があるかないかはわからない。