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

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

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

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

随時追加更新します

・(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(要ログイン)[★★★]