猫でもわかるWebプログラミングと副業

本業エンジニアリングマネージャー。副業Webエンジニア。Web開発のヒントや、副業、日常生活のことを書きます。

今から、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

まだ買ってないなら買いましょう。本戦に参加したら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問題で素早く部分点を狙いに行くのも重要
  • 順位表を見るべきかどうかは人による

参考

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

*2:今でも初心者

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

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

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

*6:去年のやつ

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

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