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

競技プログラミング（プログラミングコンテスト）の概要

• （ざっくり言うと）与えられた問題を決められた計算機資源（CPU時間，主記憶領域）の制限範囲内で解くプログラムを，より早く完成させる競技．
  • コンテストの問題の例．
  • 多くのコンテストは複数の問題により構成され，各々の問題を解くまでにかかった時間や問題の難度に応じてスコアが与えられる．その合計スコアにより勝敗を競う．
  • 明確な答えのない問題に取り組ませる形式のプログラミングコンテストもあるが，本授業では対象としない．
• 世界中で様々なプログラミングコンテストが実施されている．
  • 国際大学対抗プログラミングコンテスト（ICPC, International Collegiate Programming Contest）
    • 非常に著名で伝統的なプログラミングコンテスト．2018年までは米国計算機科学学会（ACM）が開催していた．
    • 各国の国内インターネット予選，オンサイト地域予選（例えば2022年横浜大会）を勝ち抜いたチームが，翌年に実施される世界大会で競技プログラミングの能力を競う．
    • ICPC は3人1チームで参加し，チームごとに1台のコンピュータを共有するという特徴がある． したがって，単にプログラミング能力が高ければ良いというものではなく， 1台しかない計算機をどのように利用するか，3人がそれぞれどのような役割を分担するかといった戦略が重要になる． また，問題の選択，アルゴリズムの理解，コーディングの早さ，デバッグ技術なども成績を左右する重要な要素となる．
      • COVID-19 の流行による特別ルールで2020–2022年は一人一台の PC を使用していたが，2023年から2019年以前のルールに戻った．
    • 過去何度も，本学科から学生チームが出場している．
      • 2021年は本学科から出場したチーム cutting tree が国内オンライン予選を見事突破し，Religonal Contest に出場．
  • AtCoder（オンラインコンテストサイト）
    • AtCoder 株式会社が運営するサイト「AtCoder」では定期的にオンラインのプログラミングコンテストが実施されている．
    • 初心者から上級者まで広い層から参加可能な多種のコンテストがあり，学生であるか否かに関係なく自由にコンテストに参加できる（参加資格制限のある一部コンテストを除く）．
    • 本学科の学生にも毎週参加している人がいる．
      • 決して，特別な人だけが参加するような難しいコンテストではない．
  • 各種のオンラインコンテストサイト
    • AtCoder と同様のオンラインコンテストサイトには TopCoder や CodeForces など様々なものがある．
  • 他にも Google Code Jam，国際情報オリンピックなど，非常に多くのコンテスト形式の大会が開催されている．
• 近年は，IT企業の採用でも競技プログラミング能力が評価対象になることがある（例）．
  • それほど競技プログラミングの認知度の高くなかった私の学生時代（2005年頃）でも，ICPC で活躍した選手は Google などのトップ企業から勧誘を受けると言われていた．
  • また，競技プログラミング能力そのものが評価されるわけではないが，coding interview と呼ばれる形式の採用面接では競技プログラミングの能力が活用できる．

ICPC Yokohama Regional 2023

ICPC Yokohama Regional 2023 の国内予選は2023年7月7日に実施予定である． 2023年5月9日に確認した時点でまだ登録可能なようである（〆切未記載）． ICPC 予選に参加することは大変良い経験になるので，学生が自主的にチーム編成して参加することを強く推奨する． チームのコーチや監督員のアテがなければ廣田に依頼すれば，引き受けてくれそうな大学院生を紹介するかあるいは廣田自身が引き受けるので遠慮なく申し出よ．

本実験の内容と狙い

• 本実験では実践的な課題を用いた競技プログラミングコンテスト形式の実験を行う．
• 学生は，コンテスト形式の実験を通じて，現実の問題を解決するプログラムを早く正確に作る技術を身に付ける．
• より具体的には，（プログラミングの授業で出題される練習問題と異なり）解き方が自明ではない問題に取り組み， 限られた時間内に解法を自ら設計し，データ構造やアルゴリズムを正しく選択，誤りなく動くコードに落とし込む能力を身に付ける． また，作成したコードに誤りが発覚した場合に，問題箇所を特定・修正する過程を経験する．

