AOJ2170: Marked Ancestor
Marked Ancestor | Aizu Online Judge
解き方
- 対応するMarked Nodeが同じ頂点が同じ集合に含まれるようなunion findを作る
- 一旦、最終的なunion findを作って、クエリを後ろから辿りながらunion findを更新する
ハマったところ
- 同じノードに複数回マークつけている時の処理でミスってた
ARC082 D: Derangement
解き方
- となるiの個数を数える
- ただし、上記のようなiが連続している場合、その2つを入れ替えれば良いので差し引く
ハマったところ
- 特になし
https://github.com/HiroakiMikami/procon-workspace/blob/master/src/atcoder/arc082/d.ccgithub.com
ARC082 C: Together
解き方
- 差が2以下であれば、同じ数字にできる
- 差が2以下となる数字の個数の最大値を求める
- ソートして、尺取り法すれば良い
ハマったところ
- 特になし
https://github.com/HiroakiMikami/procon-workspace/blob/master/src/atcoder/arc082/c.ccgithub.com
AGC019 B: Reverse and Compare
解き方
A[i] == A[j]
を満たすA[i..j]
を反転させる時、A[i+1..j-1]
を反転させた時と同じになるので、それを引く
ハマったところ
- 最初回文を除かないといけないと考え、実装はしたものの
O(N^2)
から落ちなかった - 回文を除く方針は、サンプルの時点で通らないが、実装ミスで通ってしまっていたので方針から違うことに気づくのが遅れた。
https://github.com/HiroakiMikami/procon-workspace/blob/master/src/atcoder/agc019/b.ccgithub.com
AGC019 A: Ice Tea Store
解き方
- ただの貪欲
ハマったところ
- なんか貪欲法の実装に手間取ってしまった記憶がある
https://github.com/HiroakiMikami/procon-workspace/blob/master/src/atcoder/agc019/a.ccgithub.com