Codeforces Round #434 (Div. 1, based on Technocup 2018 Elimination Round 1)
3完99位
Unratedめ…
A問題
文字列が与えられる。その中に2種類以上の子音が3個並んでいたら切る問題。
切る回数を最小にしたい。
前から貪欲に調べていって条件を満たし次第切ればよい。
貪欲なのでO(N)
http://codeforces.com/contest/860/submission/30422539
B問題
電話番号がたくさん与えられる。それらを連続部分列で識別する場合、各電話番号について一位に定まり且つ最も短い連続部分列を求める問題。
まず全ての連続部分列を求めておく。その後各電話番号について連続部分列を求め、あらかじめ求めたものと見比べればよい。mapで殴る。
O(N(logN)^2)だと思うけど定数倍がでかい。
http://codeforces.com/contest/860/submission/30428030
C問題
たくさんの文字列とその文字列が全体の中で前に来るか後に来るかの情報が与えられる。最終的に文字列を1~Nまでの数字に置き換えつつ並び順も正しくしたい。
まず、数字としては正しいが位置が間違っているものを探し出し、それらを優先的に移動させる。その後、関係のないものを移動させる。
ただし、移動させられない場合は間違った場所にあるものを一度変な名前に変えてやるとよい。セグ木で殴る。O(NlogN)
Ratedだったら+81だったらしいのでつらい…
