オンサイトで未確認

ukuku09の活動記録。

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

AtCoder Beginner Contest 007 D: 禁止された数字

問題文 abc007.contest.atcoder.jp 解法 桁DPしてくださいという問題。桁DPがわからない人は pekempey さんの記事がとてつもなくわかりやすいのでそちらを見てください。 pekempey.hatenablog.com

AtCoder Beginner Contest 008 D: 金塊ゲーム

問題文 abc008.contest.atcoder.jp 解法 問題文が無駄に長くてわかりづらいが、よくあるやつだと思った。 ある装置を起動させると、その装置を基準に領域が最大4つ(左上・左下・右上・右下)に分割されるので、そのそれぞれについて再帰的に調べていけば良…

AtCoder Beginner Contest 006 D: トランプ挿入ソート

問題文 abc006.contest.atcoder.jp 解法 抜き取らないトランプに注目すると、それらは増加数列になっているはずなので、最長増加部分列を求めて全体から引いた数が答え。

AtCoder Beginner Contest 010 D: 浮気予防

問題文 abc010.contest.atcoder.jp 解法 サンプルのグラフを見ると「あー最小カット」という気分になるので最小カット。最大流-最小カット定理より、最大流のアルゴリズムそのままで最小カットの問題も解ける。

AtCoder Beginner Contest 038 D: プレゼント

問題文 abc038.contest.atcoder.jp 解法 dp[i] := i 番目の箱を最も外側に使う時の最大の入れ子の数 でDPする。しかし、普通にやると、その箱に入る箱を探すのを含めて $O(N^2)$ になってしまう。 DPの遷移は、dp[i] = max{dp[j] | wj < wi かつ hj < hi}+1 …