オンサイトで未確認

ukuku09の活動記録。

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 まで減らせる。あとは残り個数に応じてどの色のマーブルを配置するか場合分けすればよい。

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

 

 

AOJ 0293: Algorithm Exam

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?lang=jp&id=0293

 

解法

割り当てとか言われたらフローを流したくなるわけだけど、やっぱり最小費用流。

 

会場の使い方は最悪でも 2^5 通りなので、全部試す。

次に考えるべきは、バスの距離 $D$ が決まっている場合。受験者 $i$ の家と会場 $j$ との距離は $max(0, |ax_i - bx_j| + |ay_i - by_j| - D)$ で求まるので、このコストの辺を受験者と会場の間に張る。あとはソースからすべての受験者に向けて容量 1 の辺を、会場 $j$ から容量 $c_j$ の辺をシンクに張ってやると、流量 N を流してあとちょっと計算すれば答えが求まる。

で、その $D$ の決め方だが、これは二分探索で頑張る。

  • 使用する会場を決めたとき、D=i におけるそれらの会場への受験者の割り当て方のうち移動補助金が最小となるときの金額を F(i) とする。このとき、F(i+2) - F(i+1) ≥ F(i+1)-F(i) が成立する。

とかいうよくわからんことが書いてあるが、要は距離 $D$ のときと $D-1$ のときの経費の大小関係で二分探索が使えるということ(だと思う)。

フローを流しまくるので心配になったが、フローは速いのでなんとかなるっぽい。

 

AOJ 0274: Arts and Crafts

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?lang=jp&id=0274

 

解法

bitDP + 最小費用流。

むかし見たときは全然わからなかったけど、昨日やったら解けたのでわーい!すっごーい!(は?

 

まず bitDP パートから。問題文に、

  • それぞれの課題について、1回の授業でL個までの部品を購入することができる。
  • 部品を使用する順序は課題の完成に影響を与えない

と書いてあるので、D 回の授業である部品の集合を購入する最小価格を求める。順序がないので最適な買い方は部品の日ごとの費用だけで決まる。また、部品の種類はたかだか 8 種類、課題ごとに使用する同じ部品の数は最大 2 個なので、16bit の bit 列で表現できる。結局、dp[i][j][S] := i 回目の授業で j 個買ったときに S となる最小価格となる( i, j の部分の配列は使いまわせる)。

 

最小費用流パートは、課題と袋をノードにして流量 N を流すだけ。課題と袋のほかに、すべての課題とつながるソースと、すべての袋とつながるシンクを作っておく。あとは

  • 教員は、児童1人につき袋を1つだけ渡すことができる(袋を渡さない児童がいてもよい)。
  • 袋を渡された児童は、袋の中に入っている部品をすべて、自分が制作する課題に使わなければならない。

というところに気をつけて、課題と袋の間に先ほどの DP で求めた価格の辺を張る。

 

AtCoder Beginner Contest 003 D: AtCoder社の冬

問題文

abc003.contest.atcoder.jp

解法

いきなり X*Y の区画の上下左右すべてに、デスクまたはサーバーラックが接した配置の場合の数を数えるのは難しいので、とりあえず D 個のデスクと L 個のサーバーラックを自由に配置する場合の数を考える。これは X*Y から D 個選ぶ組み合わせの数と、X*Y-D から L 個選ぶ組み合わせの数の積に等しい。ここから、X*Y の区画の上下左右のいずれかまたは複数にデスクまたはサーバーラックが接していない配置の仕方の数を引いていく。

ちなみにこの式を包除原理という。この実装方法は蟻本にも載ってて、bit でエイってやるらしい。

あとは、この X*Y の区画を R*C のなかにずらして配置する分を掛け算で求めれば終わり。

 

 

AtCoder Beginner Contest 041 D: 徒競走

問題文

abc041.contest.atcoder.jp

解法

制約を見ると解法が察せる部類の問題。bitDPでやった。

各うさぎごとに、自分よりも先にゴールするうさぎのリストを持っておき、すでにゴールしたうさぎのリストと比較しながら、ゴールできるならゴールさせていく。ちょっと何を言ってるかわからないかもしれないが、僕もよくわからない(日本語が不自由なので。N の制約が 16 以下なので、各リストは bit で持つことができるので、はい。

 

AtCoder Beginner Contest 042 D: いろはちゃんとマス目

引き続きABC埋め。

 

問題文

abc042.contest.atcoder.jp

解法

お絵描きするとわかる。

左上を $(0, 0)$、右下を $(H-1, W-1)$ とする。障害物がなければ、グリッド内を左上から右下へ、右移動・下移動のみで移動する経路数は、全移動(H-1+W-1 回)のなかのどこで右に移動(W-1 回)したかの選び方に等しく、$$\frac{(H-1+W-1)!}{(W-1)!(H-1)!}$$ という組み合わせの数で求められる。

ただし、今回は下からAマス以内、左からからBマス以内には入れないので、$(0, 0)$ から $(H-A-1, i)$ と $(H-A, i)$ から $(H-1, W-1)$($B \leq i \leq W-1$)という経路に分解して数え上げる。