いつも通り一完 問題 Easy TopCoder Statistics - Problem Statement 解法 が小さい時はDPで簡単に求めることができる。 よく考えたり実験したりすると、DPのテーブルはループしていそう。 ループの周期を求めてもいいのだが、周期はあまり長くならなそうな…

サークルで解いた 問題 C: THE☆たこ焼き祭り2012 - AtCoder Regular Contest 008 | AtCoder 解法 全員に対しての最短経路を求めておいて、遠い人から順に配っていけばよい。 自分に対してはすぐに配れることに注意する。（で1秒以内に配れる場合など） sourc…

アジア地区の前日（だった）。 問題 Audition | Aizu Online Judge 問題概要 省略 解法 DP。 それぞれの種目別に、何回アピールを行うかを分けて考える。 ある種目について、アピールを行う回数を決めておくと、各アイドルに勝てる確率を求めることができる…

問題 Network Reliability | Aizu Online Judge 問題概要 無向グラフが与えられる。 それぞれの辺は一定確率で消える。 グラフが連結である確率を求めよ。 解法 dp。 := 頂点集合が連結である確率 とする。 のとき である。 のうちある頂点をとし、をを含む…

実装軽いやつ 問題 Tree Reconstruction | Aizu Online Judge 問題概要 各連結成分が強連結なグラフが与えられる。 各頂点について、入ってくる辺と出ていく辺の重みが等しくなるようにすると、 一部の辺の重みを隠しても復元することができる。 最大でいく…

解ける問題がなくなってきた。 問題 Box Witch | Aizu Online Judge 問題概要 省略 解法 全頂点対に容量0の辺を張っておく。 最初から辺があるものについては容量1にしておき、最大流を求めておく。以下、この残余グラフ上で考える。 追加のクエリが来たら、…

問題を解くのをさぼると死ぬ 問題 Reverse a Road II | Aizu Online Judge 問題概要 各辺の容量がの有向グラフが与えられる。 辺を一本だけ反転させ、 間の最大流を増加させられるか。 可能な場合はそのような辺は何本あるか。 解法 まず最大流を流し、残余…

問題 Texas hold 'em | Aizu Online Judge 問題概要 それぞれのプレイヤーは2枚ずつ非公開のカードを持っていて、場に3枚のカードが公開されている。 ここからさらに2枚のカードを公開し、自分のカードと場のカードの7枚から5枚を選び、手の強さを競う（手の…