2017-09-18から1日間の記事一覧

AOJ 2617 Air Pollution

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2617 解法 この問題を解く上でポイントとなるのは,大気を循環させたときに,(p[i-1], p[i], p[i+1]) の累積和が不変であるということです.今大気の状態が (a, b, c, d) であるとしましょ…

ARC058 E - 和風いろはちゃん

問題文 http://arc058.contest.atcoder.jp/tasks/arc058_c 解法 X, Y, Z が小さいので bitDP でやります. dp[i][S] := i 番目まで見たときに,直前の和が X + Y + Z 以下になるところまでの状態が S であるような場合の数 とします. たとえば,X = 5, Y = …

AOJ 1301 Malfatti Circles

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1301 解法 まず,一つの円を決め打ちします. すると,残りの2円の位置は,二分探索などをして求めることが出来ます. ここで,残りの2円が離れすぎている場合,最初に決め打ちした円が小…

ARC067 E - Grouping

問題文 http://arc067.contest.atcoder.jp/tasks/arc067_c 解法 dp[i + 1][j] := i 人以下のグループのみを用いて,あと j 人グループ分けされてない人がいるときの場合の数 という dp で解けます. 遷移は,use == 0 または C $$\displaystyle dp[i + 1][j …