54:55 + 1ペナ 6完
Fをすぐ見抜いたのでパフォはほぼカンスト、G解きたかった
A A Unique Letter
場合分け考えたけど、めんどくさかったので二重ループで解きました
(AC 3:34)
B Better Students Are Needed!
(得点、番号)みたいなのをソートしたいときは、pairでソートすることが多いです
普通に書くと、番号が大きい順になりますが「番号にマイナスをつける」と順番が入れ替わるので、問題なくなります
すでに決まった生徒を配列で管理しておいて、スキップするような実装にしました
(AC 9:42)
C Changing Jewels
レベルNの赤から、レベルNの青ができて、逆はできないので赤は愚直に青に交換していい気がします
ただ、それだと「赤を変える→青を変える」を繰り返すだけで制約が小さすぎない？？と思います
で、サンプルを見ると最後の方に大きい値があるので、値が爆発しないためなのかな～と思って、貪欲を書きます
大きいサンプルも合うので、まあいけるやろと提出すると無事AC
再帰を許す制約だったんですね
(AC 14:30)
D Draw Your Cards
実装重め...
「X以上のうち最小のもの」というパターンは二分探索が有効なことが多いです
今回は、値が追加されたり削除されたりするので、setで二分探索をするのがよさそうです(setの二分探索は書き方が悪いとO(N)になるので注意)
あとは、そのカードに重なっている枚数も管理したいので、setより持てるものが多いmapを利用しました
同時に削除されるカードはUnionFindを使って求めました、もうちょっと簡単に書けたかも
UnionFindでの求め方
1. 上に重ねるときにmergeします
2. 食べるときに、ACLでいう「leader」を求めておきます
3. mapでleaderに対応する「食べた時刻」をメモしておきます
4. leaderがわかれば食べた時刻がわかります
(AC 22:21)
E At Least One
すぐには解法が浮かばなかったので、普通に考察します
長さkについて、それぞれ何個か？を直接求めるのではなく、「左端を固定すると、長さは[a~b]の範囲では自由にできるので、[a~b]に1を加算していく」というのはよくある手法です(主客転倒？)
今回もこのテクが有効で、左端(L)を固定するとどうなるか考えてみます
まず、Ai, BiのうちLより小さいものはどうせ使えないので関係ありません
そうでないものを考えると、Lに近いものがわかればよいです(L以上の最小値)
L ≦ Ai < Biなら、Biが入った時点でAiも必ず入ります
Ai < L < Biなら、Aiは使えないので、Biを使うしかありません
こうすると、少なくとも右端(R)をどこまで伸ばさないといけないか？がわかります
それがわかれば、さらにいくら伸ばしても問題ありません
あとは、Lを動かしていったときに高速に更新できればよいです
Rの候補となるものをmultisetに入れます
Ai < L となってしまったら、その瞬間にAiを取り除きかわりにBiを入れます
こうすると、Rは、multiset中の最大値になりO(logN)で管理できます
区間への加算はimosや遅延セグメント木などを使えばよいです
(AC 33:09)
F Find 4-cycle
制約(T < 3000)があまりに変なので、さすがにそこから手を付けます
まずグラフの作り方から、二部グラフになっていることがわかるので4-cycleがあるなら、「1~Sのどれか」→「S+1~Tのどれか」→「1~Sのどれか」→「S+1~Tのどれか」という形になります
もう少し考えると、1~S側の2頂点(A,B)が4-cycleの一部になっているならば、S+1~T側の2頂点(C,D)と両方がつながっている必要があります
つまり、A-C, A-D, B-C, B-Dという辺がなければいけません
ここから直接鳩ノ巣を思いつくこともできますが、直感的な話をすると「辺がめちゃくちゃあったら、Tが少なすぎるのでそんなペア作らない方が難しい」と思います
ということで、Tの頂点をペアとした鳩ノ巣原理にたどりつきます
もう一個発想のヒントとしては、「1つ見つけて出力してください」は鳩ノ巣使うことがそれなりにあります(「あるかどうか判定してください」でも同じ出題はできるので、過信しすぎない)
鳩ノ巣さえ思いつけば、実装はそんなに難しくなくペアをひたすら列挙していけばよいです
ペアの管理にmapなどを使うとTLが怪しいので、二次元配列とかがいいんじゃないでしょうか
(AC 94:25)
G Scalene Triangle Area
条件を整理してみます
(u-s)が1増えると、条件を満たす(v-t)が2だけ減るので、長さが2ずつ減るように塗っていくことがわかります
塗るマスは区間になるので、遅延セグメント木を使ってうまく管理できないか考えます
i行目からi+1行目に移るときに、「届かなくなるマス」をうまく管理できれば良いです
これは「今右端がyのものが何個あるか？」を配列で管理しておくことで解決できます
もし、右端がyなら、i+1行目に移ったときに右端はy-2になるので、y-1, yから1だけ引くことで移動を表現できます
ただし、もとあった位置から左側に行き過ぎないように注意しないといけないので、横方向の長さが0になったら取り除くようにします
取り除くときはM行後になるので、取り除く位置を配列にメモしておけばよいです
クエリについては、先読みしてxの小さい順に答えていけばよいです
分かりにくいと思うので実装例をのせておきます
総括
鳩ノ巣何回かやられたら覚えた
