例年は本実験中に開催されるコンテストの結果を元に ICPC 国内インターネット予選に参加するチームの編成が行われる． しかしながら今年度は，新型コロナウィルス流行の影響により， ICPC 国内インターネット予選の実施日程が見通せない． したがって，今年度は授業内でのチーム編成を行わない．
学生が自主的にチーム編成して参加する場合で，コーチや監督のアテがない場合は廣田に依頼すれば，廣田はこれを引き受ける（やむを得ない事情で引き受けられなくならない限り）． 遠慮なく申し出よ．
本日のコンテスト結果とレポートの内容により評価する．
本日のコンテスト内で自分が解いたもっとも難しい問題の解き方と早く解くための実装の方針をレポートとして提出せよ． ただし，以下の点に注意すること．
CORRECT（正答）と表示されたら次の問題を選択して解く．誤答の場合はプログラムの問題個所を修正して再投稿する．
問題を解くプログラムを作成したら，問題に付記されている入出力例を使って，プログラムが正しく機能するかをチェックする． その際，手入力による標準入力や，目視による標準出力のチェックを行うのは非効率な上にミスの恐れがある． そこで，リダイレクションやパイプを使って標準入出力を使うようにする．
まず，問題に書かれている入出力の例をそれぞれファイルに保存する． 例えば入力例を example.in，出力例を example.out という名前で保存する（最後に1つの空行が含まれるように保存すること）．
実行するプログラムに対して，ファイルの内容を読み込ませるには以下のようにリダイレクション機能（<）を用いる．
./a.out < example.inこのようにすれば，プログラム実行時に example.in の内容がキーボード入力されたかのように振る舞う．
プログラムの標準出力が，出力例と一致するか確認するには，以下のようにパイプ（|）と diff コマンドを使用する．
./a.out < example.in | diff example.out -このように実行すると，プログラムの標準出力と example.out の比較が行われ，一致する場合には何も出力されない． 一方，出力が異なる場合には差分情報が表示される．
改行コードの違いを無視させたい（CR を取り除きたい）場合は，以下のようにする．
./a.out < example.in | diff --strip-trailing-cr example.out -心配であれば，自分で追加の入出力例（特に制約の境界にあるような極端な例）を作成してチェックする．
競技プログラミングでは，プログラムの実行時間（または消費CPU時間）や使用できる記憶領域に制約があるのが普通である． 例えば，「すべてのテスト入力に対して2 [sec.]以内，使用記憶領域128 [MB]以下で答えを出力しなければならない」といった具合である． そのような制約を満たすプログラムを設計するには， 使用するデータ構造とアルゴリズムを考え，プログラムの実行時間と記憶領域を事前に見積もる必要がある．
例として，実行時間2 [sec.]以内，記憶領域制限 64 [MB]で 「与えられるn個の実数の中央値を出力せよ（ただし 1 ≤ n ≤ 105）」という問題に対するプログラムを考える．
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int n;
double *a;
int i, j;
scanf("%d", &n);
a = malloc(sizeof(double) * n);
for (i = 0; i < n; ++i) {
scanf("%lf", &a[i]);
}
// Perform bubble sort in ascending order.
for (i = 0; i < n - 1; ++i) {
for (j = 0; j < n - 1 - i; ++j) {
if (a[j] > a[j + 1]) {
double tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
}
}
}
printf("%lf\n", a[n / 2]);
free(a);
return 0;
}上記のプログラムは，以下の3つの機能から成り立っている．
この3つの処理の計算量のオーダは，順に O(n)，O(n2)，O(1) であり， nが大きい場合には1番目と3番目の処理は，2番目と比べて無視できるほどに小さい． したがって，2番目の処理だけを考えれば大まかな計算量を見積もれる． 2番目の処理は，二重ループの内側の処理がおよそn2/2回実行される． 二重ループの内側では，1回の比較と，不等式が成立する場合には3回の変数の代入操作が実行される． したがって，毎回不等式が成立する最悪のケースでは， プログラム全体で以下の処理が実行される．
入力nとして与えられる最大の値は105であるので， 最悪の場合には 5×109回の比較， 1.5×1010回の代入操作 が実行されることになる．
1秒間に実行可能な処理は計算機環境や処理の内容に依存するが， 一般的には1 [sec.]あたり107回（良いケースでも108回）程度の 基本的な処理を実行できる． ここで言う基本的な処理とは整数の加減乗除や実数の加減乗算，代入操作などである． 分岐を伴う比較はこれらの処理よりと比べて時間を要するのが普通である．
上記の例の実行時間制限は2 [sec.]であるので， nが105に近い場合には制限時間内にプログラムは答えを出力できないと予想できる． したがって，計算量 O(n2) のバブルソートではなく，より高速なソートアルゴリズムを使わなければならない．
実際の計算量見積もりはコーディング前に行うため， 「(1/2)n2回の比較」や「(3/2)n2回の代入操作」における 「(1/2)」や「(3/2)」の部分を正確に見積もるのは難しい． しかしながら，この部分は大まかに見積もれば十分である（桁が合っていれば良い）．
最後に，使用する記憶領域の見積もり方について解説する． 概ね変数および配列の使用する記憶領域の合計がプログラム全体の使用する記憶領域となる． したがって，上記の例では変数n，i，j，tmp，および配列aの記憶領域を考えれば良い． 変数n，i，j，tmpはそれぞれ数 [byte] しか使用しないため無視できる． 配列aはmalloc関数によってsizeof(double) * n [byte]の記憶領域が割り当てられる． 倍精度実数型doubleは（大抵の計算機環境では）8 [byte]であり，nとして与えらえる入力の最大値は105であるので， 配列aは最大でも 800 [KB] の記憶領域しか使用しない． したがって，このプログラムの記憶領域は十分に制限内に収まっていると見積もられる．
Problemset をクリックせよ．