電気電子情報工学実験II (b) 実践的・競技プログラミング（2022年度）第2回

講話（横野智紀氏）

横野氏より，ICPC 参加体験談，競技プログラミングについてのお話を伺う．

練習コンテスト（Contest 1-3）解説

解説資料（前回授業ページ掲載のものと同じ）

問題を解くための考え方

説明資料

競技プログラミングと通常のプログラミング（共通部分と違い）

競技プログラミングで求められる能力は，通常のプログラミングの場合と多くの共通点を持つ．その一方で，まったく考え方が異なる部分もある．

競技プログラミングと通常のプログラミングで共通して求められる能力．
- 自然言語により表現される問題に対して，その問題を解くソフトウェアを設計する能力．
- データ構造やアルゴリズムの知識・応用能力．
- 必要となる計算量や記憶領域の見積もり．
- プログラミング言語（標準ライブラリの利用等を含む）の利用能力．
- ソースコードの問題個所の特定と修正能力（デバッグ技術）．
競技プログラミングと通常のプログラミングで考え方が異なる点．
- 競技プログラミングでは保守性は求められない． コードの利用はコンテストその場限りであるため．したがって，通常のプログラミングでは許されない以下のような手段を使っても良い．
  - 自己説明的でない短い変数名の多用（コード可読性は低下するが命名時間やコード記述時間を節約できる）．
  - 関数マクロの多用．ただしマクロの挙動を理解し，副作用に注意して使用すること．
  - グローバル変数の使用（保守性は著しく低下するが，関数間のデータ受け渡しが簡単になる）．
  - 1つの関数の中にたくさんの機能を詰め込むコード記述（通常は機能ごとに独立した関数とすべきだが，まとめた方がコード記述時間を節約できる場合がある）．同様にファイル分割を行う必要もない．
- 競技プログラミングでは入力のチェックやエラー処理を書く必要はない．
  - 通常のプログラミングでは，想定外の入力がないかチェックを行い，おかしな入力に対するエラー処理を書く．
  - 競技プログラミングでは，入力は必ず問題文中の制約を守っているため，想定外の入力やエラー処理を考える必要はない．
- 競技プログラミングに出題される問題には適当な解法が存在するが，現実の問題はそうとは限らない．
  - 特に研究で扱うような問題は，良い解法が存在しないことが多々ある．
- 競技プログラミングでは平均計算量よりも最悪計算量を考えることが多い．
  - 例えば分枝限定法によるツリー探索は，多くの場合に探索範囲を限定してプログラムを高速化するが，最悪ケースでは全探索してしまう．
  - 競技プログラミングのコンテストシステムは大抵そのような最悪ケースに近い入力をテストに含めているため，最悪ケースで性能の出せない方法は回避するのが一般的である．
  - 通常のプログラミングでは，平均的に速ければ十分であることが多く，そのような場合には典型的な入力に対して高速に機能する方法が望まれる．

状況に応じたプログラミングのスタイルを選ぶことが大切．

練習コンテスト（Contest 2-1）

ルール

すべての問題で実行時間制限と記憶領域制限が設定されている．問題ごとの制限を確認するには，コンテスト開始後に競技参加者向けのトップ画面の Problemset をクリックせよ．
回答には C（C99），C++（C++11），Java が利用できる．
他人に相談したり，他人にヒントを与えてはならない．
コンテスト中にウェブ検索や書籍等を使って調べものをしても良い．
ソースコードの雛型などの電子的準備をしても良い．
- ただし流用して良いのは自分が書いたコードのみであり，他者が書いたコードを複写してはならない．
本コンテストの結果は成績評価の対象外である．

コンテストページ

コンテストシステム（DomJudge）の使い方
コンテストサイト．
- 右上に「contest:」というプルダウンメニューから「Contest2-1」を選ぶ．
- 開始予定時刻：2022-05-19 ??:?? (JST) 【授業中にアナウンスします】
- 終了時刻：2022-05-19 ??:?? (JST) 【授業中にアナウンスします】
- コンテスト時間：50分
- 問題数：2
コンテストの全問を解いた場合，残りの時間は自由にして良い．
全体の回答状況を見て，ヒントを出す場合がある．

解説

