Hatena::ブログ(Diary)

kyuridenamidaのチラ裏

2011-10-09

頻出典型アルゴリズムの演習問題としてよさげなやつ

効率的な別解とか存在する問題もあるけど演習によさそうなやつをピックアップ。

そのアルゴリズムじゃないと解けないわけではないって問題も多いので注意。(ただ演習するのには都合が良いかなと)

※個人的難易度をつけてみました。とても主観的な難易度付けなので気にせず解いてみてください。

随時追加更新します

・(10/10 04:31) ワーシャルフロイド法を使うのが適切そうな2題追加

・(10/10 04:33) 深さ優先探索が寂しかったので1題追加

・(10/10 04:??) 最小全域木が寂しかったので2題追加

・(10/24) 深さ優先探索っぽいの追加(幅優先でもよい問題だが)



深さ優先探索

Ball[☆](効率的な別解もあり)

Sum of Integers[☆]

The Number of Island[☆]

Block[★]

Sergeant Rian[★★☆]

Property Distribution[★] (幅優先探索でも何でも解ける)

幅優先探索

Mysterious Worm[★]

Cheese[★]

Seven Puzzle[★☆]

Stray Twins[★★]

Deven-Eleven[★★]

Summer of Phyonkichi[★★☆]

ワーシャルフロイド法(For 全点対最短路問題)

Traveling Alone: One-way Ticket of Youth[★]

A reward for a Carpenter[★]

Convenient Location[★☆]

Boat Travel[★★]

Water Pipe Construction[★★★]

ダイクストラ法(For 単一始点最短路問題)

Highway Express Bus[★★]

Pachimon Creature[★★★☆] (どちらかというとDP解法がおすすめ)

Aizu Buried Treasure[★★★☆]

JOI2010-2011本選(問3)[★★★]

ベルマンフォード法(For 単一始点最短路問題)

Bicycle Diet[★★★]

プリム法/クラスカル法(For 最小全域木問題)

Carden Lantern[★☆]

Stellar Performance of the Debunkey Family[★☆]

Computation of Minimum Length of Pipeline[★★★]

Finals(2010年度JOI春合宿)[★★☆] ←間違えてContestって問題になってたので訂正

オイラー閉路

Patrol[★]

Kobutanukitsuneko[★★☆]

最大のヒストグラム中の長方形求めてゴニョゴニョするやつ

(参考:ALGORITHM NOTE ヒストグラム中の最大の長方形の面積)

Rectangular Searching[★★]

3494 -- Largest Submatrix of All 1’s[★★]

座標圧縮

Paint Color[★★☆]

包除原理(追加してみた 10/09-15:13)

2407 -- Relatives[★★]

SRM491 D2H(要ログイン)[★★★]

a_kawashiroa_kawashiro 2011/10/09 07:56 いい記事だと思う

roxion1377roxion1377 2011/10/10 10:09 幅優先なりワーシャルフロイドなり
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0144

tozangezantozangezan 2011/10/10 12:12 JOI合宿のコンテスト、最小全域木かどうかはおいといて2010年だと思います(Finalsの間違い?)

kyuridenamidakyuridenamida 2011/10/10 12:50 あまちがえてた>tozangezan

refiuterefiute 2011/10/24 20:44 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0118
これとか深さ優先にどうでしょう?

raven38raven38 2014/05/04 18:16 ありがたいです

square1001square1001 2015/12/18 17:57 深さ優先探索の AOJ 0033 - "Balls" は "Ball" だと思います.

kyuridenamidakyuridenamida 2015/12/18 18:22 >square1001さん
ありがとうございます.修正しました.

square1001square1001 2016/04/13 13:22 Paint Color, 座標圧縮しなくても通りました
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1649803#1

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証