第1回コンテストの解説
- 解説資料
- リンク先ファイルは授業開始後にアップロードされる．
成績評価
前回同様，コンテスト結果とレポートの内容により評価する．
- 本授業への出席とレポートの提出は必須である．
- システム上でコンテストの
最初の2問（問題A，問題B）最初の1問（問題A）について「CORRECT」（正答）の結果を得ているか否かで本授業への出欠を判定する．
- コンテスト結果を成績評価に反映する．したがって，より早く，より多くの問題について「CORRECT」の結果を得ている方が良い成績になる．
- 不正（レポートの剽窃等）を行った学生および不正を援助した学生は処罰される．
レポート
今日の授業で自分が解いたもっとも難しい問題（あるいは，より難しい問題）の解き方と実装の方針をレポートとして提出せよ． ただし，以下の点に注意すること．
- 提出期限は 2020-06-25 23:59（3週間後）．
- 提出は Google Classroom の「実践的・競技プログラミング（2）レポート」から行うこと．
- PDF で提出すること．
- ページサイズは A4，ページ数の上限は4ページとする（説明が十分ならどれだけ短くても構わない）．
- レポートにはレポートタイトル，氏名，学籍番号，日付，ページ番号を含めること．
- レポートにソースコードを含めなくても良い．ただし，説明に必要であればソースコードの部分または全体を載せても良い．
- 説明がわかりやすくなるよう図を使うなど工夫すること．
- 誤字脱字に注意し，レポートの体裁にも気を配ること．
コンテストの前に
競技プログラミングと通常のプログラミング（共通部分と違い）
競技プログラミングで求められる能力は，通常のプログラミングの場合と多くの共通点を持つ． その一方で，まったく考え方が異なる部分もある．
- 競技プログラミングと通常のプログラミングで共通して求められる能力．
- 自然言語により表現される問題に対して，その問題を解くソフトウェアを設計する能力．
- データ構造やアルゴリズムの知識・応用能力．
- 必要となる計算量や記憶領域の見積もり．
- プログラミング言語（標準ライブラリの利用等を含む）の利用能力．
- ソースコードの問題個所の特定と修正能力（デバッグ技術）．
- 競技プログラミングと通常のプログラミングで考え方が異なる点．
- 競技プログラミングでは保守性は求められない． コードの利用はコンテストその場限りであるため． したがって，通常のプログラミングでは許されない以下のような手段を使っても良い．
- 自己説明的でない短い変数名の多用（コード可読性は低下するがコード記述時間を節約できる）．
- 関数マクロの多用．ただしマクロの挙動を理解し，副作用に注意して使用すること．
- グローバル変数の使用（保守性は著しく低下するが，関数間のデータ受け渡しが簡単になる）．
- 1つの関数の中にたくさんの機能を詰め込むコード記述（通常は機能ごとに独立した関数とすべきだが，まとめた方がコード記述時間を節約できる）． 同様にファイル分割を行う必要もない．
- 競技プログラミングでは入力のチェックやエラー処理を書く必要はない．
- 通常のプログラミングでは，想定外の入力がないかチェックを行い，おかしな入力に対するエラー処理を書く．
- 競技プログラミングでは，入力は必ず問題文中の制約を守っているため，想定外の入力やエラー処理を考える必要はない．
- 競技プログラミングに出題される問題には必ず適当な解法が存在するが，現実の問題はそうとは限らない．
- 特に研究で扱うような問題は，良い解法が存在しないことが多々ある．
- 競技プログラミングでは最悪計算量を考える（平均計算量は重視されない）．
- 例えば分枝限定法によるツリー探索は，多くの場合に探索範囲を限定してプログラムを高速化するが， 最悪ケースでは全探索してしまう．
- 競技プログラミングのコンテストシステムは大抵そのような最悪ケースに近い入力をテストに含めているため，最悪ケースで性能の出せない方法は回避するのが一般的である．
- 通常のプログラミングでは，平均的に速ければ十分であることが多く，そのような場合には典型的な入力に対して高速に機能する方法が望まれる．
状況に応じたプログラミングのスタイルを選ぶことが大切．
競技プログラミングの問題を解くための考え方
- 説明資料
- リンク先ファイルは授業開始後にアップロードされる．
宿題
宿題に関するページを見よ．
コンテスト（演習）
ルール
- 第1回コンテストのルールと同じである．
- ただし，出席は問題Aの正答を得ているか否かで判定する．
- 出席したが事情があり問題Aに正答できなかった場合は教員（廣田）にeメールせよ．
コンテストページ
- コンテストシステム（DomJudge）の使い方
- コンテストサイト
- 開始予定時刻：2020-06-04 14:30 (JST) 【開始時刻は授業中にアナウンスします】
- 終了時刻：2020-06-04 18:00 (JST)
- コンテストの全問を解いた場合，残りの時間は自由にして良い．
- 忘れないうちにレポート作成に取り掛かることを推奨．
- それでも時間が余る場合は，宿題を片づけることを推奨．
- 全体の回答状況を見て，ヒントを出す場合がある．
- 問題解説はレポート提出期限後にウェブ掲載する．
第2回コンテストの解説
- 解説資料
リンク先ファイルはレポート提出期限後にアップロードされる． 2020-06-26 アップロード．
付録（競技プログラミングを始めたい人へのアドバイス等）
- 競技プログラミングで使われる基本テクニックの多くは第1回付録記載の「プログラミングコンテストチャレンジブック 第2版」（蟻本）に書かれているので読んでみよ．
- AtCoder などのオンラインコンテストサイトに登録し，過去問を解いてみよ．
- 特に，AtCoder Beginner Contest（ABC）は競技プログラミング初心者～中級者向けに開催される大会で問題も比較的易しい．
- 過去の ABC の問題Aや問題B（最も易しい2題）の大半が解けない場合は，競技プログラミング以前のプログラミングの基本の学習に時間をかける方が良い．
- 慣れてきたら，実際に ABC に参加してみよ．
- 競技プログラミングに適したプログラミング言語の習得・使用を推奨．
- C++（C++11以降）や Java などの高機能かつある程度高速な言語が一般的に有利とされる．
- C の理解が不十分な状態ならば，まずは C の学習を進める方が良い．
- C しか使えない場合も，ANSI C（従来のC言語，皆さんが授業で習ったもの，C89/C90 とも呼ばれる）ではなく C99 を使えば多少楽になる．
- C99 は ANSI C に機能を追加した新しいC言語規格．1999年に ISO 規格として発行された．C99 にさらに多くの機能を追加した規格 C11 も存在する．
- C99 は，変数宣言がブロックの先頭以外で可能，可変長配列が利用可能，複素数が標準サポートされるなど，ANSI C に比べて使い勝手が良い．
- C99 で記述された C ソースコードは，
gcc -std=c99 hoge.c とオプションをつけてコンパイルする．
- 本授業中のコンテストのように使用できる言語が限定されている場合は，その言語を使用するしかない．
- コンテスト固有のルールやノウハウに注意．
- 例えば，ACM ICPC は電子的準備に強い制限がある上に3名チームで利用できる計算機が1台であるなどの制約があるのに対して， AtCoder のコンテストは電子的な事前準備やコンテスト中のウェブ検索が可能かつ個人戦である．
- したがって，AtCoder であれば，事前に使いそうなソースコード雛型の準備や，参考にしそうなウェブサイトを予め開いておくなどの対策が求められる．
- 誤答に対するペナルティもコンテストにより異なる．ペナルティがない（あるいは非常に小さい）ならテスト不十分でも積極的に提出するという戦略が考えられる．
- 簡便なデバッグ技術
- サンプル入力でプログラムがクラッシュしたら
gdb コマンドなどのデバッガを使ってエラー発生個所を特定できる．
- IDE（Eclipse や Visual Studio など）付属の GUI デバッガを使用する手もある．
- デバッガを使用できない場合，二分探索でエラーの原因を特定する．
- プログラムを前半と後半に分け，後半をコメントアウトして再実行することでエラーが前半・後半のいずれによるものか特定できる． 特定されたエラー範囲をさらに二分して同様の行為を繰り返せばエラーの発生個所を十分小さく絞り込める．
- プログラムのエラーに再現性がない場合には変数の未初期化や配列の添え字範囲を疑う．
- 新しいバージョンの GCC では address sanitizer を使って添え字チェックが出来る（詳しくは
gcc sanitizer などでウェブ検索）．
- 授業用仮想マシンで使用するCentOS 7標準コンパイラGCC 4.8.5ではこの機能は使用できない．
- 競技プログラミングに適したエディタの使用を推奨．少なくとも，キーワードのカラーハイライトや，変数名の補完機能があるものが望ましい．