解説資料（コンテスト終了後にアップロード）．

競技プログラミングを始めたい人へのアドバイスなど

AtCoder などのオンラインコンテストサイトに登録し，過去問を解いてみよ．
- まずは AtCoder Beginners Selection から適当に問題を選んで解いてみよ．
- 感覚がつかめたら過去の AtCoder Beginner Contest（ABC）の過去問を解いてみよ．
  - AtCoder の過去のコンテスト一覧：https://atcoder.jp/contests/archive?lang=ja
  - ABC は競技プログラミング初心者～中級者向けに開催される大会で問題も比較的易しい．
  - ABC の問題Aや問題B（最も易しい2題）の大半が解けない場合は，競技プログラミング以前のプログラミングの基本の学習に時間をかける方が良い．
    - ただし，近年のABCの問題Bはやや難化傾向．
- 少し慣れてきたら，実際に ABC に参加してみよ．
  - 始めたいと思ったら迷わず始めるのが良い．
競技プログラミングに適した開発環境の利用を推奨．
- 例えばエディタであれば，少なくともキーワードのカラーハイライトや変数名の補完機能があるものが望ましい．
- 高機能なエディタ，プログラムのビルドシステム（コンパイル・リンクを自動で行うシステム），デバッグ機能などを統合した統合開発環境（例：Eclipse）を使う手もある．
競技プログラミングに適したプログラミング言語の習得・使用を推奨．
- C++（C++11以降）や Java などの高機能かつ実行速度がある程度高速な言語が一般的に有利とされる．
  - C の理解が不十分な状態ならば，まずは C の学習を進める方が良い．
- C しか使えない場合も，ANSI C（従来のC言語，皆さんが授業で習ったもの，C89/C90 とも呼ばれる）ではなく C99 を使えば多少楽になる．
  - C99 は ANSI C に機能を追加した新しいC言語規格．1999年に ISO 規格として発行された．C99 にさらに多くの機能を追加した規格 C11 や C17 も存在する．
  - C99 は，変数宣言がブロックの先頭以外で可能，可変長配列が利用可能，複素数が標準サポートされるなど，ANSI C に比べて使い勝手が良い．
  - C99 で記述された C ソースコードは，gcc -std=c99 hoge.c とオプションをつけてコンパイルする．
    - 新しいバージョンの gcc ではオプションを付けなくても C99 としてコンパイルできる場合がある．
- コンテストで使用できる言語が限定されている場合は，その中から言語を選択するしかない．
コンテスト固有のルールやノウハウに注意．
- 例えば，（2019年度以前の）ICPC は電子的準備に強い制限がある上に3名チームで利用できる計算機が1台であるなどの制約があるのに対して， AtCoder のコンテストは電子的な事前準備やコンテスト中のウェブ検索が可能かつ個人戦である．
  - したがって，AtCoder であれば，事前に使いそうなソースコード雛型の準備や，参考にしそうなウェブサイトを予め開いておくなどの対策が求められる．
- 誤答に対するペナルティもコンテストにより異なる．ペナルティがない（あるいは非常に小さい）ならテスト不十分でも積極的に提出するという戦略が考えられる．
競技プログラミングで使われる基本テクニックの多くは第1回付録記載の「プログラミングコンテストチャレンジブック第2版」（蟻本）に書かれているので読んでみよ．

デバッグの技術

プログラムを書く際，どれほど注意してもプログラムの不具合（バグ）を完全に避けるのは難しい．
しかしながら日常的にプログラミングをしていない者には難解なバグであっても，経験豊かなプログラマには瞬間的に解決可能であったり，そもそも当然に予防されていることが多い．
ここでは基本的なバグの修正（デバッグ）技術，バグの予防の方法の初歩について述べる．

予防と早期発見

デバッグ技術を磨く前に，バグを予防したり早期発見する方がはるかに賢く，手間も少ない．
コンパイラによる警告を活用する．
- コンパイラは文法的に合法であっても，静的解析で不具合が疑われる箇所を警告する機能を持つのが普通である．
  - 変数未初期化
  - if 文の条件において比較（a == b）せず代入（a = b）を使用
  - 関数に渡す引数の数や型の誤り
  - 数値のオーバーフロー
  - 未定義動作
  - 未使用変数
  - 推奨されない関数の使用（gets 関数など）
  - …
