第1回授業のコンテスト解説
注意：リンク先ファイルは授業開始後にアップロードされる．
成績評価
前回同様，本番コンテスト結果とレポートの内容により評価する．
- 本授業への出席とレポートの提出は必須である．
- 一度の授業で複数回コンテストを実施する．最後に実施したコンテスト（本番コンテスト）の結果を成績評価に反映する． したがって，本番コンテストでより早く，より多くの問題について正答しているとより良い成績になる．
- 各授業の本番コンテストで，コンテストシステム上に一度でもソースコードを提出したら授業へ出席したと判定する．
- 正答でなくとも出席と判定するので，一問も解けない場合でも何らかのソースコードを提出すること．
- 不正（レポートの剽窃等）を行った学生および不正を援助した学生は処罰される．
コンテストの前に
競技プログラミングと通常のプログラミング（共通部分と違い）
競技プログラミングで求められる能力は，通常のプログラミングの場合と多くの共通点を持つ． その一方で，まったく考え方が異なる部分もある．
- 競技プログラミングと通常のプログラミングで共通して求められる能力．
- 自然言語により表現される問題に対して，その問題を解くソフトウェアを設計する能力．
- データ構造やアルゴリズムの知識・応用能力．
- 必要となる計算量や記憶領域の見積もり．
- プログラミング言語（標準ライブラリの利用等を含む）の利用能力．
- ソースコードの問題個所の特定と修正能力（デバッグ技術）．
- 競技プログラミングと通常のプログラミングで考え方が異なる点．
- 競技プログラミングでは保守性は求められない． コードの利用はコンテストその場限りであるため． したがって，通常のプログラミングでは許されない以下のような手段を使っても良い．
- 自己説明的でない短い変数名の多用（コード可読性は低下するがコード記述時間を節約できる）．
- 関数マクロの多用．ただしマクロの挙動を理解し，副作用に注意して使用すること．
- グローバル変数の使用（保守性は著しく低下するが，関数間のデータ受け渡しが簡単になる）．
- 1つの関数の中にたくさんの機能を詰め込むコード記述（通常は機能ごとに独立した関数とすべきだが，まとめた方がコード記述時間を節約できる）． 同様にファイル分割を行う必要もない．
- 競技プログラミングでは入力のチェックやエラー処理を書く必要はない．
- 通常のプログラミングでは，想定外の入力がないかチェックを行い，おかしな入力に対するエラー処理を書く．
- 競技プログラミングでは，入力は必ず問題文中の制約を守っているため，想定外の入力やエラー処理を考える必要はない．
- 競技プログラミングに出題される問題には必ず適当な解法が存在するが，現実の問題はそうとは限らない．
- 特に研究で扱うような問題は，良い解法が存在しないことが多々ある．
- 競技プログラミングでは最悪計算量を考える（平均計算量は重視されない）．
- 例えば分枝限定法によるツリー探索は，多くの場合に探索範囲を限定してプログラムを高速化するが， 最悪ケースでは全探索してしまう．
- 競技プログラミングのコンテストシステムは大抵そのような最悪ケースに近い入力をテストに含めているため，最悪ケースで性能の出せない方法は回避するのが一般的である．
- 通常のプログラミングでは，平均的に速ければ十分であることが多く，そのような場合には典型的な入力に対して高速に機能する方法が望まれる．
状況に応じたプログラミングのスタイルを選ぶことが大切．
競技プログラミングの問題を解くための考え方
練習コンテスト（Contest 2-1）
ルール
- すべての問題で実行時間制限と記憶領域制限が設定されている． 問題ごとの制限を確認するには，コンテスト開始後に競技参加者向けのトップ画面の
Problemset をクリックせよ．
- 回答には C（C99），C++（C++11），Java が利用できる．
- コンテスト中にウェブ検索や書籍等を使って調べものをしても良い．
- ソースコードの雛型などの電子的準備をしても良い．
- ただし流用して良いのは自分が書いたコードのみであり，他者が書いたコードを複写してはならない．
- 練習コンテストの結果は成績評価の対象外である．
コンテストページ
- コンテストシステム（DomJudge）の使い方
- コンテストサイト
- 右上に「contest:」というプルダウンメニューから「Contest2-1」を選ぶ．
- 開始予定時刻：2021-05-27 ??:?? (JST) 【授業中にアナウンスします】
- 終了時刻：2021-05-27 ??:?? (JST) 【授業中にアナウンスします】
- コンテスト時間：45分
- 問題数：2
- コンテストの全問を解いた場合，残りの時間は自由にして良い．
- コンテスト中は，映像・音声による授業配信を行わない．
- 全体に対する連絡は Discord チャンネルまたは授業ページ（このあたり）を通じて行う．
- 全体の回答状況を見て，ヒントを出す場合がある．
- 解説は次回に行う．
競技プログラミングを始めたい人へのアドバイスなど
- 競技プログラミングで使われる基本テクニックの多くは第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 や C17 も存在する．
- C99 は，変数宣言がブロックの先頭以外で可能，可変長配列が利用可能，複素数が標準サポートされるなど，ANSI C に比べて使い勝手が良い．
- C99 で記述された C ソースコードは，
gcc -std=c99 hoge.c とオプションをつけてコンパイルする．
- 新しいバージョンの gcc ではオプションを付けなくても C99 としてコンパイルできる場合がある．
- 本授業中のコンテストのように使用できる言語が限定されている場合は，その中から言語を選択するしかない．
- コンテスト固有のルールやノウハウに注意．
- 例えば，ACM ICPC は電子的準備に強い制限がある上に3名チームで利用できる計算機が1台であるなどの制約があるのに対して， AtCoder のコンテストは電子的な事前準備やコンテスト中のウェブ検索が可能かつ個人戦である．
- したがって，AtCoder であれば，事前に使いそうなソースコード雛型の準備や，参考にしそうなウェブサイトを予め開いておくなどの対策が求められる．
- 誤答に対するペナルティもコンテストにより異なる．ペナルティがない（あるいは非常に小さい）ならテスト不十分でも積極的に提出するという戦略が考えられる．
- 簡便なデバッグ技術
- サンプル入力でプログラムがクラッシュしたら
gdb コマンドなどのデバッガを使ってエラー発生個所を特定できる．
- IDE（Eclipse や Visual Studio など）付属の GUI デバッガを使用する手もある．
- デバッガを使用できない場合，二分探索でエラーの原因を特定する．
- プログラムを前半と後半に分け，後半をコメントアウトして再実行することでエラーが前半・後半のいずれによるものか特定できる． 特定されたエラー範囲をさらに二分して同様の行為を繰り返せばエラーの発生個所を十分小さく絞り込める．
- プログラムのエラーに再現性がない場合には変数の未初期化や配列の添え字範囲を疑う．
- 新しいバージョンの GCC では address sanitizer を使って添え字チェックが出来る（詳しくは
gcc sanitizer などでウェブ検索）．
- 授業用仮想マシンで使用するCentOS 7標準コンパイラGCC 4.8.5ではこの機能は使用できない．
- 競技プログラミングに適したエディタの使用を推奨．少なくとも，キーワードのカラーハイライトや，変数名の補完機能があるものが望ましい．
本日のレポート課題
本日の本番コンテスト内で自分が解いたもっとも難しい問題の解き方と早く解くための実装の方針をレポートとして提出せよ． ただし，以下の注意点を守ること．
- 提出期限は 2021-06-03 12:59（次回授業の開始直前）．
- 期限厳守のこと（期限後のレポート提出，レポート差し替えは本当に無視します）．
- 不完全でも可能な範囲で書いて期限内に提出すること．
- 提出は Google Classroom の「実践的・競技プログラミング（2）レポート」から行うこと．
- PDF で提出すること．
- ページサイズは A4，ページ数の上限は4ページとする（説明が十分なら1，2ページでも構わない）．
- 「説明が十分」というのは単に自分自身が理解できるできるだけでなく，第三者を理解・納得させられる状態のこと．
- レポートの中身にはレポートタイトル，氏名，学籍番号，日付，ページ番号を含めること．
- レポートのファイル名はeメールアドレスの
@ より左側の文字列で始めること．例えば hb990000_report1.pdf のようにすること．
- レポートにソースコードを含めなくても良い．ただし，説明に必要であればソースコードの部分または全体を載せても良い．
- 誤字脱字に注意し，レポートの体裁にも気を配ること．
本番コンテスト（Contest 2-2）
ルール
- すべての問題で実行時間と記憶領域の制限が設定されている． 問題ごとの制限を確認するには，コンテスト開始後に競技参加者向けのトップ画面の
Problemset をクリックせよ．
- 回答には C（C99），C++（C++11），Java が利用できる．
- コンテスト中にウェブ検索や書籍等を使って調べものをしても良い．
- ソースコードの雛型などの電子的準備をしても良い．
- ただし流用して良いのは自分が書いたコードのみであり，他者が書いたコードを複写してはならない．
- 他人に相談したり，他人にヒントを与えてはならない．
- 問題に関する疑義照会は Discord のダイレクトメッセージを廣田宛に送ること． 間違えて全体チャットを使って他者にヒントを与えないように注意．
- 本番コンテストの結果は成績評価の対象となる．
コンテストページ
- コンテストシステム（DomJudge）の使い方
- コンテストサイト
- 右上に「contest:」というプルダウンメニューから「Contest2-2」を選ぶ．
- 開始予定時刻：2021-05-27 ??:?? (JST) 【授業中にアナウンスします】
- 終了時刻：2021-05-27 ??:?? (JST) 【授業中にアナウンスします】
- コンテスト時間：100分
- 問題数：4
- コンテストの全問を解いた場合，残りの時間は自由にして良い．
- 忘れないうちにレポート作成に取り掛かることを推奨．
- レポート作成が時間内に完了したら，今度は作問してみよ．作問は問題を解くより難しい．良問をレポート付録として提出した場合には加点する（その場合は翌年度以降の問題として採用することがある）．
- コンテスト中は，映像・音声による授業配信を行わない．
- 全体に対する連絡は Discord チャンネルまたは授業ページ（このあたり）を通じて行う．
- 全体の回答状況を見て，ヒントを出す場合がある．
- 解説は次回に行う．
授業後の復習用コンテストシステム
- 授業終了後に復習用のコンテスト「Prac2-1」，「Prac2-2」が稼働する．コンテストの復習やレポート作成の手助けに用いられたい．
予告
- 次回の本番コンテストに最小全域木（Minimum Spanning Tree）を求める Prim アルゴリズムを応用して回答できる問題を出題します．