成績評価

• 成績評価は以下を総合的に勘案して行われる．
  • 第2回，第3回授業の最後に実施される本番コンテストの結果．
    • したがって，第2回，第3回授業の本番コンテストでより早く，より多くの問題について正答しているとより良い成績になる．
  • 第3回授業の4週間後を期限とするレポート．
• 以下の場合，成績は不可となる．
  • 実践的・競技プログラミングの第1回から第3回のうち1回でも欠席した場合．
    • 各回の最後に実施されるコンテストで，コンテストシステム上に一度でもソースコードを提出したら授業へ出席したと判定する．
      • 正答でなくとも出席と判定するので，一問も解けない場合でも何らかのソースコードを提出すること．
    • 一度の授業で複数回コンテストを実施する．最後に実施したコンテスト（本番コンテスト）の結果を成績評価に反映する．
  • レポートを期限内に提出しなかった場合．
    • 期限厳守のこと（期限後のレポート提出，レポート差し替えは本当に無視される）．
• 不正（レポートの剽窃，コンテストにおける故意のルール違反等）を行った学生および不正を援助した学生は厳しく処罰される．

レポート課題の予告

• 第3回授業（2023-05-25）の終了後，4週間以内（2023-06-22 23:59 まで）にレポートを提出すること．
• レポートには，各回で説明された以下の項目それぞれについての説明と，項目ごとにそれを実践した結果（プログラムを作成して問題を解いた結果）について報告すること．
  • 第1回：計算量・実行時間と記憶領域（メモリ）の見積もり．
  • 第2回：デバッグ．
  • 第3回：定番テクニック・アルゴリズムを利用したプログラム設計．
• レポートで報告する際の問題は好きに選択して良いが，本実験のコンテストで出題されたいずれかの問題を推奨する．
  • しかしながら，それ以外の適当な問題を用いても良い．例えば，授業外の競技プログラミングコンテストで出題された問題を解いたときの結果でも良い．
• レポート提出は Google Classroom の「実践的・競技プログラミング レポート」から行うこと．
• レポートは単一の PDF として提出すること．
• ページサイズは A4，ページ数の上限は12ページとする（説明が十分なら2，3ページでも構わない）．
  • 「説明が十分」というのは単に自分自身が理解できるできるだけでなく，第三者を理解・納得させられる状態のことである．
• レポートの中身にはレポートタイトル，氏名，学籍番号，日付，ページ番号を含めること．
• レポートのファイル名はeメールアドレスの @ より左側の文字列で始めること．例えば hb990000_report.pdf のようにすること．
• レポートにソースコードを含めなくても良い．ただし，説明に必要であればソースコードの部分または全体を載せること（別添するのではなく PDF に含めること）．
  • 読みやすくすること．例えば等幅フォントを使い，本文と明確に区別可能なように掲載すること．
• その他の注意点については，廣田に提出するレポートを作成する際の注意事項を参照のこと．

コンテストの前に

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

• コンテストは複数の問題から構成される．全体を眺めて解けそうな問題を選ぶ．
• 選択した問題を解くプログラムを作成する．
• 問題に付記された入出力サンプルを使ってプログラムが正しく機能するか確かめる． 異常がなさそうであれば，プログラムのソースコードをコンテストシステムに提出する．
• コンテストシステム内で自動的にコードがコンパイルされプログラムのチェックが行われる．
  • サンプル以外の様々なケースがテストされる．したがって，サンプル入力に対しては正常動作するプログラムであっても，他の入力に対して誤動作すれば誤答判定となる．
  • 実行時間超過や記憶領域（メモリ）制限超過の場合は正答にはならない．
• 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 -

• 心配であれば，自分で追加の入出力例（特に制約の境界にあるような極端な例）を作成してチェックする．

