Hatena::ブログ(Diary)

miracle cafeteria

2011-01-29

ICPCの練習方法

15:15

ICPC(国際大学対抗プログラミングコンテスト)に出たいけど、

  強くなるには何をしたら良いのか分からない、という人向け。


自分の考えでは、ICPCの競技者は以下の4段階に分かれます。

 初級者レベル:プログラミング自体を学んでいる人

 中級者レベル:基本的なアルゴリズムを学んでいる人

 上級者レベル:様々なアルゴリズムを学んでいる人

 最上級レベル:様々なアルゴリズムを自由に応用できる人


競技者レベルが異なれば、理想的な勉強の方法が異なるので、

以下では各レベルに応じた勉強方法を簡単に紹介したいと思います。


・初級者レベル

 以下のような人たちが、このレベルに該当します。

  ・プログラミングができない

  ・関数を使ったプログラムが書ける程度

 このレベルの人の勉強法

  ・プログラミング本を1冊買って、実装しつつ学習

  ・サンプルコードを書きかえて、出力を少し変えてみる

  ・分からないことはすぐに質問する

    (身近にプログラミングできる人がいると楽)

 

・中級者レベル

 以下のような人たちが、このレベルに該当します。

  ・簡単なプログラムが自由に書ける

  ・BFSやDFSというアルゴリズムを知っている

 このレベルの人の勉強法

  ・ひたすら簡単な問題を解く:目標は100問! 

  ・基本的なアルゴリズムの本を買って、勉強してみる

    (ソースコードが載っている本がおすすめ:アリ本の2章など)

  ・どうしても解けない問題は、ひとまず放置しておく

    (身近に強い人がいれば、聞いてみると良い)

 コメント:

  プログラミングができる人は、とにかく問題を解きましょう。

  たくさん問題を解くことでプログラミングに慣れ、

  バグも出にくくなるはずです。

  本で学習したアルゴリズムを使って問題が解けるようになると、

  どんどん競技プログラミングが楽しくなってくると思います。

  

・上級者レベル

 以下のような人たちが、このレベルに該当します。

  ・Union-FindやFenwick木を何も見ずに実装できる

  ・最大流問題や幾何問題を解くプログラムが書ける

 このレベルの人の学習法:

  ・ひたすら大量の問題を解く:目標は1000問!

  ・アルゴリズムが思い浮かばない問題も考え続ける

    (身近に強い人がいれば、互いに相談してみる)

  ・どうしても分からないときは解答を見て勉強し、

   次に類題が出た時には必ず解けるようにする

 コメント:

  このレベルになると、書店の簡単なアルゴリズム本では

  満足できなくなってくると思います。

  BBSやアルゴリズム紹介ページを利用して、

  様々なアルゴリズムを身につけていきましょう。


・最上級レベル

 以下のような人たちが、このレベルに該当します。

  ・各種アルゴリズムを組み合わせて問題が解ける

  ・むしろ自分でアルゴリズムが提案できる

 

 私より上のレベルの人に言えることはありません…。

 

ちなみに自分はこんな感じで勉強しました。

(初級者レベルだったころ)

 ・C言語を勉強する

 ・時間をかけて簡単な問題を解く

 ・C++言語のSTL(vectorとか)を勉強する

 ・ひたすら簡単な問題を解く

(このあたりから中級者レベル)

 ・BFSやDFSの基本的な書き方を勉強する

 ・ひたすら簡単な問題を解く

 ・ひたすら問題を解く

(このあたりから上級者レベル)

 ・分からない問題の解法を調べ、アルゴリズムを学ぶ

 ・ひたすら問題を解く

 ・ひたすら問題を解く

 ・ひたすら問題を解く

(未だに最上級レベルには達してないですが...w)

色々書きましたが、

中級者レベル以降の競技者にとって重要なことは、

"問題をとにかくたくさん解く"ということです。

初めのうちは信じられないかもしれませんが、

"解いた問題数と実力は比例する"という人もいます。

1日1問、もしくは2問解くことを毎日続けていけば、

半年後には自分でも驚くほどの実力がついていると思いますよ。

継続は力なり、、頑張ってください。