titiaのノート: 部分列DP

ラベル 部分列DP の投稿を表示しています。すべての投稿を表示

2026年6月13日土曜日

　A一完。

コンテスト後のツイート

yukicoder contest 501 AだけAC。
連続する数字をまとめて管理するようにしたら色々やりやすかった。
— titia (@titia_til) June 5, 2026

　解説AC。

　そもそも通常の部分列DPでK=1の場合を解くことができなかったのは反省。

　しかし、そこを理解しても難しかった。

　まず、部分列DPでNEXTを使わずにやる方法があることを知らなかった。それを行列累乗に持ち込むためにどういうコードを書けば良いかも分かっていなかった。

　勉強になった。

　実験して、行の数が足りていればいけそうな解法と、ギリギリでも大体大丈夫な解法を作り、組み合わせることで無理矢理ACしたが、多分Hack caseがあります……。

　とりあえず、良いペアという条件が、gcd(a,M)%gcd(b,M)==0 or gcd(b,M)%gcd(a,M)==0と表せることだけは理解しておこう。（ACしたのにそれすらよく分かっていなかった）

　A一問しか解けなかった。ひどい。

　一応自力AC。

　Tester解説と同じ方法だと思うんだけど、計算量がよく分からなかった。

　五乗じゃないの？　と思ったけど、ちゃんと解析したら四乗になりそうな気もしてきた。

　解説AC。

　隣接xorを考えるのだから、累積xorを考えてみるというのは典型なのだろうが、思いつけなかった。

　その後の部分列DPのやり方も実は知らなかった気がする。各文字についての配列を持たなくてもできるとは聞いたことがあったが、こういう風にやれば良いのか。

　Eまで。unratedになったこともあり、Gは見ずFを考えていたが分からずに終わった。unratedでやや集中力が途切れてしまったが、集中しても解けていなかっただろうと思う。

　解説AC。

　解説を見ると確かに典型の組み合わせなのだが、結構難しいと思う。

　制約を見ると、何らかのDPをするとは予想できる。

　また、重複して数えないため、できるだけ左にある文字で構成される「TT」を考えようとは思える。

　だが、二つ目のTの一文字目を決め、部分列DPを使って次の文字の位置を前計算しておくと、そのうちどういうものが「できるだけ左にある文字で構成される「TT」」二番目の条件を満たしているかが分かる……というのは言われてみれば分かるが思いつかなかった。

　（デバッグでWAのテストケースを探すとき他の人のコードは見たけれど）解説は見ずにAC。

　一番はじめにおける候補（その後に、今まで使った以外の全ての数字が登場している）のうち最も小さいものを採用……というのを繰り返していけば良い。

　解法はそれで良いが実装がやや面倒で、BITやセグ木を使った。

　実装難ではあるけれど、解法を思い付く難易度はFより簡単ですね。