スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

ライブラリチェックに使える問題集

Competitive Programming Advent Calendar Div2013 17 日目の記事です。

競技プログラミングでは自分だけのライブラリを作っている人はたくさんいます。
典型アルゴリズムをあらかじめ書いてまとめておくことで、コンテストでそれを使う問題が出題されたときにスムーズに解答することができます。
この記事では、ライブラリのベリファイに使える問題リストをまとめようと思います。

既存のもの

この記事と似た趣旨のものは既に web 上にいくつか存在しています。
親切な方々に Twitter 上で教えてもらいました。ありがとうございます。
まずはこれらを簡単に紹介します。

○ Aizu Online Judge > COURSE > Library
http://judge.u-aizu.ac.jp/onlinejudge/course.jsp#library
ジャンル分けされたいくつかの有名問題に挑戦することができます。ちょっと変わったところでは、最小有向全域木などもあります。
ジャッジ不可になっているものも多いので、今後、コンテンツの充実に期待したいところです。

○ ぼくのかんがえたさいきょうのきからいぶらり(2)
http://topcoder.g.hatena.ne.jp/not522/20121214
not さんによる、みんなで問題やデータセットを出し合ってライブラリベリファイしよう、という試みです。計算幾何に関しては not さんが雛形を示してくれています。
> ここにpull requestしていただければ問題集が充実してみんな幸せになれます。
とのことなのでみなさん参加しましょう。宣伝。
これが十分充実すればこの記事は用済みになりますね……

○ PKU Online Judge POJ classification of the most widely circulated, and hope will cut the (transfer)
http://www.codeweblog.com/pku-online-judge-poj-classification-of-the-most-widely-circulated-and-hope-will-cut-the-transfer/
中国語の翻訳元ページは http://bbs.pediy.com/showthread.php?t=123253
Peking Online Judge に収録されている一部の問題をジャンルごとにまとめたページです。

○ UVA toolkit
http://uvatoolkit.com/problemssolve.php
UVa Online Judge に収録されている一部の問題をジャンルごとにまとめたページです。キーワードで検索もできます。

○ UVa Online Judge > AOAPC, Competitive Programming 1~3
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8 の下 5 つ
UVa に収録されている比較的基本的な問題がジャンル分けされてまとめられています。
ライブラリチェックというよりは、特定のジャンルの基礎固めみたいなことに向いているかもしれません。

○ LightOJ
http://lightoj.com/index.php
バングラデシュ産のオンラインジャッジです。今は 434 問が収録されています。
すべての問題が細かくジャンル分けされており、ライブラリベリファイの用途にも使えます。
ただし、次のような欠点があるので注意が必要です:
・アカウントを作らないと何もできない
・本名でのアカウント作成を推奨しており、明らかに人名っぽくないアカウントは、中の人に見つかり次第 "(send full name to lightoj.mod@gmail.com)" さんに改名させられる
アニメキャラの名前で登録してる人もいますが・・・どうなんでしょうか。

ライブラリベリファイ問題集 頻出編

比較的コンテストでよく使われる、あるいは非常に有名なアルゴリズムを扱います。
上に挙げたページに載っている問題はできるだけ扱わないようにしています。
なるべくアルゴリズムを知っていれば瞬殺できる問題 / コードを貼るだけで解ける問題をピックアップしていますが、一部そうじゃないものもあるのでネタバレは自己責任ということでお願いします。

○ さいころ
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0198
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1253

○ 最大流
http://poj.org/problem?id=1273
http://poj.org/problem?id=1459
http://poj.org/problem?id=3155 (流量が実数)
http://www.spoj.com/problems/FASTFLOW/ (N≦5000, M≦30000)

○ 最小費用流
http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1535

○ 二部グラフの最小費用マッチング
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2429
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1687 (整数容量, 実数コスト)

○ Suffix Array 構築
http://www.spoj.com/problems/SARRAY/

○ 最長共通部分文字列
http://poj.org/problem?id=2217
http://www.spoj.com/problems/LCS/
http://www.spoj.com/problems/LCS2/ (文字列三つ以上もあり)

○ Manacher
http://www.spoj.com/problems/NUMOFPAL/

○ 最近点対
http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1186 (N≦10000)
http://www.spoj.com/problems/CPP/ (N≦30000)
http://www.spoj.com/problems/CLOPPAIR/ (N≦50000)

○ 最小包含円
http://www.spoj.com/problems/QCJ4/

○ 巡回行列
http://poj.org/problem?id=3150
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3335

ライブラリベリファイ問題集 趣味編

持っててもほとんど使わないようなマニアックなものを扱います。ただの趣味です。

○ ルービックキューブ
http://poj.org/problem?id=1290
http://poj.org/problem?id=1955

○ 正二十面体
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1319

○ 離散対数
http://poj.org/problem?id=2417
http://poj.org/problem?id=3243 (MOD が合成数)

○ 多倍長実数
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3844

○ 無向グラフの全域最小カット
http://poj.org/problem?id=2914
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1930

○ 最小シュタイナー木
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1040

○ 高速フーリエ変換
http://www.spoj.com/problems/MUL/
http://jag2013spring.contest.atcoder.jp/tasks/icpc2013spring_f (二次元 FFT)

○ 一般グラフの最大マッチング
http://www.codechef.com/JUNE11/problems/MINESREV/
http://www.codechef.com/problems/ENCODE09

○ 線形計画問題
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1439
http://www.numerical.rl.ac.uk/cute/netlib.html

以上で終わりです。
これはと思ったものがあれば利用していただければ幸いです。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。