読者です 読者をやめる 読者になる 読者になる

kyos1704活動記

適当に考えたことや調べたことを垂れ流すものです。質問等ありましたらtwitter:@kyos1704 に質問してください。

競技プログラミングの勉強方針について

新入生についてはともかくやる気とかモチベーションは十分だという人が実力を上げるにはどうすればいいかという話


競技プログラミングにおいて何を目的にするかという点が最も大事だと思う

チームとかでの視点ではいい記事があるのでこっち見たほうがいいかも
http://topcoder.g.hatena.ne.jp/iwiwi/20120608/1339162885

個々人がどうするか的な視点でみる

ここではICPCを目的にしているものとして考える


ICPCでは、ACしている問題数が一番のファクターであるので
時間内に解ける問題数が増えることが目的となる

ボトルネックとなりうるのは2種類あって
・時間的制約
・知識的制約
が考えられます。(おそらく一般的にこれは言える気がします

以下では国内予選突破程度を目的としている人を対象とします
(要するに私です)

国内予選突破は4完したらできるものとします。
(A~Dを解きたい)


・知識的制約に関して
AB問題に関して言うと、必要ないっぽいので割愛します
知識が必要な問題に限定すると
C問題はDP、D問題はグラフ系統の問題がよく出ます。(ホンマカ
要するにその辺りの知識が全くない場合、B問題まで解いてACをもらったあとに
頭を抱える事になってしまいます。
知識がない場合は座っているだけになってしまうことが考えられるので、
勉強できるならしてしまいましょう。
(過去問を信じるならDまでで必要な知識はそこまで多くない)

このことを一般化すると、勉強しましょう(あっ



・時間的制約に関して
ABCDどの問題であれ、問題を解くために必要な時間は
・・アルゴリズムを考える時間
・・実装する時間
・・バグを潰す時間
の3つが存在します(もっとあるかもしれないけどとりあえず無視
多分これICPCとか関係無い気がするけどまあいいか

ICPCではPCを使える時間が限られているため、
アルゴリズムを考える時間を短縮することはさしあたって考えないとすると
(アルゴリズム考える時間短縮ってどうすりゃいいんだろう、だれか教えて)
実装してバグを潰す時間をできるだけ短縮することが目的となります。

この場合どのような手段で短縮化できるかを考えます

・・実装する時間の短縮
・・・書いてる間に迷わない(考えない)ですむようにする
・・・タイプ数を減らす
考えなくてすむようにするには、先に変数の名前を考えておくとか(いつも同じ変数を使うとか)
関数を小分けにして、一個一個を簡単にしておくとか

タイプ数は変数名ぐらいしかないかなぁ?

・・バグを潰す時間の短縮
・・・バグらせない
・・・バグを特定しやすくしておく

やっぱ関数わけるとかしか思いつかない
あとはバグりやすい実装方法しか思いつかないときは、
練習のうちに他の人のコードを読んでバグらなさそうな
わかりやすい書き方を考えてみるとかしておくとよい
どうしようもないときはその書き方を何回もやって慣れておく

特定しやすくするには、バグの内容が予想できる場合には
バグ検知のテストケースとか作っておく