ICPC 重要問題集

ICPC用の重要問題を分野別に集め、ポイントをコメントしていきましょう。 いずれ重要アルゴリズム集を作るときの参考になるように。

• 探索問題
  • 国内予選2000B http://icpc.score.is.tsukuba.ac.jp/problems/B.html
    • DFS
  • PKU1915 http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1915
    • BFS

• 動的計画法
  • PKU1458 http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1458
    • 最長共通部分列

• グラフ理論
  • 国内予選2003D http://www.u-aizu.ac.jp/conference/ACM/results/D.html
    • 最小全域木 -Kruskalのアルゴリズム or Primのアルゴリズム-

• 文字列処理
  • PKU1917 http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1917
    • 正規表現を利用した処理

• 構文解析
  • PKU1460 http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1460
    • 四則演算の式の解釈 -LL(1)に基づく構文解析ルーチンの設計-
  • 国内予選1998 3 http://www.acm-japan.org/past-icpc/domestic1998/problem3.htm
    • 複素数の加減乗算の式の解釈

• 計算幾何
  • 国内予選2004D http://ccserv.adm.ehime-u.ac.jp/ICPC/problems/domestic/d2004/D.jp/D.html
    • 円による点の包含