低得点ARC。3完勝負になるのか、あるいは難しくて2完できれば御の字になるのか。まあ難しかったんだけど。普通に2完だった。CDは、たまにはこういう問題欲しいよねという感じのだった。開始前に順位表から最初の問題を開いておいて、時間になったらF5。
C - K-th Substring
5000だから2乗は通る。Cなのに解き方が全然見えない。Kが5以下と異様に小さいことに気づく。構成してみるか。Kが1なら簡単。辞書順最小の1文字を取ってくればいい。2だったら、その1文字の後の最小文字を探す、最後の文字だけなら別の文字を、けっこう面倒だな。5は無理じゃね。substringはO(N^2)個だし、ソートといえばトライ木とか？いや無理だろうな。色々なケースを考えてみる。aaaaaaみたいな文字列かもしれないし、ランダムっぽい文字列かもしれない。文字列のタイプによって（人間が出力を考えるなら）戦略が変わってくる。
ん、長さ5のsubstringを考えれば、それより辞書順で小さいsubstringを自明に生成できるな。文字数を減らせば、ことなる文字列になるし、辞書順でも小さくなる。答えはK文字以下としてよさそうだ。それなら力ずくソートできるのでは。オーダーは大丈夫そうだが、string（つまりvector）を大量に持ってそれをソートするのはどうなんだ。まあいけるやろ。ある位置からK文字取れないこともある。それはif文で除いた。実際はuniqueかけるから問題ないんだろうけど、ここはしっかり書いておくところ。あとはsortしてuniqueしてK番目を出力するだけ。uniqueの使い方はググった。今回は問題の制約から戻り値を使う必要がなかった。
D - Equals
p_i=iとなる最小のiを最大化したいのだと誤読。そう読むと、そういうiが存在しないケースについて問題文やサンプルの説明を探すことになる。まあ誤読だったわけだ。個数を最大化したいのね。制約で、xとyを入れ替えた実質的に同じペアが許容されているように見えたのが気になった。いつものように入力を0-indexedに修正する。そのとき、問題設定がやや複雑なので気分的な確認に少し時間を使った。
これは連結成分内なら好きなように配置できる。ライブラリのグラフを使うか。んー、そこまでする必要はない。UnionFindか。使うの久しぶりだなあ。さて、これでもう解けたと思いきや、どうやって数えるかがパッと出てこない。Nは10^5なのでO(N^2)が通らない。連結成分毎にO(N)とかかけてると定数倍は小さくてもTLEの恐れがある。
まあちゃんと考えれば方針は立つ。UnionFindのrootの値でソートしてrootの値で区切り、位置と数をそれぞれ配列に入れてsort, set_intersectionすればいい。O(NlogN)の処理を分割してやっているので速いはず。ただ、区切るのが相当面倒。このへんライブラリ化できなかったかなあとか思ってた。
面倒なので他の方法も頭の中で考える。位置と数、どちらも0以上N未満、それを両方横1列に（幅Nで該当位置に）並べて、同じところにあったらカウントする。これは連結成分毎にやらずとも、まとめてできるのではないか？連結成分のrootをIDとして書き込む。重複はない。全部埋まる（だからvectorの初期化は考えなくていい）。サンプルは通ったが、ちょっと確信がなくて30秒くらいコードを読み直した。まあそのまま提出してAC。
解説を読むと、そうか各位置についてその数を既定の場所へ持って行けるか見ればいいのね（と書くために10分以上考えた（まだ正直理解があやしい））。連結成分内なら好きな順列が作れる、というところまでは考えたが、それをこういう捉え方はできなかったなあ。
