ICPC国内予選にチーム KazumaDragon として参加しました． チームメンバーは suibaka(僕), kazuma, nakano の3人． 結果は全体で 18 位，大学内で 2位 でした． 目標は20位以内に入ることだったので，達成できて良かったです．以下本番終了までの流れを書き…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1358 解法 終点から更新していくベルマンフォードのように解いた． まず，各頂点から a, b, c で行ける頂点を予め求めておく． d[v] := その頂点から終点に必ずたどり着けるなら，その時の…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1613&lang=jp 解法 包含関係は，一番背景連結成分を根とした木構造になっていることがわかる． よって，背景連結成分を根として，各再帰段階でBFSをするDFSを行えば，その木構造が得られる…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1615 解法 友人の助けを借りて解いた．この問題は最大流の問題に帰着させることができる．（想定解は違う方法だった．） まず，二部グラフ {V1, V2} をつくる．V1 は n 頂点からなり，各人…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2237 解法 bitDP．dp[i][S][j] := i 番目(0-indexed) の敵と j 番目のねこが戦っていて，生き残っている猫が S であるときの勝てる最大確率とする．このDPテーブルを最後の敵から最初の敵…

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_semiexp 解法 dp[i][j] := i 番目の電車まで考えた時，右端が j である (j=0: 停車, j=1: 通過) 場合の数 として更新していく． 右端で停車しない場合は単純に dp[i-1][0] + dp[i-1][1] でよい． 停車する…

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_number 解法 いわゆる桁DPというやつ． dp[i][j][lt] := 上から i 桁目まで見た時，各桁の総和の余りが j であり，かつ N 未満かどうかが lt (less than) のときの場合の数この dp だと 0 が常に条件を満…

問題文 D: サイコロ - Typical DP Contest | AtCoder 解法 サイコロの出た目の積の素因数には 2, 3, 5 しかない． つまり，D にそれ以外の素因数があればダメ． そうでなければ，D = 2^a * 3^b * 5^c と一意的に表すことができる． dp[x][y][z] := 今現在，2…

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_tournament 解法 まず各山について考える．たとえば，8人いるなら [0, 7], [0, 3], [4, 7], [0, 1], … などが各山にあたる． ある山 X に属する個人が，X の中で優勝する確率と，次に X が対戦することに…

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_game 解法 漸化式的にも解けるが，メモ化再帰で書くほうがわかりやすいかもしれない． この場合，minimax法でやる． dp[l][r] := 左の一番上が l 枚目，右の一番上が r 番目の状態から始めた時の，(その瞬…

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_contest 解法 基本的なナップサック問題． p(i), N ソースコード #include <bits/stdc++.h> using namespace std; constexpr int max_p = 10000; int main() { int n; cin >> n; vector<int> p(n); for(auto& x : p) cin >> x;</int></bits/stdc++.h>…

Typical DP Contest - Typical DP Contest | AtCoderTypical DP Contest の全ての問題の解法を書いていきたい．Typical DP Contest A - コンテスト - すいバカ日誌 Typical DP Contest B - ゲーム - すいバカ日誌 Typical DP Contest C - トーナメント - す…