CODE FESTIVAL 2018 qual B 参加記録＆解説（A～D）
CODE FESTIVAL 2018 qual B - AtCoder
前のこどふぉに出ていたので5分遅刻で参加。結果は108位でした…
A～Dを振り返ります。今回は公式解説がかなり丁寧なので、それを少し補足するような感じで短めに書きます。
A - Probability of Participation
A - Probability of Participation
解法
1以上100以下の整数のうち、 で割り切れるものは
個です。これを100から引いたものが答えです。
ACコード
（Ruby）Submission #3406469 - CODE FESTIVAL 2018 qual B
B - Tensai
解法
顔が一番面白い人に毎回トレーニングをしてもらうのが最適です。実装方法はいくつかありますが
- 字の上手さと顔の面白さのペアを顔の面白さ基準でソートし、一番顔が面白い人の字の上手さを
増加させ、スコアを計算する
- 与えられた入力のまま普通にスコアを計算したあと、
を加算する
などをすればよいです。
ACコード
（Ruby）Submission #3406640 - CODE FESTIVAL 2018 qual B
C - Special Cake for CODE FESTIVAL
C - Special Cake for CODE FESTIVAL
解法
答えは公式解説に書いてあるとおりです。ので、ちょっと思考の流れを書きます。
制約を確認すると、マスの数は最大100万になり、 X を置いてもよいマスの数はその5分の1＋ちょっとです。そのため、ある程度答えが規則的になるだろうという予想から、「ある行について、5マスごとに1個 X を置いてみる」ということを考えます。
5マスごとに X を置くと、間には X のないマスが4つあります。これら全てをカバーしなければいけません。
一番左と一番右は、その行の中で X に接しているため、既にカバーできています。残り2つは上と下に助けてもらいたいので、それぞれ上と下に置きます。このような形を作れれば、X の間の4マスが全てカバーできます。
この形を繰り返していくと、公式解説のような模様ができます。
ACコード
（Ruby）Submission #3407445 - CODE FESTIVAL 2018 qual B
D - Sushi Restaurant
解法
この記事はD問題まで書きますが、もちろんこれが4問の中ではダントツに重いです。ただこの問題も公式解説が丁寧です。そちらで丁寧に説明されていることはこの記事では端折っていきます。
「 
番目に空腹度が小さい人」に着目する
参加者の空腹度が確率で決まったあと、与えられた寿司がどのように割り振られるか考えます。このとき、1番空腹度が小さい人は1番寿司が少ない皿を、2番目に空腹度が小さい人は2番目に寿司が少ない皿を…というふうに寿司が割り振られます。
このため、「 番目に寿司が少ない皿（つまり、
番目に空腹度が小さい人が取る皿）は、寿司をいくつにするのが最適か？」ということを、各皿ごとに独立に考えることができます。ということで、「
番目に空腹度が小さい人」の空腹度がどのような分布になっているかを知りたくなります。
もしこの確率分布が求められている場合、最適な寿司の数はいくつになるでしょうか。ここで、「絶対値で定義された誤差の合計を最小にするのは、分布の中央値である」という知識が使えます。これは少し前のABC/ARCでも登場した知識です。以前の問題のように確率の概念がない場合は小さい方から数えて 個目の要素を採用していましたが、今回のようにそれぞれの要素に確率が付いている場合も似たように考えることができて、「確率の累積値が
であるところの要素」が中央値となります。
この値は空腹度の候補 のうちどれかになっているので、もちろん整数です。そのまま寿司の個数として採用することができます。
確率分布を求める
今までの話で、「 番目に空腹度が小さい人」の空腹度の分布が求められれば答えが求められる、ということが分かりました。次はこの確率分布を求めます。
番目に空腹度が小さい人の空腹度が、
番目に小さい候補である
となる確率を考えてみます。なんとなく「この人より空腹度が小さい人が
人、空腹度が大きい人が
人いて…」みたいなことを考えたくなりますが、こうすると空腹度
の人が複数人いたときに困ります。
もう一つ「空腹度 の人が全部で
人いるときの…」という条件を付け足し、
を全探索すれば確率が求められないことはないです。ただこうすると、
のループで
の計算が必要で間に合いません。
このようなときに使える手段が、「 番目に空腹度が小さい人の空腹度が
以上となる確率」を考えることです。これが求められれば、順次差分を取ることで目的の確率分布が求められます。
そしてこの値は、「ぴったり」を求めるよりも求めやすいです。具体的には、 より小さい空腹度を持つ人の人数が
人のどれかである確率を求めることになります。これも結局全探索のオーダーが1つ増えそうに見えますが…
以上となる：
人のどれかである
番目に空腹度が小さい人の空腹度が
人のどれかである
こうして並べてみると、「 番目」のときの結果に要素を1つ足すだけで「
番目」の結果になり、差分更新で求めることができるのです。
あとは要素1つが現実的な時間で求められればよいです。「 より小さい空腹度を持つ人の人数が
人である」という確率は、
より小さい空腹度になる確率を
として
と求められます。コンビネーションは前計算、 も各
が出る確率
の累積和なので前計算。累乗の部分は繰り返し二乗法で
に落ちるので、十分現実的な時間で求められます。
解法まとめ
ということで、まとめです。
の累積和およびコンビネーションを前計算しておく。
- 前計算の値と差分更新のテクニックを利用して、「
- この確率分布の中央値を求めて、各皿ごとに最適な寿司の数を決め、答えを計算する。
ACコード
Submission #3410686 - CODE FESTIVAL 2018 qual B
誤差がかなり積もってしまうので、double よりも精度の高い long double を用いました。精度が良い分、計算時間とメモリの占有量は大きくなるのですが、この問題の場合はどちらも余裕があるので大丈夫でした。
公式解説では対数に変換して計算する方法が紹介されています。対数にすると累乗が掛け算になるので、それで が計算量に付いていないのだと思います…たぶん。
さいごに
D, Eは全体的にAC者がものすごく少なかったですね。私も通せませんでしたが、Dはしっかり復習できたと思います。Eも理解しなければ…
