AGC029B
B - Powers of two
- 考えたこと
- 和が2ベキになるペアを列挙しておいて、頂点の重複がないように選ぶ
- しかし素朴にやると「各ペアについて和が2ベキかチェック」が10^10で無理
- ある二つの数が足して2ベキになるとき、何か他の特徴がないか？
- 頻度表を作れば10^7ぐらいでできるか
- グラフができた後でのペア最大化はどうやる？
- 同じ値の頂点がありうる
- 1,1,3とか二部グラフではない
- あ、被覆とかそういう系？
- ググる
- 二部グラフの最大マッチングが有名だが、一般のグラフでも多項式時間アルゴリズムがあるらしい
- でもO(N^4)だな…
- 2ベキ可能グラフに参加できる頂点の数の上限が言えるかな
- 連結でないものは刻んでいいしね
- あ、ダメだ、「全部1」とかがあるのか
- 2ベキな数たとえば8が3つある場合、自分自身とのペア8-8があり得る
- こういう辺は先に取り除いてもいいのかな
- ダメだな、8,8,24,56の時8-8を作らない方が個数が多い
- 同じ頂点が何度も使えるし自己辺あるので一般マッチングだと思わない方が良さそう
- これは多分位数1の点から取っていくのが最適なのだろう
- 位数1の点が存在しないことがある？あるか、1が4つあるケースね。
- 「自分も含めて、ペアになる点が一つしかない点」とするべき
- ある数xが別の数$2^a-x, 2^b-x$とペアになる時(a<b)
- $(2^a-x) + (2^b-x) = 2^a+2^b-2x = (2^{b-a} + 1)(2^a) - 2x$
- これがペアになる時は2x=2^aだと結論するのは飛躍があるか？
- xが奇数の時、ペアになる値も奇数、偶数の時はペアになる値も偶数、なので奇数になるまで2で割ってxが奇数の場合について考える
- 右辺を2で割ると$(2^{b-a} + 1)(2^{a-1}) - x$
- a>1についてこれは奇数になる
- 2^cを2で割ったものとして許される奇数は1だけ
- うーん
- 公式解説
- 問題分割