オンサイトで未確認

ukuku09の活動記録。

† ACM-ICPC 2017 国内予選 参加記 †

前置き 私は大悪魔、胡桃沢=ウクニキア=マクドウェル…。今日は我が力を世界に知らしめるための第一歩として、ICPC2017国内予選に参加してきたわ! ちなみに結果はこんな感じよ!↓ …ふっふっふ、なぁーはっはっはぁー!6完で8位!どう?!これが我がチーム…

AOJ 2370: RabbitWalking

久しぶりにブログを書くわ!自分用メモだけど。 問題概要 RabbitWalking | Aizu Online Judge 解法 まず"-1"の判定ですが、グラフが奇閉路を含まないことと二部グラフであることは必要十分条件なので、与えられたグラフの各連結成分が二部グラフであるかどう…

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 …

AtCoder Beginner Contest 004 D: マーブル

問題文 abc004.contest.atcoder.jp 解法 箱の番号とマーブルの残り個数を状態として適当な位置からDPする。 各色を独立に考えようとすると、状態数が 2000 * 300 * 300 * 300 になってしまう。しかし、無駄な移動をしないなら、すべてのマーブルの移動後は赤…

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$ の道路を使う直前の…

AtCoder Beginner Contest 034 D: 食塩水

ABC埋め続き。 問題文 abc034.contest.atcoder.jp 解法 貪欲に混ぜるとダメ。 水:食塩の比率が同じ2つの食塩があるときは、水が少ないほうを優先的に入れたほうが、全体の濃度を薄める効果が小さい(=最終的な濃度を大きくできる)。みたいに考えていると…

AtCoder Beginner Contest 023 D: 射撃王

ABC埋め。 問題文 abc023.contest.atcoder.jp 解法 制約的に $O(NlogN)$ くらいかなぁってなるので、二分探索をする。 風船のペナルティの最大値を x とすると、各風船がそこに到達するまでの時間は、 $$T_i = (x - H_i) / S_i$$ で求められる。あとは、この…

AtCoder Beginner Contest 051 D: Candidates of No Shortest Paths

ABC埋め中。 問題文 abc051.contest.atcoder.jp 解法 Warshall-Floyd で全頂点間の最短経路を求めて、与えられたエッジの端点間の最短経路重みがエッジの重みより小さくなっているかどうかを判定するだけで、そのエッジがグラフ上のいずれかの最短経路上に含…

AtCoder Beginner Contest 054 D: Mixing Experiment

2月なのでABC埋め。記事は自分用なのであんまりタメにならなそう。 問題文 abc054.contest.atcoder.jp 解法 制約がそんなに大きくないので01ナップザックっぽく解いた。 dp[i][j][k]:=薬品 i-1 まででタイプAが j グラム、タイプBが k グラムの溶液を作る最…

ごどく部活動記録【海外遠征編】ACM-ICPC 2016 バンコク大会 参加記

初海外!初海外ですよ!!(ひきこもり並感 ということで、ごどく部の遠征も兼ねて、ICPCバンコク大会に参加してきました。 「バンコクの黒板w」 「なんかそれすごく惜しい感じがする」 「はい。」 www.acm-icpc.eng.chula.ac.th

ACM-ICPC 2016 国内予選 敗戦記

先日のICPC国内予選に、チームmochinochaの一員として参加しました。 結果は4完26位、惜しくも予選敗退でした。。。 国内予選の順位表はこちら↓ 順位と結果 | ACM-ICPC 2016 Asia Tsukuba Regional