試験やらレポートやら院試で何もできていなかったので久々の復帰戦 一方現環境のABC全く勝てないので青には落ちたくないよ～
結果
oooo(2)- 517位
Perf:1852 2013→1998 (-15) 😨
A問題
Submission #69073884 - AtCoder Regular Contest 205 (Div. 2)
使える四角の左上を消し続けるで問題ないことがわかる
クエリになっても結局区間内に使える左上は何個？ を解けばよい 00:07:30
B問題
https://atcoder.jp/contests/arc205/submissions/69078507
本当に何もわからなくて手元にいろいろ書いてみると、K_3とかK_5 みたいな奇数の完全グラフは全部白から全部黒にできそうな一方偶数はダメそう
全部白のK_2nを操作すると残った白い辺が完全マッチングになっている→よく見たら1回の操作で頂点から出ている白い辺の偶奇は保存するので、どうせこの下で最適が達成できる→AC 00:40:56
C問題
同じ向きの人の間で包含関係にあるものがあったらダメ、違う向きの人の区間が重なっていたらダメ これが全てだが判定を書くのが少々重い...... 01:05:10
D問題
https://atcoder.jp/contests/arc205/submissions/69086498
min((n-1)/2,n-最大距離)かな～→WA
真面目に考える。 一番しんどい状況を考えるとして各分岐で最も頂点サイズの大きい方に進むしかない。それ以外の頂点は後で適当にマッチできる。すると、最初に木DPで部分木の重さを求めておき、一番重い子に進むというシミュレーションを行えばよいことがわかる。進んだ先の頂点がマッチに使えるかどうかは今まで進まなかった部分の頂点に余裕があるかどうかで判別できる。
E問題
読んだだけ ゼータ変換ってオンラインでできるんですか？ というかこれ解けなきゃダメなんですか？？？
感想
ABCの練習を、します
