オンサイトで未確認

ukuku09の活動記録。

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$)という経路に分解して数え上げる。

 

 

AtCoder Beginner Contest 040 D: 道路の老朽化対策について

一昨日のABC埋め。

 

問題文

abc040.contest.atcoder.jp

解法

$y_i$ の降順に全域木を作っていくと、i 本目の道路を使う直前の状態というのは、 $y_i$ 年以前の道路を含まない部分グラフとなっている。結局、初めて $w_j$ 以下となる $y_i$ の道路を使う直前の部分グラフの大きさが、各クエリの答えとなる。クエリを先読みして $w_j$ でソートしておくと、Kruskal 法で全域木を作る過程でうまく答えを求められる。

全域木となった時点で、任意の異なる2都市間を移動することができるようになるので、その他の道路については考えなくても良い。

 

余談

これICPC直前のABCで、大学でチームメンバーと一緒に出た(もちろん個人戦)記憶があるなぁ。あの時はこれ解けなかったけど。

 

AtCoder Beginner Contest 034 D: 食塩水

ABC埋め続き。

 

問題文

abc034.contest.atcoder.jp

解法

貪欲に混ぜるとダメ。

水:食塩の比率が同じ2つの食塩があるときは、水が少ないほうを優先的に入れたほうが、全体の濃度を薄める効果が小さい(=最終的な濃度を大きくできる)。みたいに考えていると、瞬間を見ながら解を求めるのではなく、全体(目指すべき濃度)を見て、ある食塩水がその結果に及ぼす影響を考えればよさそうという気持ちになる。

食塩水 i を構成する水量を $w_i$、食塩量を $q_i$ として、目指すべき濃度を総水量 $W$ と総食塩量 $Q$ を使って $\frac{Q}{W}$ と表すことにする。この時、食塩水 i が全体に及ぼす影響 $e_i$ は、

$$e_i = q_i - \frac{Q}{W} * w_i$$

  • $e_i < 0$ のとき、濃度を下げる
  • $e_i = 0$ のとき、濃度を変化させない
  • $e_i > 0$ のとき、濃度を上げる

となる。式の意味がわからなかったら $q_i - \frac{Q}{W} * w_i = 0$ の式を整理するとなんとなくわかるかもしれない。

今回はできるだけ濃くしたいので、目指すべき濃度より高くなるように食塩水を選んでいく。濃度 $X$ より高い食塩水が作れるなら、同じ作り方で濃度 $X-1$ より高い食塩水が作れるわけだから、目指すべき濃度の設定には二分探索が使える。

 

余談

昨日から思ってたけど、日本語が不自由だ。

AtCoder Beginner Contest 023 D: 射撃王

ABC埋め。

 

問題文

abc023.contest.atcoder.jp

解法

制約的に $O(NlogN)$ くらいかなぁってなるので、二分探索をする。

風船のペナルティの最大値を x とすると、各風船がそこに到達するまでの時間は、

$$T_i = (x - H_i) / S_i$$

で求められる。あとは、この時間が短い順に全ての風船を N 秒間で割っていった時に、各風船 i を Ti 秒以内に割ることができるかどうかを見てやるだけでいい。

解の取りうる最大値が大きいので一見やばそうに見えるけど二分探索は神なので余裕。

結局 $O(Nlog(max(H_i+S_i*N)))$ くらい。