• 統合開発環境（Eclipse 等）にもファイルを用いた標準入出力機能があるのが普通である．

  • 実験外でそのような統合開発環境を用いる場合，自分の開発環境でのチェック方法を調べること．

練習コンテスト（Contest 1-1）

コンテストサイト

• コンテストサイトを開く．
  • ICS 上のブラウザで開くことを推奨する（ICS 上でプログラムを作成する場合）．
    • ページ下部の QA 参照．
  • ブラウザ側の証明書が古すぎると証明書が検証できない旨の警告が出ることがあるが，その場合は例外に追加して続行すること．
• 次に，コンテストシステム（DomJudge）の使い方 を読み，自分のアカウントを作成せよ．
  • 以後のコンテストでは同じアカウントを継続して使用するので ID とパスワードを忘れないこと．
• アカウントを作成してログイン後，右上の Logout ボタンの右側にコンテストを選択するプルダウンメニューが表示されるので「Contest1-1」を選ぶ．
• 開始時刻になるのを待つ．
• 開始時刻になったら「実施するコンテストの基本的な流れ」で説明したとおり問題に回答する．
• 回答は画面上部メニュー欄の「Submit」からコンテストシステムにソースコードを提出できる．
• 回答には C（C17），C++（C++14），Java が利用できる．
  • 細かいことが気になる人向けの詳細情報：
    • C: gcc version 10.2.1 20210110 (Debian 10.2.1-6), gcc -x c -Wall -O2 -static -pipe -o "$DEST" "$@" -lm
    • C++: gcc version 10.2.1 20210110 (Debian 10.2.1-6), g++ -x c++ -Wall -O2 -static -pipe -o "$DEST" "$@"
    • Java: javac 11.0.16, openjdk version "11.0.16" 2022-07-19, OpenJDK Runtime Environment (build 11.0.16+8-post-Debian-1deb11u1), OpenJDK 64-Bit Server VM (build 11.0.16+8-post-Debian-1deb11u1, mixed mode, sharing)
• 画面上部の「Scoreboard」から自分や他の学生の回答状況が確認できる．
• すべての問題で実行時間制限と記憶領域制限が設定されている． 問題ごとの制限を確認するには，コンテスト開始後に競技参加者向けのトップ画面の Problemset をクリックせよ．

ルール

• 他人に相談したり，他人にヒントを与えてはならない．
• コンテスト中にウェブ検索や書籍等を使って調べものをしても良い．
• ソースコードの雛型などの電子的準備をしても良い．
  • ただし流用して良いのは自分が書いたコードのみであり，他者が書いたコードを複写してはならない．
• コンテストの全問を解いた場合，残りの時間は自由にして良い．
• コンテストの情報
  • 開始予定時刻：2023-05-11 ??:?? (JST) 【授業中にアナウンスします】
  • 終了時刻：2023-05-11 ??:?? (JST) 【授業中にアナウンスします】
  • コンテスト時間：約30分（アカウント作成を含む）
  • 問題数：2
• 本コンテストの結果は成績評価の対象外である．

解説

解説資料（コンテスト終了後にアップロード）．

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

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

例として，実行時間 0.5 [sec.]以内，記憶領域制限 128 [MB]で 「与えられるn個の実数の中央値を出力せよ（ただし 1 ≤ n ≤ 10⁵）」という問題に対するプログラムを考える．

#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("%f\n", a[n / 2]);
  
  free(a);
  return 0;
}

上記のプログラムは，以下の3つの機能から成り立っている．

• 実数の個数nおよび，n個の実数の読み込み．
• n個の実数の並びに対するバブルソート．
• ソートされた実数の並びのn/2番目（すなわち中央値）の出力．

この3つの処理の計算量のオーダは順に O(n)，O(n²)，O(1) であり， nが大きい場合には1番目と3番目の処理は，2番目と比べて無視できるほどに小さい． したがって，2番目の処理だけを考えれば大まかな計算量を見積もれる． 2番目の処理は，二重ループの内側の処理がおよそn²/2回実行される． 二重ループの内側では，1回の比較と，不等式が成立する場合には3回の変数の代入操作が実行される． したがって，毎回不等式が成立する最悪のケースでは， プログラム全体で以下の処理が実行される．

