この記事は解説 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）
- F : Chef and Universe（634/5539）
- G : Red and blue points（278/5539）
自分はここまで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は割と面白いのでみなさんも是非どうぞ！
