オンサイトで未確認

ukuku09の活動記録。

2017-02-20から1日間の記事一覧

AOJ 0293: Algorithm Exam

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?lang=jp&id=0293 解法 割り当てとか言われたらフローを流したくなるわけだけど、やっぱり最小費用流。 会場の使い方は最悪でも 2^5 通りなので、全部試す。 次に考えるべきは、バスの距離 $D$…

AOJ 0274: Arts and Crafts

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?lang=jp&id=0274 解法 bitDP + 最小費用流。 むかし見たときは全然わからなかったけど、昨日やったら解けたのでわーい!すっごーい!(は? まず bitDP パートから。問題文に、 それぞれの課…

AtCoder Beginner Contest 003 D: AtCoder社の冬

問題文 abc003.contest.atcoder.jp 解法 いきなり X*Y の区画の上下左右すべてに、デスクまたはサーバーラックが接した配置の場合の数を数えるのは難しいので、とりあえず D 個のデスクと L 個のサーバーラックを自由に配置する場合の数を考える。これは X*Y…

AtCoder Beginner Contest 041 D: 徒競走

問題文 abc041.contest.atcoder.jp 解法 制約を見ると解法が察せる部類の問題。bitDPでやった。 各うさぎごとに、自分よりも先にゴールするうさぎのリストを持っておき、すでにゴールしたうさぎのリストと比較しながら、ゴールできるならゴールさせていく。…

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

引き続きABC埋め。 問題文 abc042.contest.atcoder.jp 解法 お絵描きするとわかる。 左上を $(0, 0)$、右下を $(H-1, W-1)$ とする。障害物がなければ、グリッド内を左上から右下へ、右移動・下移動のみで移動する経路数は、全移動(H-1+W-1 回)のなかのど…

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

一昨日のABC埋め。 問題文 abc040.contest.atcoder.jp 解法 $y_i$ の降順に全域木を作っていくと、i 本目の道路を使う直前の状態というのは、 $y_i$ 年以前の道路を含まない部分グラフとなっている。結局、初めて $w_j$ 以下となる $y_i$ の道路を使う直前の…