今から、CODE FESTIVAL の予選Bをギリギリで抜けるために

はじめに

CODE FESTIVAL 2014に参加していました。

先ほどCODE FESTIVAL 2015 予選Aが終わったようです。今年、私は本戦参加資格がないので参加していなかったのですが、去年はギリギリで予選を突破し、本戦に参加していました。本戦の順位は140位 *1 とかでしたし、競プロも初心者でしたし *2 、予選があるのを忘れていて途中から参加したのですが、突破できました。

今から予選Bにむけて実力をつけるのは無理なので...

このCODE FESTIVAL、初心者でも本戦に行けて、初心者でも楽しめる素晴らしいお祭りです。初心者の皆さんにもぜひ参加してほしいのですが、予選Bはもう1ヶ月後です。というわけで、去年、ギリギリ予選突破した経験から、「こんなところに気をつければ良いんじゃないかなー」というところをいくつか上げます。

• あくまでも去年の経験で、今年も同じように行くかはわかりません。
• 競プロテクニックではなく、あくまで予選抜けする方法です。

注意点

あくまでも去年の経験であって、

• 問題の難易度が劇的に変わる
• 予選参加者が劇的に増える

といったことがあると通用しなくなります。

内容

• 最低限必要な実力はどれくらいか
• 予選Aより予選Bの方が通りやすい
• D問題で部分点を狙いに行くのも重要
• 順位表を見るべきかどうか

予選突破のコツいくつか

最低限の実力は、ベーシックなDP

とはいえ、DP（動的計画法）が分からない！というレベルだと流石に無理です。まずはDPまで勉強して土俵に上がりましょう。チーター本（最強最速アルゴリズマー養成講座）でDPの項まで読んで理解できたら十分だと思います。 *3

最強最速アルゴリズマー養成講座 プログラミングコンテストTopCoder攻略ガイド

まだ買ってないなら買いましょう。本戦に参加したらchokudaiさんからサインをもらえます！ *4

DPまでをなんとなく理解したら、実際に解く練習をしましょう。去年のCODE FESTIVAL 予選を解くとかが良いと思います。実際に時間を測って解くとより良いです。（参考として記事の最後に問題を幾つか載せておきます）

本戦までの間は、これくらいのレベルの問題を解きましょう。これ以上のレベルの問題をやっても、身につかないまま本戦を迎えてしまいますので、本戦まではこのレベルの問題を解きまくります。

予選Bの方が通りやすい

予選Aで絶望を感じましたか？大丈夫。強い人はみんな予選Aで突破していきます。つまり、予選Bは予選Aに比べて突破しやすいということ。ギリギリ突破を狙うなら予選Bでこそ本気を出しましょう。

予選突破のボーダーを知る

予選突破の方法は2種類あると考えています。

• 全問正解する（全問正解したらまず間違いなく突破できるでしょう）
• Cまで正解してDですばやく部分点を取る

つまり、

• C問題までは頑張ってとかなければならない
• D問題に関しては状況判断が重要
  • D問題で満点解法を思いついた→確実に満点がとれそうならいきなり満点解法を実装
  • C問題までいい感じにさらさら解けた→D問題ではとりあえず部分点を取りに行き、その後満点を考える
  • C問題でつまって時間が...→D問題満点解法でワンチャンを狙う

問題の難易度は去年と変わるかもしれません。臨機応変に対応しましょう。言いたいことは、さらっと部分点を取ることはかなり重要であるということです。場合によっては、C,D両方をも部分点でも良い場合とかあるかもしれません。 適切な状況判断をしましょう。

順位表を見るかどうか

これは人による気がします。「順位表を見ると集中力が切れてしまう」「順位表を見る時間があったら問題を考えていたい」という人もいるでしょうし（自分はこっち側の人間）、「順位表を見たほうが、部分点を取りに行くかどうか、適切な状況判断ができる」のも確かですので、どちらのタイプなのか知っておくことが重要でしょう。しかし、↑のボーダーの知識を知っておくことで、必要以上に順位表を見る時間は減らせます。

まとめ

• ベーシックDPはできないと流石に無理
• 予選Bの方が通りやすい
• D問題で素早く部分点を狙いに行くのも重要
• 順位表を見るべきかどうかは人による

参考

• AtCoderで解いておいた方がいい問題
  • AtCoder Beginner Contest 最近の *5
  • CODE FESTIVAL 2014 予選A,B *6
  • CODE FESTIVAL 2014 本戦 の最初の4,5問くらい *7
  • CODE FESTIVAL 2014 あさぷろ（Easy）
  • CODE FESTIVAL 2014 チーム対抗早解きリレー のG問題くらいまで
  • CODE THANKS FESTIVAL 日程A,B のF問題くらいまで *8
• その他最近みた参考になりそうなページ
  • CODE THANKS FESTIVAL A日程に参加してきました - フツーって言うなぁ！
  • 競技プログラミングでコーディングの際気を付けていることとか - うさぎ小屋
  • Spaghetti Source - 各種アルゴリズムの C++ による実装
  • CODE FESTIVAL 2014 参加者のインタビューのページ（CODE FESTIVAL 2015のページにあった気がする）

*1:200人中。めっちゃ調子良くてこの順位

*2:今でも初心者

*3:理解できるなら蟻本でも良いですが、チーター本の方が初心者向けです

*4:自分から話しかけてもらってくださいね

*5:最近のは簡単な問題が多い

*6:去年のやつ

*7:オープンコンテストの方

*8:すいません、自分は解いてないです