• (1/2)n²回の比較．
• (3/2)n²回の代入操作．

入力nとして与えられる最大の値は10⁵であるので， 最悪の場合には 5×10⁹回の比較， 1.5×10¹⁰回の代入操作 が実行されることになる．

1秒間に実行可能な処理は計算機環境や処理の内容に依存するが， 一般的には1 [sec.]あたり10⁷回（良いケースでも10⁸回）程度の 基本的な処理（整数や実数の加減乗算，代入操作，比較など）を実行できると大まかに見積もれる （この見積もりは非常に大雑把であり，このような方法が許容されるかは状況によるので注意すること）．

上記の例の実行時間制限は 0.5 [sec.]であるので， nが10⁵に近い場合には制限時間内にプログラムは答えを出力できないと予想できる． したがって，計算量 O(n²) のバブルソートではなく，より高速なソートアルゴリズムを使わなければならない（例えば計算量 O(n logn) のマージソート）．

実際の計算量見積もりはコーディング前に行うため， 「(1/2)n²回の比較」や「(3/2)n²回の代入操作」における係数「(1/2)」や「(3/2)」を正確に見積もるのは難しい． しかしながら，制限時間に余裕をもって間に合うようにプログラムを設計できているのであれば，この部分は大まかに見積もれれば十分である．

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

練習コンテスト（Contest 1-2）

ルール

• すべての問題で実行時間制限と記憶領域制限が設定されている． 問題ごとの制限を確認するには，コンテスト開始後に競技参加者向けのトップ画面の Problemset をクリックせよ．
• 回答には C（C17），C++（C++14），Java が利用できる．
• 他人に相談したり，他人にヒントを与えてはならない．
• コンテスト中にウェブ検索や書籍等を使って調べものをしても良い．
• ソースコードの雛型などの電子的準備をしても良い．
  • ただし流用して良いのは自分が書いたコードのみであり，他者が書いたコードを複写してはならない．
• 本コンテストの結果は成績評価の対象外である．

コンテストサイト

• コンテストシステム（DomJudge）の使い方
• コンテストサイトを開く．
  • ICS 上のブラウザで開くことを推奨する（ICS 上でプログラムを作成する場合）．
  • コンテストを選択するプルダウンメニューから「Contest1-2」を選ぶ．
  • 開始予定時刻：2023-05-11 ??:?? (JST) 【授業中にアナウンスします】
  • 終了時刻：2023-05-11 ??:?? (JST) 【授業中にアナウンスします】
  • コンテスト時間：40分
  • 問題数：2
• コンテストの全問を解いた場合，残りの時間は自由にして良い．
• 全体の回答状況を見て，ヒントを出す場合がある．

解説

解説資料（コンテスト終了後にアップロード）．

練習コンテスト（Contest 1-3）

ルール

• すべての問題で実行時間と記憶領域の制限が設定されている． 問題ごとの制限を確認するには，コンテスト開始後に競技参加者向けのトップ画面の Problemset をクリックせよ．
• 回答には C（C17），C++（C++14），Java が利用できる．
• コンテスト中にウェブ検索や書籍等を使って調べものをしても良い．
• ソースコードの雛型などの電子的準備をしても良い．
  • ただし流用して良いのは自分が書いたコードのみであり，他者が書いたコードを複写してはならない．
• 他人に相談したり，他人にヒントを与えてはならない．
  • 問題に関する疑義照会は挙手して教員に直接訪ねること．
• 本コンテストの結果は成績評価の対象外である．ただし，出席チェックの対象であるので必ず1回はコンテストシステムにソースコードを提出すること．
• 全体の回答状況を見て，教員がヒントを出す場合がある．
• コンテストの全問を解いた場合，残りの時間は自由にして良い．
  • ウェブ上に存在するプログラミングコンテストの過去問を解くことを推奨．

