kyopro-tessoku-answers

「競技プログラミングの鉄則 ～アルゴリズムと思考力を高める 77 の技術～」(米田優峻 著, 2022/9, マイナビ出版)の問題に順に解答していきます。著者のサイトはこちらです。

概要

• 自動採点システムにACした解答から載せます。
• コーディングのスタイルは、一般的なC++のコードとして好ましいものにします。たとえば配列を固定長のグローバル変数で確保することはしない、といったことです。
• 関数が長くてユニットテストできないのは割り切ります。
• コンパイル環境はこのレポジトリのDockerfileで作成し、ルールに従ってC++17を使います。C++20は使いません。
• このレポジトリは私の練習帳なので、もっとよいコードが多数あると思います。探してみてください。
• まず全問ACすることが私の目標です。複雑な分岐をエレガントに書き換えるのはそのあとの課題です。

私の取り組み方

できるだけヒントなしで解く、という方針で臨んでいます。

1. 問題文だけ見て解ければ一番理想です。書籍の章の名前から、適用するアルゴリズムが分かることもあります。
2. 問題文を読んで解けない問題は、解説を途中まで読んで分かったら実装します。それでも解けなければ解説の続きを読みます。
3. コード例を見るのは、解説を読んでもACできないときだけです
4. テストケースが公開されていますが見ていません。WAやTLEという文字だけ見て、どう修正するか検討します。

ビルド環境を構築して起動する

docker-compose build
docker-compose up -d
docker-compose exec kyopro-tessoku-answers /bin/bash
docker-compose down

解答を実行する

コンテナ内で作業ディレクトリに移動して make すると、各問について実行可能な解答を作成します。実行可能ファイル名は、問題番号と同じです(問題A01の解答はa01)。

cd /home/work/
make -j
./a01
./b01

公開されているテストケースがあれば、それらを用いて自動採点システムではなく手元でテストできます。

1. テストケースをダウンロードし、ダウンロードした .zip を、 testcase/ 以下に展開します。例えば問題A01の 入力は testcase/A01/in/*.txt です。
2. 上記の通り、 make で実行可能な解答をビルドします。
3. 下記の通りPythonスクリプト solve.py を起動すると、問題に対応するそれぞれのテストケース *.txt に対して合否を表示します。第一引数は問題番号を接頭辞とする、実行ファイル名です(大文字と小文字は区別しません、拡張子 .exe は省略してください)。
4. 全テストに合格した場合は最後に Passed と表示します。不合格なテストがあれば Failed と表示します。一定時間(solve.pyにハードコーディングした秒数)経っても終わらないテストは強制終了して不合格とします。あるいは実行時エラーなどが起きるかもしれません。

python3 solve.py a01

実行ファイル名が a01alt のときは第一引数にそう指定すると、 a01alt を実行して問題A01をテストケース testcase/A01 を使って解きます。

python3 solve.py a01alt

自動採点システムと同様にこのsolve.py自身は、テスト結果として合格(AC)、不合格(WA, TLE, RE)であることしか出力しません。解答にdebug printfを仕込めばテストケースに対しても出力されますが、その場合は自動採点システムよりも豊富な情報を得ていることをご承知おきください。

C20を解いて得点を求める専用のスクリプトも用意しました。

python3 solve_c20.py

コード集

鉄則本を解いた後、AtCoderの問題を解いていますので、そこで使うコード集を併せて置きます。鉄則本の自動採点システムはAtCoderの常設中のコンテストです。コード集は snipetts/ 、コード集の説明はこちらです。