- コンパイラのもつ警告機能をできるだけ強化して使用する．
  - 例えば gcc であれば以下のように警告オプションを付加する（実はこれでもすべての警告が出力されるわけではない）．
```
gcc -Wall -Wextra fuga.c
```
  - コンパイラごとに警告可能な問題点，警告のためのオプションは異なる．自分の使用するコンパイラのマニュアルを読むこと．
    - gcc の警告オプションに関するマニュアル
- コンパイラの静的解析による不具合検出能力は限定的であるが，検出された不具合の警告を無視してはならない．
少しコードを書くたびにプログラムをビルド（コンパイル），実行して異常がないかを確認する．
- 全部書いてからコンパイルエラーがないか，正常に実行されるかを確認するのは良い考えではない．
- 今までバグがなく，新たに問題が生じたのであれば，新たに追記された少しのコード（とその関連箇所）に原因を絞り込むことができる．
- これを行うためには容易にプログラムのビルド，実行が可能であるようにしておく．
  - 例えばプログラムのビルドと実行をひとまとめにした Makefile を用意しておく．
  - プログラムのビルドだけならば，Eclipse などの IDE を使えば，常時コンパイラ警告となる箇所を表示してくれる．
- 理想的にはテストコードを書いておき，コードを追記や変更するたびに自動的に実行する．
  - 競技プログラミングでは時間的制約があるため，現実的にはテストコードを準備するのは難しい．
assert 関数（実際はマクロ）による検査．

デバッガ

デバッガはプログラムのデバッグ作業を支援するツール．
- gdb コマンドなど．
デバッガの機能
- ステップ実行
- 実行中の任意箇所での変数出力
- ブレークポイント設定
- 条件付ブレーク
- プログラムのクラッシュ箇所の検出
- core ファイルを用いたスタックトレース
- …

典型的な使用例：プログラムを実行してクラッシュしたときに gdb コマンドでクラッシュ箇所を突き止める．

バグのあるサンプルプログラム，サンプル入力
- 配列の範囲外アクセスによるエラー停止を期待しているが，必ずしも停止するとは限らない点に注意．
サンプルプログラムをコンパイル，実行するとクラッシュする可能性がある．エラーメッセージは環境により異なるので注意．

gcc -Wall -Wextra find_median_broken.c -o find_median_broken

./find_median_broken < find_median_input_1000.txt
zsh: segmentation fault (core dumped)  ./find_median_broken < find_median_input_1000.txt

プログラムをコンパイルする際にデバッグ情報を生成するようにオプション -g を付加してコンパイルする．

gcc -g -Wall -Wextra find_median_broken.c -o find_median_broken

デバッガを起動する．

gdb ./find_median_broken

プログラムを実行する．クラッシュすると該当するプログラム行が表示される．

GNU gdb (Ubuntu 9.2-0ubuntu1~20.04.1) 9.2
Copyright (C) 2020 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
Type "show copying" and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
    <http://www.gnu.org/software/gdb/documentation/>.

For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from ./find_median_broken...
(gdb) run < find_median_input_1000.txt
Starting program: /home/hirota/2022_exp2/find_median_broken < find_median_input_1000.txt

Program received signal SIGSEGV, Segmentation fault.
0x0000555555555298 in bubble_sort (n=1000, a=0x55555555b2b0) at find_median_broken.c:14
14              a[j * n] = tmp; /* Should be a[j + 1] = tmp; */
(gdb)

gdb によるデバッグの手順はプログラミング基礎IIで学んだはずであるので詳細には触れない．
IDE（Eclipse や Visual Studio など）では付属のデバッガを用いて GUI でデバッグ処理を行うこともできる（例1，例2）

Address Sanitizer

Address Sanitizer を使えば，配列の範囲外アクセスを動的に（実行時に）検出できる．
- 比較的新しいバージョンの GCC などで利用できる．
- 残念ながら，計算機室の CentOS 7 標準コンパイラ GCC 4.8.5 ではこの機能は使用できない．

使用例

例えば，前述のプログラムは小さな入力に対してはクラッシュせず，単に誤った結果を出力するかもしれない．

