AtCoder Beginner Contest 237

 　FHが解けず六完。Eが嘘解法だった。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 237　F、Hが解けず。
D 難しい。次の文字がLのindexとRのindexで分けて、R+L[::-1]
E ダイクストラ
G X=1、Xより大きい数を2、小さい数を0にすると、加算更新の遅延セグ木で解ける。あんまり関係ないけどhttps://t.co/1LGrFRyfgR　の解説を見に行ったら落ち着いた。

— titia (@titia_til) January 30, 2022

E - Skiing

　楽しさの変化を距離とみなしてダイクストラと考えて、負辺があるけど大丈夫そうな気がして投げたら通ってしまった。after_contestで落ちたのは納得。

　正しい解法は、登るときだけ標高差をコストとみなして、ダイクストラ。そして、全頂点探索し、スタート地点との標高差で楽しさを計算。というのは、言われれば分かるけど、なかなか思いつきにくい印象。

　コンテスト中、TLEが返ってきたら、解けていなかった気もする。

F - |LIS| = 3

　これは通せなくてはいけなかった。

　LISのDPを考えたとき、各長さのLISの最後の値の最小値を持ってDPする。それをそのまま持てば良い。

　コンテスト中はなぜか、各文字が最後に来るような最長のLISの長さは？　と考えてしまっていた。これだと$4^10$もたなければいけないので、間に合わない。

Ex - Hakata

　解説放送を見てAC。

・Dilworthの定理：推移的なDAGについて、最大独立集合（任意の二点に辺が存在しない頂点集合の最大サイズ）と最小パス被覆の本数が一致する

　を用いて、フロー（mincut）の問題へ帰着するところが難しい。

　ただ、回文を列挙した後、グラフの問題として見てみたら、フローの雰囲気を感じ取ることはできてもおかしくないか。