mayoko’s diary

プロコンとかいろいろ。

2016-02-09から1日間の記事一覧

Educational Codeforces Round 1 E. Chocolate Bar

問題 codeforces.com 解法 落ち着いて dp すれば良いです。dp[n][m][k] = (n*m の長方形で, ぴったり k 個の square を作るには最低いくつのコストが必要か?) を考えます。分割の仕方は 縦に切るか横に切るかしかなく, 2 つに分割した長方形に対して, 一方…

SRM 531 div1 med: MonsterFarm

問題 TopCoder Statistics - Problem Statement 解法 まず強連結成分分解して, グラフを DAG にします。この DAG において, 終点(その頂点から辺が伸びていないような頂点)への行き方が何通りあるか, というのが, 答えが -1 でない場合の答になります。これ…

SRM 531 div1 easy: NoRepeatPlaylist

問題 TopCoder Statistics - Problem Statement 解法 包除原理で解きました。i 個以下の曲を使って P 曲を並べる場合, 最初の曲は i 通り, 次の曲は i-1 通り, ..., M 曲目は i-M 通り, となり, それ以後は i-M 通りだけ使える曲があります。i 個の曲の選び…