競プロ初心者だった頃の注意すべき点を列挙する 1
背景
ここ最近になって競プロを始めて、毎週プログラミングコンテストに参加する人が増えていると感じます。*1
特に日本語で提供される初心者向けコンテスト AtCoder Beginner Contest (ABC) に参加する人が多いです。各ABCに対して解説pdfと配信動画が公式に用意されていますが、実装で苦戦している人が多いように思えます。
今回の一連の記事では、無意識にやっているようなレベルの実装上のテクニックをあぶりだす為に、自分が競プロを始めた頃の提出コード*2をもとに難所を列挙していきます。ここでの対象読者層は、1問でも解いた人からAtCoder上での緑色くらいまでを想定しています。
以下の記事よりもかなり細かいレベルで書いていきます。
初心者向けのABCの問題傾向とその対策 - ヘクトのメモ
この記事の要約
競プロ初心者かつコンテストパフォーマンスを上げたい人への典型tips集
実装の前に
このセクションは実装の話ではなく、本当の初心者の頃に少しでも高いコンテストパフォーマンスを出すために役立つことです。*3
自分のPC上で書いたプログラムがとにかく実行できることを確認する
まず、提出履歴を最初から振り返ると、C言語を使っておりコンパイルエラー (CE)をたくさん出していた。AtCoderではCEはペナルティではありません。しかし、CEになるのはC, C++, Javaなどのコンパイルが必要な言語だけです。
Pythonなどのコンパイルを必要としない言語では、プログラムが実行できないときには実行時エラー (RE)という扱いになりペナルティが加算されます。というわけで、提出する前に実行できるかを確認するだけで不必要なペナルティを減らせます。
サンプルケースを必ず試す
サンプルケースは公式に与えられている手がかりなので活用しましょう。特に入出力のフォーマットを満たしているかは確認すべきです。
AOJでは、正答を出力しているがその形式のみを間違えると、プレゼンテーションエラー (PE) と呼ばれる誤答 (WA)になります。
コンテスト中にコードを何度も書き換えていると、サンプルケースを試すのが面倒になる気持ちになります。小さな変更だったら実行できることを確認したら提出してしまうとかやりがちでしょう。*4 ただ、その小さな変更がプログラムの出力に大きく影響することはよくあって、サンプルケースを試せば不必要なWAを減らせます。
このトピックについて、AtCoder上でのtipがあります。AtCoderではコンテスト中のテストケースはスクランブルされていますが、実はサンプルテストケースは必ず一番上に来ます。テストケースのステータスを見て、AC, AC, WA, AC, AC, AC, WA, WA, ...... とかだったらサンプルテストケースで落ちているということが分かります。
コーディングしやすいエディタを用意して、インデントを整える
始めた頃はメモ帳とかでコーディングしていましたが、流石にそれは辛かった。インデントも崩れているので、大分読みにくいです。コードを読みやすく整理すると、バグを見つける時にかかる時間が短くなります。コンテストにおいては素早くコーディングするために、環境を整えることも重要な要素です。たまにメモ帳で競プロする人がいますが、このようなエディタを導入するだけでレートが上がると思います。
(2019/02/09 追記) 紙に書いて試行錯誤する
chokudai(高橋 直大)🍆🍡 on Twitter: "【アンケート】競技プログラミングをする際に、紙とペンなどの筆記用具を利用していますか?"
問題文を言い換えたり、サンプルテストケースを手で試したり、細かい実装の整理に役立ちます。
また、コンテスト中の思考の過程を可視化できる。
自分の場合はそもそも紙がないと600点以上の問題を解くのは正直辛いです。
最後に
実装の話に入る前にこんなに書くとは思っていなかったので、この記事はもう少し続くと思います。