CodeChef June Challenge 2016: 1問目から7問目
Devu and Array
- 明らかに最小値と最大値の間の数しか作れない。
- 最小値と最大値の間の数は実際に作れる。
Chef and Coins Game
- 実験すると n mod 6≠0 なら先手必勝で、そうでないなら後手必勝。
- n mod 6≠0 からはn mod 6=0 に持ち込める
- n mod 6=0 からは n mod 6≠0 にしかできない
Chef And Binary Operation
- 操作が分かりづらいので整理。
- AND: 数列内に 0 がひとつでもあれば、好きな要素を 0 にできる
- OR: 数列内に 1 がひとつでもあれば、好きな要素を 1 にできる
- XOR: 任意の 2 要素を swap する
- 要素が全部 0 とか全部 1 のケースを除いて、確実に構成可能。0 の個数を調整してから XOR で swap を繰り返せばいい。
- AND, OR を適用する要素は、なるべくA[i]≠B[i] であるものがいい。
Chef And The Hiring Event
- $prod(a)=(a[n-1]+1)(a[n-2]+1)\cdots(a[0]+1)-1$。これはa[i]を選ぶ選ばないを数式になおしただけ。
- prod が偶数なので、すべての桁は偶数。
- 頑張る。
Chef and Array K
- 妙に簡単すぎて誤読を疑う。
- 同じ要素に 2 回操作をすれば、異なるK,K-2,K-4,... 個の符号を反転と読み替えられる。
- 数列に 0 があれば、異なるK,K-1,K-2,... 個の符号を反転と読み替えられる。
- i 回操作をすると決めたとき、どの要素に操作を行うかという選択 nCi を足していけばいい。
Chef and Rectangle
- 値を増やすことしかできないので、領域内の最大値に合わせるのが最小。
- Q≦50 なので O(QNM) が通りそう。
- 領域の総和、領域の最大値が O(1) で計算できれば O(QNM)。
- 領域の総和は累積和で OK。
- 領域の最大値は sparse table で OK。メモリがちょっと怖い。
- 二次元セグ木は多分間に合わない?
Chef and cities
- A[i] に変更を掛けたとき影響を受けるクエリは A[i] の約数のみ。
- 105 以下の約数の個数の最大値は 128。
- R=1,...,N の結果を配列に保存しておけばいい。
- 約数列挙はエラトステネスの篩っぽくやれば O(n log n)。
- xを整数、yを1未満の実数として、N=10x+yと表現できるなら、Nの最上位桁は10yの整数部分。
- 誤差で死ぬっぽいので eps で誤魔化す。
ここまでは簡単…。