TopCoder SRM 632

2014-09-05 | [Competitive programming]

300

長さが 1 のときは自明に可能．

長さが 2 以上のときは，少なくとも 0 と 0 以外が交互に現れる必要がある． それを満たしているときは，0 以外だけ取り出し，それぞれ 1 だけ引いたものが可能かどうかを再帰的に判定．

500

辺の capacity が 3^i と激しい差があることを用いる．

capacity が大きい辺から見ていく． 辺を使えることにしてもグラフが連結にならない場合は，単につなげておく． 連結になる場合は，その辺を通るフローをめいっぱい流す．めいっぱい流したのでグラフは結局連結にならない． めいっぱい流しても，他の辺は容量が著しく大きいので他の辺は無視してよい．

900

ある連続した線の引き方において，y 座標を変えない時，その引き方中に現れる端点たちは「同じ連結成分」に属するとよぶことにする． y 座標を変える線たちを取り払うと，重要なのは「上下のそれぞれで，連結成分を k 個作るような点の訪れ方は何通りあるか」になる． これを上下で適当に組み合わせると答えになる．

点が 1 個だけのところから連結成分たちを作ること考える． このとき，行える操作は「最後に訪れた点のすぐ左か右に新たな点を作り，そこへ行く」か「点 1 つからなる新たな連結成分を作り，そこへ移動する」のどちらかである． この構成法で訪れる順番を逆にすると，有効な訪れ方のすべてが得られる． （連結成分が変わる場合は明らかで，左右に移動する場合は，その後に新たな点が間に加えられたとしても，順番を逆にして訪れるので すでに間の点は訪れられているので，問題がない）

結局，dp[i][j] = dp[i-1][j] * 2 + dp[i-1][j] * i として，dp[N][K] により K 個の連結成分の場合の数が求められる．

結果

500 で「mod を取り忘れている」ことに気づいて resubmit (>_<)

同じミスをしている人がいたので challenge して +50

ooo +50 940.74 14 位

rating: 2975 -> 2990