競技プログラミングこと始め

Abstract

  プログラミングコンテストでは，プログラミングの様々な技能を競い合う．その中で，競技プログラミングでは，出題された同一の問題を，より早く正確にコーディングする技能を競う．
  当然だが，競技プログラミングでは値の入出力を行う必要がある．しかしながら，全く対策をしないと，そもそも普段 sprintf() を使わないから挙動が分からない，といった事態に陥る．この最悪の事態を回避するため，これら基本的な操作と，競技プログラム特有の簡略化表現についてのテンプレートを作成する．また，コンテストの過去問やその答案を学習する．

Introduction

  競技プログラミングを始めるにあたり，まず，競技プログラミング用のテンプレートを作成する． その後，実際に過去のコンテストで出題された問題，POJ 2386 Lake Counting [5] の実装を行う．

Method

  競技プログラミング用のテンプレート作成にあたり，[1]~[4] を参考にして実装を行った．

Implementation

  POJ 2386 Lake Counting [5] の実装にあたり，[9] を参考に実装を行った．また，[9] で省略された箇所について，[6]~[8] を参考にした．下記に，実装したコードを示す．

./POJ-2386.cpp

Results

  下記に POJ-2386.cpp の実行結果を示す．

$ make

mkdir -p make_temp/;\
g++ POJ-2386.cpp -MM -std=gnu++0x        -Wall -O3\
| sed 's/POJ-2386\.o/make_temp\/POJ-2386.o make_temp\/POJ-2386.d/' > make_temp/POJ-2386.d;\
[ -s make_temp/POJ-2386.d ] || rm -f make_temp/POJ-2386.d

mkdir -p make_temp/;\
g++ POJ-2386.cpp -c -o make_temp/POJ-2386.o -std=gnu++0x         -Wall -O3

============================================================

SRCS:
POJ-2386.cpp

OBJS:
make_temp/POJ-2386.o

CFLAGS:
-std=gnu++0x     -Wall -O3

============================================================

g++ -o exe make_temp/POJ-2386.o -std=gnu++0x     -Wall -O3


$ ./exe.exe
main(510): N: 10, M: 12
MatX =
W        .       .       .       .       .       .       .       .       W       W       .
.        W       W       W       .       .       .       .       .       W       W       W
.        .       .       .       W       W       .       .       .       W       W       .
.        .       .       .       .       .       .       .       .       W       W       .
.        .       .       .       .       .       .       .       .       W       .       .
.        .       W       .       .       .       .       .       .       W       .       .
.        W       .       W       .       .       .       .       .       W       W       .
W        .       W       .       W       .       .       .       .       .       W       .
.        W       .       W       .       .       .       .       .       .       W       .
.        .       W       .       .       .       .       .       .       .       W       .
MatX =
.        .       .       .       .       .       .       .       .       .       .       .
.        .       .       .       .       .       .       .       .       .       .       .
.        .       .       .       .       .       .       .       .       .       .       .
.        .       .       .       .       .       .       .       .       .       .       .
.        .       .       .       .       .       .       .       .       .       .       .
.        .       .       .       .       .       .       .       .       .       .       .
.        .       .       .       .       .       .       .       .       .       .       .
.        .       .       .       .       .       .       .       .       .       .       .
.        .       .       .       .       .       .       .       .       .       .       .
.        .       .       .       .       .       .       .       .       .       .       .
result: 3
--------------------------------
 Execution time:     0. 004 sec
--------------------------------

Discussion

  いろいろと趣向を凝らした結果，誰の参考にもならないソースコードとなったことを反省したい．意外だったのは，sprintf() で読み込みを行う場合，通常改行コードを意識する必要はないことである． (ただし，今回の場合は，趣向を凝らした結果，改行を意識せざるを得なくなってしまった．) 参考文献として掲げたコード [6]~[9] を見ると，非常に簡潔で，見通しがよい． また， 通常プログラムを書く際は，必要十分なメモリを確保しようと考えるが， こと競技プログラミングにおいては，(メモリ制限を満たす限り) この考えは不要であると思われる． 競技プログラミングでは， 問題に，より簡潔で見通しがよく， 必要応じて高速なコーディングが求められるように思う． 今後，競技プログラミングに触れる際は， この点を意識して活動したい．
  また，for の define 置換 FOR を unsigned int で用意したため，不都合が生じ使用できていない．int に直すとよいと思われる．

Conclusion

■ [1]~[4] を参考に，競技プログラミング用のテンプレートを作成した．
■ 実際に過去のコンテストで出題された問題 (POJ 2386 Lake Counting) を，[5]~[9] を参考に実装した．

References

[1] AtCoder - 過去のコンテスト
[2] github.com/admiswalker/SubStandardLibrary
[3] ADMIS_Walker の ぶろぐ - C++ で MatB(':', 0) = MatA(':', 0); を実装する
[4] ADMIS_Walker の ぶろぐ - 汎用 Makefile の書き方
[5] Lake Counting
[6] math, programming, and little something to laugh - POJ 2386 Lake Counting
[7] liqz - POJ 2386 Lake Counting
[8] プログラミングコンテストの記録 POJ 2386 - Lake Counting
[9] プログラミングコンテストチャレンジブック [第2版] page.35~36 Lake Counting (POJ No.2386)

プログラミングコンテストチャレンジブック [第2版]
～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～
著者: 秋葉拓哉, 岩田陽一, 北川宜稔
出版社: マイナビ
発売日: 2012/1/28
メディア: 単行本 (ソフトカバー)
ページ数: 368 ページ