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

競技プログラミング(プログラミングコンテスト)の概要

本実験の内容と狙い

ICPC 国内予選のチーム編成

例年は本実験中に開催されるコンテストの結果を元に ICPC 国内インターネット予選に参加するチームの編成が行われる. しかしながら今年度は,新型コロナウィルス流行の影響により, ICPC 国内インターネット予選の実施日程が見通せない. したがって,今年度は授業内でのチーム編成を行わない.

学生が自主的にチーム編成して参加する場合で,コーチや監督のアテがない場合は廣田に依頼すれば,廣田はこれを引き受ける(やむを得ない事情で引き受けられなくならない限り). 遠慮なく申し出よ.

成績評価

本日のコンテスト結果とレポートの内容により評価する.

レポート

本日のコンテスト内で自分が解いたもっとも難しい問題の解き方と早く解くための実装の方針をレポートとして提出せよ. ただし,以下の点に注意すること.

コンテスト(演習)の前に

実施するコンテストの基本的な流れ

リダイレクションやパイプを用いた入出力のチェック方法

計算量と記憶領域(メモリ)の見積もり

競技プログラミングでは,プログラムの実行時間(または消費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)」の部分を正確に見積もるのは難しい. しかしながら,この部分は大まかに見積もれば十分である(桁が合っていれば良い).

最後に,使用する記憶領域の見積もり方について解説する. 概ね変数および配列の使用する記憶領域の合計がプログラム全体の使用する記憶領域となる. したがって,上記の例では変数nijtmp,および配列aの記憶領域を考えれば良い. 変数nijtmpはそれぞれ数 [byte] しか使用しないため無視できる. 配列amalloc関数によってsizeof(double) * n [byte]の記憶領域が割り当てられる. 倍精度実数型doubleは(大抵の計算機環境では)8 [byte]であり,nとして与えらえる入力の最大値は105であるので, 配列aは最大でも 800 [KB] の記憶領域しか使用しない. したがって,このプログラムの記憶領域は十分に制限内に収まっていると見積もられる.

コンテスト(演習)

ルール

コンテストページ

付録(自習用の参考資料)