競技プログラミングをする上での予備知識

Latest Author yuki2006yuki2006 /Date 2018-02-26 02:36:48 / Views 13624
1 (Favした一覧ページはユーザーページから)

競技プログラミングをする上での予備知識

管理者が、勉強会などで実際に感じた、初めて競技プログラミングをする上での予備知識、ハードルなどをまとめてます。
競技プログラミングするときに挫折される方を減らして、競技プログラミング人口を増やすのが目的です。
登録をする(重要)
TopCoderなどでコンテストに参加するためには5分前までには登録をしないと参加できません。意外と忘れやすいです。
AtCoderでは、時間過ぎてからの参加も大丈夫のようです。
制約に書かれている値は、そういう入力が来ることが保証されている(それ以外はこない)
実際によくあったのは、入力を受け取る際に制約範囲外のチェックをしていたり、「範囲外の値の時はどうすればいいですか?」と質問されたりしました。
もちろん、チェックのコードが合っても問題無いです(そもそもこないので)。範囲外の値は来ませんが、万が一来たら、運営側の問題なので文句言っていいです。
入力は標準入力で
TopCoderなどを除き、基本的に標準入力で与えられます。実行引数ではないことに注意。標準入力の扱い方を知らなかった方はこれを機に覚えましょう
答え以外の出力しない
TopCoderなどを除き、答えは標準出力に出力しますが。答え以外の出力をするのは誤りになります。 (例
        //ans=の出力が余計
        printf("ans=%s",ans);

経験者でもよくあるミスはデバッグするために出力していることがあります。標準エラー出力は基本的に出力しても大丈夫なので、なるべくこちらでデバッグしましょう。
標準機能で使えるものなら、何を使っても良い
関数を作ることはもちろん、言語で準備されている関数・クラスなら使っても良いです。
よくあったのは、「正規表現を使ってもいいとは知らなかった」、「全部自力でしないといけないと思ってた」などありました。
ソースは1ファイルで
ソースを提出し、ジャッジされる系のコンテストは、1ソースファイル内に書く必要があリます。特にJava等、モジュールを別ファイルしている方などは、1ファイルにまとめるしかないようです。
コードは事前に準備してもよい
特にWebサイト上のコンテストはフルスクラッチでなくても、事前に使いそうな関数、クラスを作っても良いです。競技プログラミング経験者は、事前に準備されている方も多いです。
コンテストによっては違うかもしれませんので注意。
最適解を求める必要はない
初めはよく思いがちですが、問題の最適解を求める必要はないです。制約内に解けるプログラムであればよいです。(AtCoderで言うと部分点を狙いに行きましょう)
解法を考える際に「なにかうまい方法はないかなぁ」、「この考えは最適じゃないから違うかも」と思いがちですが、制約を見て計算量を見積もってみれば、実はそんなに難しくないかもしれません。
なので、「制約を見る」、「計算量を見積ること」は、結構重要です。最適解は強くなってから、また考えてみましょう。
フェイクに気をつける
「問題文に書かれている」、「入力に与えられている」、「制約が大きそう」、「サンプルの説明」などでも、よく考えて見れば実際に使わない、考慮する必要はないことがあります。
特に「サンプルの説明」はフェイクになりがちです。「サンプルの説明」に誘導されて筋が悪い方針を考えてしまうかもしれません。問題によっては回答者に優しくない場合があり、作問者はフェイクチャンスと言わんばかりにフェイクを入れることがあります。サンプルの説明は程々に見るようにしましょう
競技プログラミングはそういう世界の問題なので仕方ないです。気づけるようになれたらいいですね。
出力ベースに考える
出力をするものをよく考えれば、少し簡単になるかもしれません。
問題文には色々書いてあっても、「最終的に○○した出力すれば良い。(例、 1000000007で割った余りを出力すれば良い等)」
すれば良いというのは、言ってしまえば競技プログラミング特有のフェイクで、○○を求めるためのテクニックを要する事が多いです。
解の具体例を考えがちですが、解の数などだけで良い場合が多く、具体的は置いといて数え上げるという考えも必要です。
逆に○○しない答えは、かなり難しいことが多いです。
よくあるのは、「1000000007(素数)で割った余りを求めよ」、「下8桁で良い」、「奇数か偶数かで良い」
ACが正義です。
トリッキーなやり方、黒魔術なコードだとしてもACが出れば正義です。
テストケースが弱かっただけでも、ACなら正義です。ただしyukicoderの場合、そういうコード見つけ次第テストケースを追加し、リジャッジします。