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

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

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

本実験の内容と狙い

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

ICPC 国内予選のチーム編成

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

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

成績評価

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

• 本授業への出席とレポートの提出は必須である．
• 一度の授業で複数回コンテストを実施する．最後に実施したコンテスト（本番コンテスト）の結果を成績評価に反映する． したがって，本番コンテストでより早く，より多くの問題について正答しているとより良い成績になる．
• 各授業の本番コンテストで，コンテストシステム上に一度でもソースコードを提出したら授業へ出席したと判定する．
  • 正答でなくとも出席と判定するので，一問も解けない場合でも何らかのソースコードを提出すること．
• 不正（レポートの剽窃等）を行った学生および不正を援助した学生は処罰される．

コンテストの前に

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

• コンテストは複数の問題から構成される．全体を眺めて解けそうな問題を選ぶ．
• 選択した問題を解くプログラムを作成する．
• 問題に付記された入出力例を使ってプログラムが正しく機能するか確かめる． 異常がなさそうであれば，プログラムのソースコードをコンテストシステムに提出する．
• コンテストシステム内で自動的にコードがコンパイルされプログラムのチェックが行われる
• 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 -

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

• IDE（Eclipse 等）にもファイルを用いた標準入出力機能があるのが普通なので，自分の開発環境でのチェック方法を調べること．

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

• コンテストサイト を開く．
• 次に，コンテストシステム（DomJudge）の使い方 を読み，自分のアカウントを作成せよ．
  • 以後のコンテストでは同じアカウントを継続して使用するので ID とパスワードを忘れないこと．
  • 一部環境ではアカウントの作成時にブラウザが停止するとの報告が去年あった．そのような場合には別のブラウザを試すこと．
• アカウントを作成してログイン後，右上に「contest:」というプルダウンメニューが表示されるので「Contest1-1」を選ぶ．
• 開始時刻になるのを待つ．
• 開始時刻になったら「実施するコンテストの基本的な流れ」で説明したとおり問題に回答する．
• 回答は上部メニュー欄の「Submit」からコンテストシステムにソースコードを提出できる．
• 回答には C（C99），C++（C++11），Java が利用できる．
• 「Scoreboard」には自分や他の学生の回答状況が表示される．
• コンテストの情報
  • 開始予定時刻：2021-05-20 ??:?? (JST) 【授業中にアナウンスします】
  • 終了時刻：2021-05-20 ??:?? (JST) 【授業中にアナウンスします】
  • コンテスト時間：約30分（アカウント作成を含む）
  • 問題数：2
• 練習コンテストの結果は成績評価の対象外である．
• コンテストの全問を解いた場合，残りの時間は自由にして良い．

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

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

例として，実行時間 0.5 [sec.]以内，記憶領域制限 64 [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("%lf\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²) のバブルソートではなく，より高速なソートアルゴリズムを使わなければならない．

実際の計算量見積もりはコーディング前に行うため， 「(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（C99），C++（C++11），Java が利用できる．
• コンテスト中にウェブ検索や書籍等を使って調べものをしても良い．
• ソースコードの雛型などの電子的準備をしても良い．
  • ただし流用して良いのは自分が書いたコードのみであり，他者が書いたコードを複写してはならない．
• 練習コンテストの結果は成績評価の対象外である．

コンテストページ

• コンテストシステム（DomJudge）の使い方
• コンテストサイト
  • 右上に「contest:」というプルダウンメニューから「Contest1-2」を選ぶ．
  • 開始予定時刻：2021-05-20 ??:?? (JST) 【授業中にアナウンスします】
  • 終了時刻：2021-05-20 ??:?? (JST) 【授業中にアナウンスします】
  • コンテスト時間：45分
  • 問題数：2
• コンテストの全問を解いた場合，残りの時間は自由にして良い．
• コンテスト中は，映像・音声による授業配信を行わない．
  • 全体に対する連絡は Discord チャンネルまたは授業ページ（このあたり）を通じて行う．
• 全体の回答状況を見て，ヒントを出す場合がある．
• 解説は次回に行う．

本日のレポート課題

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

• 提出期限は 2021-05-27 12:59（次回授業の開始直前）．
  • 期限厳守のこと（期限後のレポート提出，レポート差し替えは本当に無視します）．
  • 不完全でも可能な範囲で書いて期限内に提出すること．
• 提出は Google Classroom の「実践的・競技プログラミング（1）レポート」から行うこと．
• PDF で提出すること．
• ページサイズは A4，ページ数の上限は4ページとする（説明が十分なら1，2ページでも構わない）．
  • 「説明が十分」というのは単に自分自身が理解できるできるだけでなく，第三者を理解・納得させられる状態のこと．
• レポートの中身にはレポートタイトル，氏名，学籍番号，日付，ページ番号を含めること．
• レポートのファイル名はeメールアドレスの @ より左側の文字列で始めること．例えば hb990000_report1.pdf のようにすること．
• レポートにソースコードを含めなくても良い．ただし，説明に必要であればソースコードの部分または全体を載せても良い．
• 誤字脱字に注意し，レポートの体裁にも気を配ること．

本番コンテスト（Contest 1-3）

ルール

• すべての問題で実行時間と記憶領域の制限が設定されている． 問題ごとの制限を確認するには，コンテスト開始後に競技参加者向けのトップ画面の Problemset をクリックせよ．
• 回答には C（C99），C++（C++11），Java が利用できる．
• コンテスト中にウェブ検索や書籍等を使って調べものをしても良い．
• ソースコードの雛型などの電子的準備をしても良い．
  • ただし流用して良いのは自分が書いたコードのみであり，他者が書いたコードを複写してはならない．
• 他人に相談したり，他人にヒントを与えてはならない．
  • 問題に関する疑義照会は Discord のダイレクトメッセージを廣田宛に送ること． 間違えて全体チャットを使って他者にヒントを与えないように注意．
• 本番コンテストの結果は成績評価の対象となる．

コンテストページ

• コンテストシステム（DomJudge）の使い方
• コンテストサイト
  • 右上に「contest:」というプルダウンメニューから「Contest1-3」を選ぶ．
  • 開始予定時刻：2021-05-20 ??:?? (JST) 【授業中にアナウンスします】
  • 終了時刻：2021-05-20 ??:?? (JST) 【授業中にアナウンスします】
  • コンテスト時間：100分
  • 問題数：4
• コンテストの全問を解いた場合，残りの時間は自由にして良い．
  • 忘れないうちにレポート作成に取り掛かることを推奨．
  • レポート作成が時間内に完了したら，今度は作問してみよ．作問は問題を解くより難しい．良問をレポート付録として提出した場合には加点する（その場合は翌年度以降の問題として採用することがある）．
• コンテスト中は，映像・音声による授業配信を行わない．
  • 全体に対する連絡は Discord チャンネルまたは授業ページ（このあたり）を通じて行う．
• 全体の回答状況を見て，ヒントを出す場合がある．
• 解説は次回に行う．

予告

• 次回の本番コンテストに動的計画法を応用して回答できる問題を出題します．

付録（自習用の参考資料）

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