Eまで。unratedになったこともあり、Gは見ずFを考えていたが分からずに終わった。unratedでやや集中力が途切れてしまったが、集中しても解けていなかっただろうと思う。
F - Square Subsequence
解説AC。
解説を見ると確かに典型の組み合わせなのだが、結構難しいと思う。
制約を見ると、何らかのDPをするとは予想できる。
また、重複して数えないため、できるだけ左にある文字で構成される「TT」を考えようとは思える。
だが、二つ目のTの一文字目を決め、部分列DPを使って次の文字の位置を前計算しておくと、そのうちどういうものが「できるだけ左にある文字で構成される「TT」」二番目の条件を満たしているかが分かる……というのは言われてみれば分かるが思いつかなかった。
G - Minimum Permutation
（デバッグでWAのテストケースを探すとき他の人のコードは見たけれど）解説は見ずにAC。
一番はじめにおける候補（その後に、今まで使った以外の全ての数字が登場している）のうち最も小さいものを採用……というのを繰り返していけば良い。
解法はそれで良いが実装がやや面倒で、BITやセグ木を使った。
実装難ではあるけれど、解法を思い付く難易度はFより簡単ですね。
0 件のコメント:
コメントを投稿