gcc -g -Wall -Wextra find_median_broken.c -o find_median_broken

./find_median_broken < find_median_input_10.txt
1.123400

コンパイルオプション -fsanitize=address を付加して Address Sanitizer 機能を有効化すればば，プログラムの実行時に配列の範囲外アクセスを検出してエラーであることを教えてくれる．

gcc -g -fsanitize=address -Wall -Wextra find_median_broken.c -o find_median_broken

./find_median_broken < find_median_input_10.txt
=================================================================
==1542==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6070000001a0 at pc 0x55fe0844745c bp 0x7fffbf7f7870 sp 0x7fffbf7f7860
WRITE of size 8 at 0x6070000001a0 thread T0
    #0 0x55fe0844745b in bubble_sort /home/hirota/2022_exp2/find_median_broken.c:14
    #1 0x55fe0844760d in main /home/hirota/2022_exp2/find_median_broken.c:31
    #2 0x7f2757c05082 in __libc_start_main ../csu/libc-start.c:308
    #3 0x55fe0844720d in _start (/home/hirota/2022_exp2/find_median_broken+0x120d)

Address 0x6070000001a0 is a wild pointer.
SUMMARY: AddressSanitizer: heap-buffer-overflow /home/hirota/2022_exp2/find_median_broken.c:14 in bubble_sort
Shadow bytes around the buggy address:
  0x0c0e7fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c0e7fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c0e7fff8000: fa fa fa fa fd fd fd fd fd fd fd fd fd fa fa fa
  0x0c0e7fff8010: fa fa 00 00 00 00 00 00 00 00 05 fa fa fa fa fa
  0x0c0e7fff8020: 00 00 00 00 00 00 00 00 00 00 fa fa fa fa fa fa
=>0x0c0e7fff8030: fa fa fa fa[fa]fa fa fa fa fa fa fa fa fa fa fa
  0x0c0e7fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c0e7fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c0e7fff8060: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c0e7fff8070: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c0e7fff8080: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==1542==ABORTING

「プログラムに配列の範囲外アクセスをする不具合があるにもかかわらず，偶然に動き続けてしまう」という深刻な問題を早期に発見できる．
- この機能はとても強力である．
- 不具合は発生後のデバッグにも利用できるが，不具合予防のために普段から利用するのがより賢い．
余談だが，メモリリークを検出する Leak Sanitizer 機能も存在する．

二分法デバッグ

二分探索でエラーが生じている箇所を特定する．
- プログラムを前半と後半に二分し，不具合が前半・後半のいずれで生じているかを特定する．
  - 例：結果の値に不具合のあるプログラムの前半と後半の間に printf を挟んで変数を表示させる．変数が期待した値になっているか否かにより不具合を起こしている範囲を絞り込む．
  - 例：クラッシュ箇所が明らかでないプログラムを前半と後半に二分し，後半をコメントアウトして再実行する．再びクラッシュするか否かにより不具合を起こしている範囲を絞り込む．
- 特定された範囲をさらに二分して同様の行為を繰り返せばエラーの発生個所を十分小さく絞り込める．
主にデバッガが使用できない場合などに用いられる．
- 十分な機能を備えたデバッガが使用できないプログラミング言語を使用している場合（きわめて稀），
- デバッガが使用できない計算機を使用している場合．
- プログラマがデバッガを使用できない場合．
デバッガと比べると手軽さと言う点では優れるが，問題点も多い．
- 多数の変数を監視する場合，長大な printf の記述が必要．
- 副作用が生じる可能性がある．
  - コメントアウトや printf の挿入によりプログラムの振る舞いが変化するおそれ（再現性のないバグのため）．
  - バグが再現されなくなるおそれ．
- デバッグのための記述が新たなバグを生むおそれ．
  - デバッグのためにコードに手を加える場合，容易に元に戻せるようにする．
    - git などの version control system，revision control system (RCS) を使用する．

再現性のないバグ

プログラムのエラーに再現性がない場合，有効な解決策は少ない．
再現性がないバグが生じる典型的な原因．
- 変数・メモリの未初期化
  - 未初期化の数値の変数を printf 表示すると意図せず巨大な数が表示されるのが典型．
    - 単なる型間違いの場合もある．
  - コンパイラ警告で予防できることもある．
    - 関数の引数として受け取る配列や malloc/realloc された領域などコンパイラが検出できない未初期化も多くある．
