良いセットだった。G解けず悔しいね。
Gがかなり面白い。
G
問題概要
まず「N 頂点の任意のグラフについて、k 組以上のマッチングが元のグラフか補グラフに含まれる」が成り立つ最大の k を出力して下さい。
その後「u,v 間に辺があるか」を N 回まで質問して k 組のマッチングを構成して下さい。
解法
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
コンテスト中の思考
とりあえず辺に0,1を割り当てると思うことにする。
まず上界を考える。
0のクリークと1のクリークの間を0で繋ぐのが良さそう。
1/3くらいで分割するとちょうど両方1/3くらいになる。
さすがにこれが上界だろうと思って構成方法を考える。
N 回って少なすぎる・・・
N/2 組とりあえず聞く
→ そこからロスなくやるの無理そう
３頂点のパスごとに分ける
→ 01 は嬉しいが、00,11 は困る
→ 00-11 の間を聞くとちょっと嬉しい
→ その後 00011-00111 の間を聞くとちょっと嬉しい
→ 00011100111 みたいになった後嬉しい行動がなく、詰み・・・
... 2 hours later ...
答え
パス状に聞いていき、隣接が異なる場所が現れたらそこの３頂点を切り離して続行する。
これで大体 1/3 が達成可能。
majority vote algorithm みたいなノリ？
１頂点ずつ追加する方針ちょっと考えて、棄却してしまったな・・・
棄却した思考過程：
00...0 と言われた後に 11...1 と言われると困りそう
00 の間に葉を生やしても 0 と言われて困りそう
でも、01 が出来るのが 00 と言われる以上にかなり嬉しいんだなぁ。
うーん、悔しい。
他の問題
A
簡単枠として面白かった。
B
問題概要：棒がN本与えられるので、等脚台形を作って下さい。
2a > c-b を探したいので、とりあえず a を全部試せば良くてこれはmultisetで出来る。
さすがに楽な解法ありそうに思ったけど、すぐに思いつかなかったので大人しく実装した。
今日は実装の調子はまぁまぁだった。
楽な解法：２個組が複数通りあるなら長方形ができるね
C
いい感じのdp
D
逆
E
こんなの凸に決まってる
F1
分割して条件を考えたら出来た
i,i+2をマージするかどうかの列を考える方がいいらしい？
H
面白そうな見た目をしてるし後で考えてみるか。