CodeChef December Challenge 2018 参加日記
ひさびさのロングチャレンジは2完で460位/786人(Div1)。Div1は問題が難しすぎて楽しくない…。
ある電子パネルは、xボルト以上の電源につなぐと壊れてしまう。1000コイン与えられるので、次の2オペレーションを使ってxを特定せよ。
・yボルトの電源につなぐ（1コイン）
・壊れたパネルを治す（cコイン）
1 <= x <= 150,000
1 <= c <= 150
二分探索をするだけだが、素直に[l,r)の中央を取っていくと、cが大きい場合に修理費が嵩みコインが足りなくなる。中央ではなく、l+(r-l)/4などの下限に近い値を使えば問題ない。
https://www.codechef.com/viewsolution/21784719
隠れた整数列[a1, a2, ... an]がある。XOR(ai, aj, ak)を何度か問い合わせることで、要素すべての値を確定させよ。ただし、各Indexに対して、3回までしか問い合わせは実行できない。
8 <= n <= 5 x 10^4
要素1からイテレートしていく。
残り要素数が4または8以上のとき、
one = a[i] ^ a[i+1] ^ a[i+2]
two = a[i+1] ^ a[i+2] ^ a[i+3]
three = a[i] ^ a[i+1] ^ a[i+2]
four = a[i] ^ a[i+2] ^ a[i+3]
を取得し、
a[i] = one ^ three ^ four
a[i+1] = one ^ two ^ three
a[i + 2] = one ^ two ^ four
a[i + 3] = two ^ three ^ four
を得ることができる。
残り要素数が5,6,7の場合も同様にパターンを見つけ出す。特に残り7の場合は手作業では難く、別にスクリプトを書いて導出した。
https://www.codechef.com/viewsolution/21865422
無向グラフを、すべての頂点の入次数が偶数になるように有向グラフ化せよ。
・1 <= N(頂点数), M(辺数) <= 10^5
・グラフは連結している
・重複辺や自己ループは存在しない
まず自明なこととして、条件を満たす有向グラフを作るのは、辺が奇数のときは不可能、辺が偶数のときは必ず可能である。また、もし木であれば、葉からどんどん消していけばよいので簡単である（葉Aからその親B、Bの親からBに方向づける）。
よって、次のようにグラフを木に変換してしまえばよい。
・適当な全域木をつくる
・この木で使われなかった辺を、ダミーノード（葉）を作って繋げてしまう
（実装は省略）
言われてしまえば簡単な問題で、これが解けなかったのは悔しい。