- 配列の添え字範囲の超過
  - C/C++ だと配列の添え字範囲を超えても，即エラーになるとは限らない．
  - 添え字範囲を超えた配列と関係のない箇所に不具合を生じさせることもある．
  - Address Sanitizer を使えば検出可能．
  - 言語によってはこのような問題を回避できる．
    - Java なら IndexOutOfBoundsException 例外が生じる．
    - C++ であれば，例えば配列の代わりに std::vector を使用して要素参照には at() 関数を用いれば添え字範囲を超えたときに out_of_range 例外が送出される．
- 未定義処理
  - 例えば，負数のオペランドに対する剰余演算子の振る舞いは ANSI C では未定義（C99 から定義される）
  - （競技プログラミングでは稀な状況だが）コードを変えずに開発環境や実行環境を変えて不具合が生じる場合は原因の有力候補．
- マルチプロセス/マルチスレッドプログラミング（並列処理）
  - マルチプロセスあるいはマルチスレッドでプログラムを並列処理する場合，複数のプロセス間あるいはスレッド間で，処理の順番は保障されない．
  - 競プロでは稀．
- 連携している外部システムの問題
  - 連携している外部システムの振る舞いに問題がある，通信が安定しないなどの状況．
  - 競プロでは稀．
再現性はないが規則性がみられる場合，記録を残すことで規則性から原因を推測できることがある．

プログラマの誤解によるバグ

誤解の例
- 要求仕様の誤解．
  - 例えば，未満と以下を読み違えている．
- プログラミング言語仕様の誤解．
  - 例えば関数 fgets と scanf で改行文字を読み込み方が異なることに気付いていない．
- 誤った方法で問題を解けると勘違いしてる．
プログラマの誤解によるバグは，デバッガ等のツールを使っても解決できないことが多い．
他のプログラマに発見してもらう．
- 単独で参加する競技プログラミングでは不可だが，チーム戦の場合には可能．
- プログラムを書いた人が意図を説明しながら，コードを説明することで問題を発見してもらう．
- 実際のソフトウェア開発現場でペアプログラミングやコード・レビューが導入される動機の一つ．

本番コンテスト（Contest 2-2）

ルール

すべての問題で実行時間と記憶領域の制限が設定されている．問題ごとの制限を確認するには，コンテスト開始後に競技参加者向けのトップ画面の Problemset をクリックせよ．
回答には C（C99），C++（C++11），Java が利用できる．
コンテスト中にウェブ検索や書籍等を使って調べものをしても良い．
ソースコードの雛型などの電子的準備をしても良い．
- ただし流用して良いのは自分が書いたコードのみであり，他者が書いたコードを複写してはならない．
他人に相談したり，他人にヒントを与えてはならない．
- 問題に関する疑義照会は挙手して教員に直接訪ねること．
本コンテストの結果は成績評価の対象である．また，出席チェックの対象でもあるので必ず1回はコンテストシステムにソースコードを提出すること．
全体の回答状況を見て，教員がヒントを出す場合がある．
コンテストの全問を解いた場合，残りの時間は自由にして良い．
- ウェブ上に存在するプログラミングコンテストの過去問を解くことを推奨．

コンテストページ

コンテストシステム（DomJudge）の使い方
コンテストサイト．
- 右上に「contest:」というプルダウンメニューから「Contest2-2」を選ぶ．
- 開始予定時刻：2022-05-19 ??:?? (JST) 【授業中にアナウンスします】
- 終了時刻：2022-05-19 ??:?? (JST) 【授業中にアナウンスします】
- コンテスト時間：~~100分~~ 90分
- 問題数：4

解説

解説は次回授業中に行う．

復習用コンテストシステム

授業終了後に復習用のコンテスト「Prac2-1」，「Prac2-2」が稼働する．コンテストの復習に用いられたい．

参考書籍

Brian W. Kernighan（著），Rob Pike（著），福崎俊博（訳），「プログラミング作法」，アスキー，2000．
- デバッグについて第5章に記述．
- 若干古い記述がされている部分があることに注意．
- 2017年に再販されている．