コンテストサイト

• コンテストシステム（DomJudge）の使い方
• コンテストサイトを開く．
  • ICS 上のブラウザで開くことを推奨する（ICS 上でプログラムを作成する場合）．
  • コンテストを選択するプルダウンメニューから「Contest1-3」を選ぶ．
  • 開始予定時刻：2023-05-11 ??:?? (JST) 【授業中にアナウンスします】
  • 終了時刻：2023-05-11 ??:?? (JST) 【授業中にアナウンスします】
  • コンテスト時間：100分
  • 問題数：4

解説

• 解説資料（コンテスト終了後にアップロード）．
• 口頭での解説は次回授業中に行う．

復習用コンテストシステム

• 授業終了後に復習用のコンテスト「Prac1-3」が稼働する．コンテストの復習に用いられたい．

予告

• 次回以降の授業中に行うコンテストの一部は成績評価の対象となる．
• 今回のコンテストと同じルールで開催されるため，ソースコード雛型や持ち込み書籍の準備をしておくことを強く推奨する．

付録（自習用の参考資料，やや古い）

• 秋葉拓哉，他，「プログラミングコンテストチャレンジブック 第2版」，マイナビ，2012．
  • 競技プログラミング分野の標準的な教科書．
  • 通称「蟻本」．
  • 福井大のアカウントを持っている人は電子書籍として閲覧できると，ある学生さんから教えて頂きました．
    • 「学認アカウントをお持ちの方はこちら」をクリックして，遷移後のページのプルダウンメニューから福井大学を選択．その後，福大ポータルの認証画面になるので福大の ID とパスワードを入力したら書籍に飛びます（既に福大ポータルにログインしていたら，そのまま遷移します）．
    • 現在はリクエスト中のため時間制限があるが申請受理されると全部読めるようになる（おそらく来週から読めるようになっているだろう）とのことです．
• 筧捷彦，「目指せ!プログラミング世界一 ―大学対抗プログラミングコンテストICPCへの挑戦」，近代科学社，2009．
  • ICPC の OB が中心となって書かれた本．
• T. コルメン，他，「アルゴリズムイントロダクション 第3版」，近代科学社，2012．
  • （競プロの本ではなく）アルゴリズムとデータ構造に関する標準的教科書．
  • ややページ数が多く（第1巻，第2巻がある），やや難しいという意見もある． この本でなくても良いので，データ構造とアルゴリズムに関する自分に合った参考書を選んで読み通し，基本的なアルゴリズムの知識を身に付けるのが良い．
• 近年は競技プログラミング向けの本が多数出版されているので書店・図書館等を探されたい．

付録（Q and A）

• Q. ブラウザの開き方がわからない．
  • A. VcXsrv（ICS）上のターミナルで以下のコマンドを実行すると ICS 上で Firefox が立ち上がる．

  firefox &

• Q. vim や emacs の使い方が分からない（編入生向け）．
  • A. VcXsrv（ICS）上のターミナルで以下のコマンドを実行すると一般的な GUI エディタが起動できる．

  gedit &

• Q. gcc とは何か．C言語コンパイルコマンドは cc じゃないのか．
  • A1. CentOS 7 において cc と gcc は同じ．
  • A2. より正確に説明すると，CentOS 7 において /bin/cc は /bin/gcc への単なるシンボリックリンク（Windows でいうところのショートカットみたいなもの）．
  • A3. gcc は GNU Compiler Collection に含まれる C コンパイラのコマンド．
• Q. ソースコードのコンパイル方法が分からない．
  • A1. コンパイルコマンド例（C）

  gcc -Wall -O2 source.c

  • A2. コンパイルコマンド例（C++）

  g++ -std=gnu++11 -Wall -O2 source.cpp

  • A3. コンパイルコマンド例（Java）

  javac source.java

• その他の質問があれば教員やティーチング・アシスタントに尋ねること．