AGC029B
https://gyazo.com/080d6b0ddcfd467e67ccc6894b6b8155
考えたこと
和が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だけ
うーん
公式解説
「位数1の点から取っていく」この方針はよい
これを効率的に見つけ出す方法を発見できなかった
この問題条件では最大の値の頂点は1つしかペアになる値を持たないことが肝
問題分割