読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

CodeChef June Challenge 2016: 1問目から7問目

Devu and Array

  • 明らかに最小値と最大値の間の数しか作れない。
  • 最小値と最大値の間の数は実際に作れる。

gist.github.com

Chef and Coins Game

  • 実験すると n mod 6≠0 なら先手必勝で、そうでないなら後手必勝。
    • n mod 6≠0 からはn mod 6=0 に持ち込める
    • n mod 6=0 からは n mod 6≠0 にしかできない

gist.github.com

Chef And Binary Operation

  • 操作が分かりづらいので整理。
    • AND: 数列内に 0 がひとつでもあれば、好きな要素を 0 にできる
    • OR: 数列内に 1 がひとつでもあれば、好きな要素を 1 にできる
    • XOR: 任意の 2 要素を swap する
  • 要素が全部 0 とか全部 1 のケースを除いて、確実に構成可能。0 の個数を調整してから XOR で swap を繰り返せばいい。
  • AND, OR を適用する要素は、なるべくA[i]≠B[i] であるものがいい。

gist.github.com

Chef And The Hiring Event

  • $prod(a)=(a[n-1]+1)(a[n-2]+1)\cdots(a[0]+1)-1$。これはa[i]を選ぶ選ばないを数式になおしただけ。
  • prod が偶数なので、すべての桁は偶数。
  • 頑張る。

gist.github.com

Chef and Array K

  • 妙に簡単すぎて誤読を疑う。
  • 同じ要素に 2 回操作をすれば、異なるK,K-2,K-4,... 個の符号を反転と読み替えられる。
  • 数列に 0 があれば、異なるK,K-1,K-2,... 個の符号を反転と読み替えられる。
  • i 回操作をすると決めたとき、どの要素に操作を行うかという選択 nCi を足していけばいい。

gist.github.com

Chef and Rectangle

  • 値を増やすことしかできないので、領域内の最大値に合わせるのが最小。
  • Q≦50 なので O(QNM) が通りそう。
  • 領域の総和、領域の最大値が O(1) で計算できれば O(QNM)。
  • 領域の総和は累積和で OK。
  • 領域の最大値は sparse table で OK。メモリがちょっと怖い。
  • 二次元セグ木は多分間に合わない?

gist.github.com

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 で誤魔化す。

gist.github.com

ここまでは簡単…。