CodeChef December Challenge 2017の解説と感想 - はまやんはまやんはまやん

この記事は解説 Advent Calendar 2017の12日目の記事です。

CodeChef December Challenge 2017

CodeChefは月1でLong Challengeという大会をやっている
- 期間は10日間ぐらい
- 10問出題され、うち1問はマラソン問題
- 難易度順にはなっていないが、解いた人数でソートされるため、時間が経つと難易度順になっていく
- 部分点が沢山ある

以下解説と感想 (題名横は「AC数/総人数」である)

A : Chef And his Cake（4650/5539）
- 問題文と解説
- 最初はやはり簡単だろうという予想で全探索から考えていくと、解法が作れる
B : Penalty Shoot-out（3573/5539）
- 問題文と解説
- CodeChefでよくあるややこしい問題から繰り出される注意力実装
- ReadForcesは良くない
- 3500人解いてる問題はやるだけ
C : Total Diamonds（2351/5539）
- 問題文と解説
- 個人的には2000人以上も解けているのに驚いている
- ダイアの個数の求め方が特殊なので、ダイアの個数をそこそこ簡単に求められて、全探索できそうな部分が無いか探した
- すると部屋番号は[2,N*2]なので、部屋番号を全探索しながら、ダイアの総数を数え上げていった
- 難しくない？
D : Chef and Hamming Distance of arrays（2342/5539）
- 問題文と解説
- 2000人以上が解けている問題は難しく考えないように心がけるといい
- 「同じ数が3つ以上現れない」という不自然な制約があるので、ここから考えると必勝法のようなものが発見できる
- 最適戦略を探すのが本質な問題
E : Chef And Easy Xor Queries（637/5539）
- 問題文と解説
- この辺から厳しくなってくるが、CodeChefはデータ構造で殴らせる問題が多い（イメージ）
- 解いてる人数が500人くらいの問題は典型的な難しいデータ構造やアルゴリズムを要求してくるイメージ
- クエリ2がややこしいので問題の言い換えを考えてみると、以下にも平方分割でやってきたようなクエリになる
- ややこしいクエリは問題の言い換えを考えてみよう
F : Chef and Universe（634/5539）
- 問題文と解説
- ダイクストラっぽい感じもあるが、その方面で考えると解けない
- 解けない方針を捨てるのは勇気がいるが、Long Challengeは時間だけはある
- なんとなく単調性や凸グラフが見えそうな感じがあるが、それでも解けない
- 問題の本質を導く「コスパが良いものから使う」というブレイクスルー
- こういう本質を素早く見抜く力が自分には無い（AtCoder苦手）
- （しかも最後は実験して、凹グラフと仮定して三部探索するという暴挙）
G : Red and blue points（278/5539）
- 問題文と解説
- 自分としてはこの人数帯が解けたのは嬉しい
- といっても、AtCoderで既出な傾向の問題だったので、割とすぐ思いついて解けたというのがある
- 基本は全探索からの高速化であると思い出させてくれる問題である

　
自分はここまでACして、以下はACできていない問題である

H : Santa Delivering Problem（マラソン枠）（235/5539）
- 問題概要（かなり端折っている）
  - サンタの家とN件の家がある
  - 家iには既にプレゼントA[i]が届いているが、本当はプレゼントB[i]を届ける必要がある
  - サンタは最初自分の家にいる
  - サンタが全ての家のプレゼントを正しいものに入れ替えるのにかかる時間を最小化する手順は？
- 235人は正の点数を取っている人数である
- 自分は各家と自分の家を1つずつ往復しながら正しいプレゼントに入れ替えていく愚直解法で5.585点取った
I : Chef, Leonardo And Queries（42/5539）
- 問題概要
  - N頂点の木があり、各頂点に0がある
  - 2種類のクエリをさばく
  - クエリ1 v k a b : f(0)=a,f(1)=b,f(i)=f(i-1)+f(i-2)とするとき、aからの距離がb以内の頂点にf(距離)を足す
  - クエリ2 v : 頂点vにかかれている数を答える
- 部分点15点は取った
- 類題は見つけた
- ある頂点から全方位的に数を足していくやり方が分からなかった
J : Chef and Direction（38/5539）
- 問題概要（かなり端折っている）
  - K人のコック候補がいる
  - コックiは毎秒P[i]皿作ることができ、給料はS[i]である
  - N個の注文が入ることが分かっている
  - 注文iは時間M[i]までに料理をD[i]皿用意する必要がある
  - 注文を全て満たすようにコックを適切に雇って給料を最小化せよ
- 部分点10点は取った
- 正直、あまり考えられてない

CodeChef Long Challengeは割と面白いのでみなさんも是非どうぞ！