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

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

本実験の内容と狙い

ICPC 国内予選のチーム編成

例年(2019年度まで)は本実験中に開催されるコンテストの結果を元に ICPC 国内インターネット予選に参加するチーム編成を行っていた. しかしながら2020年年度以降,COVID-19 の影響により ICPC 国内インターネット予選の実施日程が大きく変更されたため,2021年度は授業内でのチーム編成を行わない(2020年度の日程変更2021年度の日程見通し).

学生が自主的にチーム編成して ICPC 予選に参加することは大変良い経験になるので推奨する. チームのコーチや監督員のアテがなければ廣田に依頼すれば引き受けるので遠慮なく申し出よ. ただし,2020年度のオンライン予選は従来と異なり監督員不要であったので,参加する場合はその年度のルールをよく確認すること.

成績評価

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

コンテストの前に

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

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

練習コンテスト(Contest 1-1)

計算量・実行時間と記憶領域(メモリ)の見積もり

競技プログラミングでは,プログラムの実行時間(または消費CPU時間)や使用できる記憶領域に制約があるのが普通である. 例えば,「すべてのテスト入力に対して 2 [sec.]以内,使用記憶領域 128 [MB]以下で答えを出力しなければならない」といった具合である. そのような制約を満たすプログラムを設計するには, 使用するデータ構造とアルゴリズムを考え,プログラムの実行時間と記憶領域を事前に見積もる必要がある.

例として,実行時間 0.5 [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回)程度の 基本的な処理を実行できる. ここで言う基本的な処理とは整数や実数の加減乗算,代入操作などである. 分岐を伴う比較はこれらの処理よりと比べて時間を要するのが普通である.

上記の例の実行時間制限は 0.5 [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] の記憶領域しか使用しない. したがって,このプログラムの記憶領域は十分に制限内に収まっていると見積もられる.

練習コンテスト(Contest 1-2)

ルール

コンテストページ

本日のレポート課題

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

本番コンテスト(Contest 1-3)

ルール

コンテストページ

予告

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