「ライブラリ検証用問題」の編集履歴（バックアップ）一覧はこちら

「ライブラリ検証用問題」(2013/04/06 (土) 18:23:21) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

*ライブラリ検証用問題

ICPC用のライブラリはコンテスト前にきちんとチェックをしておきましょう。
ICPC前にライブラリをつくるときは次のページが役に立つ可能性があります。

-[[Spaghetti Source - 各種アルゴリズムの C++ による実装>http://www.prefield.com/algorithm/]]
-[[https://github.com/nya3jp/icpc/blob/master/unknown/doc/libicpc/trunk/notebook.pdf]]
-[[http://www.incompetech.com/graphpaper/]](六角座標系や方眼紙を印刷しよう！)

***計算幾何
| 問題タイトル | 内容 |
| [[AOJ 0010 Circumscribed Circle of a Triangle>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0010&lang=jp]] | 三角形の外接円の中心と半径 |
| [[AOJ 0012 A Point in a Triangle>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0012&lang=jp]] | 点pが三角形の内部にあるかどうか |
| [[AOJ 0021 Parallelism>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0021&lang=jp]] | 2つの線分の平行判定 |
| [[AOJ 0023 Circles Intersection>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0023&lang=jp]] | 2つの円の位置関係 |
| [[AOJ 0035 Is it Convex?>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0035]] | 四角形が凸多角形かチェック |
| [[AOJ 0058 Orthogonal>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0058]] | 2つの直線の直交判定 |
| [[AOJ 0068 Enclose Pins with a Rubber Band>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0068]] | 凸包の計算 |
| [[AOJ 0079 Area of Polygon>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0079]] | 凸多角形の面積 |
| [[AOJ 0081 A Symmetric Point>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0081]] | 線対称に点を移動 |
| [[AOJ 0090 Overlaps of Seals>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0090]] | 2つの円の交点計算と点が円に含まれているかの判定 |
| [[AOJ 1050 The Last Dangion>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1050]] | ボロノイ図 |
| [[AOJ 1089 Strawberry Cake>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1089]] | Convex Cut |
| [[AOJ 1100 Area of Polygons>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1100]] | 単純多角形の面積(凸とは限らない) |
| [[AOJ 1183 Chain-Confined Path>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1183&lang=jp]] | 円と直線の交点計算 |
| [[AOJ 2201 Immortal Jewels>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2201]] | 2つの円の共通接線 |
| [[ARC #004 問題A>http://arc004.contest.atcoder.jp/tasks/arc004_1]] | 2点間の最大距離(凸多角形の直径) |


***数に関する問題
| 問題タイトル | 内容 |
| [[AOJ 0009 Prime Number>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0009&lang=jp]] | 素数 |
| [[AOJ 0044 Prime Number II>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0044]] | 素数 |
| [[AOJ 0053 Sum of Prime Numbers>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0053]] | 素数 |
| [[AOJ 0005 GCD and LCM>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0005&lang=jp]] | 最大公約数・最小公倍数 |
| [[AOJ 0015 National Budget>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0015&lang=jp]] | Big Integerの足し算 |
| [[ARC #007 問題D>http://arc007.contest.atcoder.jp/tasks/arc007_4]] | Big Integerの足し算・引き算 |
| [[AOJ 0022 Maximum Sum Sequence>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0022&lang=jp]] | 連続する部分列で最大の総和, 累積和, しゃくとり法 |
| [[AOJ 0027 What day is today?>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0027&lang=jp]] | 2004年m月d日の曜日, ツェラーの公式 |
| [[ARC #002 問題B>http://arc002.contest.atcoder.jp/tasks/arc002_2]] | 日付を進める |

***組合せ・順列
| 問題タイトル | 内容 |
| [[AOJ 0030 Sum of Integers>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0030&lang=jp]] | 組合せの列挙 |
| [[AOJ 2361 Sort>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2361]] | 順列の生成 |
| [[ARC #001 問題C>http://arc001.contest.atcoder.jp/tasks/arc001_3]] | 順列の生成 |
| [[ARC #009 問題C>http://arc009.contest.atcoder.jp/tasks/arc009_3]] | 順列の生成(smallだけ) |

***最小全域木(プリム法、クラスカル法)
| 問題タイトル | 内容 |
| [[AOJ 0180 Stellar Performance of the Debunkey Family>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0180]] | 最小全域木 |

***負の閉路の検出(ベルマンフォード法、ワーシャルフロイド法)
| [[AOJ 1169 The Most Powerful Spell>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1169&lang=jp]] |
| [[AOJ 2207 Consistet Unit System>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2207]] |

***サイコロに関する問題
| [[AOJ 1057 Rolling Dice>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1057&lang=jp]] | サイコロ+ダイクストラ法 |
| [[AOJ 1181 Biased Dice>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1181&lang=jp]] | サイコロ |

***Union-Find
| [[AOJ 1016 Fibonacci Sets>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1016]] |
| [[AOJ 2364 Lucky Dip>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2364]] |
| [[ARC #006 問題D>http://arc006.contest.atcoder.jp/tasks/arc006_4]] |
| [[AutumnFest 2012 問題B>http://autumn_fest.contest.atcoder.jp/tasks/autumn_fest_02]] |

***ネットワークフロー
| [[AOJ 1088 School Excursion>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1088]] | 最小費用流 |
| [[AOJ 1163 Cards>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1163&lang=jp]] | 二部グラフのマッチング |

***三分探索
| [[AOJ 1093 KND Runs for Sweets>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1093]] |

*ライブラリ検証用問題

ICPC用のライブラリはコンテスト前にきちんとチェックをしておきましょう。
ICPC前にライブラリをつくるときは次のページが役に立つ可能性があります。

-[[Spaghetti Source - 各種アルゴリズムの C++ による実装>http://www.prefield.com/algorithm/]]
-[[https://github.com/nya3jp/icpc/blob/master/unknown/doc/libicpc/trunk/notebook.pdf]]
-[[http://www.incompetech.com/graphpaper/]](六角座標系や方眼紙を印刷しよう！)

***計算幾何
| 問題タイトル | 内容 |
| [[AOJ 0010 Circumscribed Circle of a Triangle>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0010&lang=jp]] | 三角形の外接円の中心と半径 |
| [[AOJ 0012 A Point in a Triangle>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0012&lang=jp]] | 点pが三角形の内部にあるかどうか |
| [[AOJ 0021 Parallelism>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0021&lang=jp]] | 2つの線分の平行判定 |
| [[AOJ 0023 Circles Intersection>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0023&lang=jp]] | 2つの円の位置関係 |
| [[AOJ 0035 Is it Convex?>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0035]] | 四角形が凸多角形かチェック |
| [[AOJ 0058 Orthogonal>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0058]] | 2つの直線の直交判定 |
| [[AOJ 0068 Enclose Pins with a Rubber Band>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0068]] | 凸包の計算 |
| [[AOJ 0079 Area of Polygon>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0079]] | 凸多角形の面積 |
| [[AOJ 0081 A Symmetric Point>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0081]] | 線対称に点を移動 |
| [[AOJ 0090 Overlaps of Seals>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0090]] | 2つの円の交点計算と点が円に含まれているかの判定 |
| [[AOJ 1050 The Last Dangion>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1050]] | ボロノイ図 |
| [[AOJ 1089 Strawberry Cake>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1089]] | Convex Cut |
| [[AOJ 1100 Area of Polygons>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1100]] | 単純多角形の面積(凸とは限らない) |
| [[AOJ 1183 Chain-Confined Path>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1183&lang=jp]] | 円と直線の交点計算 |
| [[AOJ 2201 Immortal Jewels>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2201]] | 2つの円の共通接線 |
| [[ARC #004 問題A>http://arc004.contest.atcoder.jp/tasks/arc004_1]] | 2点間の最大距離(凸多角形の直径) |


***数に関する問題
| 問題タイトル | 内容 |
| [[AOJ 0009 Prime Number>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0009&lang=jp]] | 素数 |
| [[AOJ 0044 Prime Number II>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0044]] | 素数 |
| [[AOJ 0053 Sum of Prime Numbers>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0053]] | 素数 |
| [[AOJ 0005 GCD and LCM>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0005&lang=jp]] | 最大公約数・最小公倍数 |
| [[AOJ 0015 National Budget>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0015&lang=jp]] | Big Integerの足し算 |
| [[ARC #007 問題D>http://arc007.contest.atcoder.jp/tasks/arc007_4]] | Big Integerの足し算・引き算 |
| [[AOJ 0022 Maximum Sum Sequence>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0022&lang=jp]] | 連続する部分列で最大の総和, 累積和, しゃくとり法 |
| [[AOJ 0027 What day is today?>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0027&lang=jp]] | 2004年m月d日の曜日, ツェラーの公式 |
| [[AOJ 0098 Maximum Sum Sequence II>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0098]] | 二次元累積和 |
| [[ARC #002 問題B>http://arc002.contest.atcoder.jp/tasks/arc002_2]] | 日付を進める |

***組合せ・順列
| 問題タイトル | 内容 |
| [[AOJ 0030 Sum of Integers>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0030&lang=jp]] | 組合せの列挙 |
| [[AOJ 2361 Sort>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2361]] | 順列の生成 |
| [[ARC #001 問題C>http://arc001.contest.atcoder.jp/tasks/arc001_3]] | 順列の生成 |
| [[ARC #009 問題C>http://arc009.contest.atcoder.jp/tasks/arc009_3]] | 順列の生成(smallだけ) |

***最小全域木(プリム法、クラスカル法)
| 問題タイトル | 内容 |
| [[AOJ 0180 Stellar Performance of the Debunkey Family>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0180]] | 最小全域木 |

***負の閉路の検出(ベルマンフォード法、ワーシャルフロイド法)
| [[AOJ 1169 The Most Powerful Spell>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1169&lang=jp]] |
| [[AOJ 2207 Consistet Unit System>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2207]] |

***サイコロに関する問題
| [[AOJ 1057 Rolling Dice>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1057&lang=jp]] | サイコロ+ダイクストラ法 |
| [[AOJ 1181 Biased Dice>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1181&lang=jp]] | サイコロ |

***Union-Find
| [[AOJ 1016 Fibonacci Sets>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1016]] |
| [[AOJ 2364 Lucky Dip>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2364]] |
| [[ARC #006 問題D>http://arc006.contest.atcoder.jp/tasks/arc006_4]] |
| [[AutumnFest 2012 問題B>http://autumn_fest.contest.atcoder.jp/tasks/autumn_fest_02]] |

***ネットワークフロー
| [[AOJ 1088 School Excursion>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1088]] | 最小費用流 |
| [[AOJ 1163 Cards>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1163&lang=jp]] | 二部グラフのマッチング |

***三分探索
| [[AOJ 1093 KND Runs for Sweets>http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1093]] |