読者です 読者をやめる 読者になる 読者になる

オンサイトで未確認

ukuku09の活動記録。

RUPC2017参加記

  • 前置き
  • Day 0: 移動フェーズ
  • Day 1: 立命館セット
  • Day 1.5: 懇親会 & 準備
  • Day 2: 会津セット
  •  Day 2.5: 懇親会
  • Day 3: 北大セット
  • 感想
  • ※お詫び
続きを読む

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 なので、w で昇順ソートしておくと、dp[i] = max{dp[j] | j < i かつ hj < hi}+1 となって、あとは hj < hi である箱 j のうちの最大の入れ子が高速にわかれば嬉しくなれる。

[1, hi) の最大値を求める部分に BIT を使うと全体で $O(NlogN)$ にできる。

w が等しい時は、h の降順でソートしておくと、更新の際に w が同じ箱同士が入れ子になるのを防げる(最大値を求める区間を考えるとわかる(語彙力がなかった。

 

 

AtCoder Beginner Contest 004 D: マーブル

問題文

abc004.contest.atcoder.jp

解法

箱の番号とマーブルの残り個数を状態として適当な位置からDPする。

各色を独立に考えようとすると、状態数が 2000 * 300 * 300 * 300 になってしまう。しかし、無駄な移動をしないなら、すべてのマーブルの移動後は赤・緑・青の順番で並ぶ。そのため、すべてのマーブルの残り個数をまとめて考えることで、状態数を 2000 * 300 * 3 まで減らせる。あとは残り個数に応じてどの色のマーブルを配置するか場合分けすればよい。

各マーブルの移動回数は各マーブルの移動距離と考えられるので、そこまで複雑にはならなかった。