yukicoder contest 417 感想
- はじめに
- A - Fee Schedule（★1）
- B - Dam（★2）
- C - Room Allocation（★2.5）
- D - Prediction by Average（★2.5）
- E - Bonus Ai（★3）
- F - Similar But Different Name（★3.5）
- G - Unnatural Pitch（★3.5→コンテスト終了後に★4に変更）
- おわりに
はじめに
皆さん，コンテストお疲れ様でした．はちじです．この度，四度目となる単独コンテストを開催しましたので，その感想を述べていきたいと思います．
A - Fee Schedule（★1）
- AC人数：131人
- First AC：hitonanode さん（0:20）
最初の問題です．例によって，コンテストの最初の問題は，★1，それも ABC-A レベルの問題を置きました．
予想はできていたことですが，最初の1～2分にACが集中していました．
B - Dam（★2）
- AC人数：110人
- First AC：hitonanode さん（3:09）
仕組みが単純で考察もしやすく，しかし注意しないと間違える数学の問題です．
周期性という，よくある考察を題材としています．これをもとに，グラフの形をイメージできれば，正解にぐっと近づくでしょう．
WAが大量に出るかなと思っていましたが，そんなことはありませんでした．上位陣は何の迷いもなく通すのだと思うと，処理力の高さを思い知らされます．
C - Room Allocation（★2.5）
- AC人数：90人
- First AC：hitonanode さん（6:39）
少しの考察要素あり，しかしそれでいて問題の構造をよく観察すれば正解に一気に近づくタイプの問題です．
このタイプの問題は過去に ABC でよく出ていた時代もあったものですが，最近ではあまり見なくなってしまったと思っています．
正解数が思った以上に多かったです．こういうのはやはり正しく処理できる人が多いのでしょうか．
D - Prediction by Average（★2.5）
- AC人数：62人
- First AC：maspy さん（10:47）
平均値を題材とした問題を作りたいと思っていたら生えたので，出題してみることにしました．
平均値が人数に応じてどのような挙動をするか考えれば，正解には辿り着きやすかったかと思います．なお，制約の「 」は「N × S を（S を 1000 倍して整数型に直したもとで）オーバーフローせずに計算できる範囲」という理由だけで定められたものであり，言ってしまえばただのブラフです．
当初はこれが★2で，しかも C 問題に置かれる予定であったのですが，各問テスターさんの指摘によって★2.5に引き上げられ，また全体テスターさんのご意見によって現在の C 問題と順番が入れ替えられることとなりました．正解者は思ったより少なく，またそうでなくても正解までに時間がかかっていた人も多いように見受けられ，個人的には意外でした．
E - Bonus Ai（★3）
- AC人数：70人
- First AC：hos.lyric さん（4:25）
かなりオーソドックスな数え上げの問題です．DP で数え上げを行う，という方針は制約を見ても立てやすいかもしれませんが，どのように遷移させていくか，という点が腕の見せ所です．また，DP の高速化を累積和やいもす法で行う必要もあり，それなりの典型力も同様に必要とされます．
各問テスターさんから， で解ける解法を提案していただきました（経路数の数え上げに帰着させる，というもの）．しかし，遷移の部分が本質であると考え，今回は導入しないことにしました．
正解数は思った以上に多かったです．
F - Similar But Different Name（★3.5）
- AC人数：39人
- First AC：hos.lyric さん（14:00）
ABC などでしばしば登場するような，文字列照合の問題です．文字列を良い感じの性質を満たすハッシュ値に置き換え，そのハッシュ値のもとで畳み込みを行うことでスコアを高速に計算する，という流れを踏む必要があり，非常に高い知識・考察力が要求されます．
当初はこれが G 問題で，また難易度も★4に設定されていたのですが，各問テスターさんから「解法に辿り着くまでのアプローチが様々ある*1」というご指摘を頂き，難易度を★3.5に下方修正しました．また，全体テスターさんもこの問題は早い段階で通されており，「F 問題と G 問題の順序を逆にすべき」とのご指摘を頂いたため，この問題が F 問題に置かれることとなりました．
実際この問題の正解数はかなり多く，逆にして本当に良かったです．
G - Unnatural Pitch（★3.5→コンテスト終了後に★4に変更）
- AC人数：8人
- First AC：maksim さん（30:47）
前回，前々回と最後に数え上げの問題を置く回が続きましたが，今回の最後の問題は最適化です．最適化の問題を考えていたところ，この問題が生え，「気づき」が重要な問題として良いと感じたため，出題を決めました．
「端より真ん中でそろえたほうが良い」ということは，直観として比較的働きやすいかと考えていますが，それを「どのように評価できるか」に気づけるかどうかが，ポイントだと考えています．これに気づけるか気づけないかで，正しい解法に辿り着けるかが大きく変わってきます．
AC数8人は完全に予想外，また想定解と同じ解法だったのは，見た限り ygussany さんのみに思われました（他はセグ木や遅延セグ木が多い）．想定解はかなり綺麗な形になるので，ぜひ考えてみてください（セグ木も遅延セグ木もいりませんが，それでも実装はやや面倒かもしれません）．
おわりに
前々回は全体的に易しめ，前回は後半が難しめのコンテストだったため，今回はその中間くらいの，易しすぎず難しすぎずの難易度を心掛けたつもりでした．しかし，最終問題の正解者数が私の作成した問題の中で過去最低になってしまったのが予想外でした......．
また，今回はコンテスト終了後に解説風の動画を作成しています（yukicoder contest 417 にゆっくりが挑戦する【ゆっくり茶番・ゆっくり解説】 - YouTube）．動画は視覚的に問題の解法を表現するのに非常に便利な媒体であり，個人的に競プロの解説には非常に適していると考えているのですが，現状ではこれを実践している例はあまり多くないです*2．そこで，今回は新たな試みとして，動画も作ってみることにしました．競プロ動画の方式は様々あり，多くの動画投稿者さんが十人十色のスタイルで行っているのですが，その中でも私が好きで作ってみたかった，「ゆっくり茶番」スタイルを，今回は取り入れてみることにしました．
さて，私はかねてからとあるオンサイトコンテストの運営に携わっていることを，各所において明かしています．その報告ができる日も，もうだいぶ近いかもしれません．
