ABC117
36分5ペナで全完です(Unratedだからって提出デバッグしてはダメ)
世界Bと世界Aでの経過時間の比はX*t:tで,X*t=TとなるX,Tが与えられるのでtについて解きましょう.
定理が与えられているので辺の長さの合計をS,最長の辺の長さをLmaxとしたとき
S-Lmax>Lmaxかどうかを確認しましょう.
これ証明なしで解いてしまいました・・・.
最初に駒を置く場所は自由なのでN箇所までは移動なしで埋まるため,残りのN-M箇所をなるべく動く量を減らして移動したいです.
よって隣接する目標地点との座標の差を持つ数列aを作ったときにaの小さいほうからN-M個の合計を取ったものが答えとなります.
(追記)貪欲嘘らしいので話半分に読んでください・・・
(追追記) これだけ最上位桁以外を取る時で落ちるので最上位桁を取らない場合でも貪欲を試しましょう.(最上位桁を取らなければ他の全パターンを考慮して貪欲できるため)
こういうのは上から決めたいって過去問で見ました.
Kの値を超えないように上からビットを検討していきます.(上のビットの方が数字が大きく,答えに与える影響が大きいため)
各A[i]とXORをとった和を最大化したいのでXのjビット目を1にするべきかはA[i]&(1<<j)の数が半分未満であるかどうかで判別できます.ちょうど半分のときは検討するビットをなるべく増やすために含みません.
