Datalore

ACM ICPC の過去問の解答例です。授業その他で必要にせまられて作ったものを、せっかくなので公開するものです。いかなる意味においても公式のものではありません。

特に断らなけらば、プログラムはC++11で動作するものです。

プログラム例と解説

2011年

国内予選

問題文のリンク先は Aizu Online Judge です。

• 問題A チェビシェフの定理 [問題文]
  解答例

  • （推奨）エラトステネスの篩で素数判定表を作り、入力ごとに範囲内の素数を数えるプログラム
    • 素数判定表にstd::vector<bool>を使い、std::accumulateを使って素数を数えるプログラム
    • 素数判定表にstd::vector<bool>を使い、std::countを使って素数を数えるプログラム
    • 素数判定表にstd::vector<bool>を使い、std::count_ifを使って素数を数えるプログラム
  • エラトステネスの篩で素数判定表を作り、増減を追いかける方法で小さい方から順に値を求めて表を作るプログラム
    • 素数判定表にstd::vector<bool>を使うプログラム
  • 既知の素数による試し割りで素数判定して素数を昇順に生成して素数列を作り、範囲内の素数の個数を数えるプログラム
    • 素数表にstd::vector<long>を使い、std::upper_boundを使って範囲を絞るプログラム
• 問題B 世界の天秤 [問題文]
  解答例

  • std::stackを使って演算子順位法の簡略版を実装したプログラム
• 問題C 同色パネル結合 [問題文]
• 問題D そして、いくつになった？ [問題文]
• 問題E 輪番停電計画 [問題文]
• 問題F 番犬派遣会社 [問題文]
• 問題G 壊れたドア [問題文]

2012年

国内予選

問題文のリンク先は Aizu Online Judge です。

• 問題B 繰り返す10進数 [問題文]
  解答例

  • stringstreamを使って数値文字列変換を行うプログラム。10進であることを利用。
  • 桁ごとにばらしてmulisetに格納するプログラム。何進法にも対応可能。
  • 桁ごとにばらしてvectorに格納するプログラム。何進法にも対応可能。
  [解説]
• 問題C 偏りのあるサイコロ [問題文]
  解答例

  • プログラム

アジア地区予選 東京大会

問題文のリンク先は Aizu Online Judge です。

• 問題A Ginkgo Numbers [問題文]
  解答例

  • [遅い] 定義をそのまま実装したプログラム
  • 試し割法を実装したプログラム。除数を、ガウス平面の第一象限に位置し、ノルムが被除数のノルムの平方根以下であるものに限定して効率化した
  • ガウス整数がガウス素数である条件を利用して、有理整数の素数判定に帰着させたプログラム。有理整数の素数判定には試し割法を使用
  [解説]
• 問題C One-Dimensional Cellular Automaton [問題文]
  解答例

  • プログラム

2013年

アジア地区予選 東京大会

問題文のリンク先は Aizu Online Judge です。

• 問題E Dragon's Cruller [問題文]
  解答例

  • ダイクストラ法によるプログラム
  • A*アルゴリズムによるプログラム。ヒューリスティックとして 目標位置にないコマの個数×最小コスト を使用

2016年

国内予選

問題文のリンク先は Aizu Online Judge です。

• 問題A 被験者の選定 [問題文]
  解答例

  • 時間計算量Ο(n²)のプログラム
  • 時間計算量Ο(n logn)のプログラム
  • 時間計算量)Ο(n logn)のプログラム（ちょっと遅い）
  [解説]
• 問題B 当選者を探せ! [問題文]
  解答例

  • プログラム
• 問題C 竹の花 [問題文]
  解答例

  • エラトステネスの篩の変種を使用するプログラム
  • ストリーム処理風のアルゴリズムを優先度つきキューで実装したプログラム
• 問題D ダルマ落とし [問題文]
  解答例

  • 動的計画法を二回実行するプログラム
• 問題E 3D プリント [問題文]
• 問題F 文字解読 [問題文]
• 問題G ワープ航法 [問題文]
• 問題H プレゼント交換会 [問題文]

改訂作業中です。当面は国立国会図書館が保存した旧Dataloreを併用してください。