問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_knapsack 解法 まず，色でソートしておく． すると以下の dp が書ける． dp[i][w][j][k] := i 番目まで見たとき，j 種類の色を使っていて，最後に使った色が k であって，重さの総和が w となるときの最大…

問題文 http://arc081.contest.atcoder.jp/tasks/arc081_c 解法 今見ている位置から後ろの，各アルファベットの最も近い位置を持っておく． すると，今見ている頂点から始めた時，以降の部分列で現れない最小のものを求めることができる． 各アルファベット…

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_cat 解法 1 1つは今見ているのが何番目かに使うとして，もう1つを何にするかが問題．自分は，どの猫まで距離1以内に配置するか，と考えた．つまり dp[i][j] := i 番目の猫まで考えた時，i 番目の猫は"自分…

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_iwi 解法 区間DP．dp[l][r] := [l, r) で最大何文字取り除けるか と定義する． まず，dp[l][r] = max(dp[l][i] + dp[i][r]) (i = l, ..., r) という遷移は，明らかだと思う． あとは，s[l...r) が完全に取…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2751 問題概要 2つのチーム（X と Y と呼ぶことにする）が，合計 A + B + C 回試合を行った． A は X が勝利した回数 B は Y が勝利した回数，C は引き分けた回数である． また，X と Y は…

問題文 http://arc044.contest.atcoder.jp/tasks/arc044_c 解法 この問題のポイントは，独立した部分問題に分割してしまう，ということ．よく考えると，縦方向の移動と横方向の移動は完全に独立して扱うことができることがわかる． なので，問題を1次元の同…

問題文 http://arc054.contest.atcoder.jp/tasks/arc054_c 解法 2部グラフの完全マッチングの個数の偶奇性を問う問題． 当然数え上げるのは大変．しかし偶奇だけなら，行列式でわかる．与えられた隣接行列を Aとする． すると，完全マッチングの個数 M は，A…

問題文 http://arc050.contest.atcoder.jp/tasks/arc050_c 解法 1 が A 桁続いたものと，1 が B 桁続いたものの最大公約数 G は，1 が gcd(A, B) 桁続いたものになる． 例えば 111111 (A = 6) と 1111 (B = 4) の最大公約数は，1 が gcd(6, 4) = 2桁続いたも…

問題文 http://arc055.contest.atcoder.jp/tasks/arc055_b 解法 dp[i][j][ate_max] := i 番目まで見て，j 個食べていて，現時点で最大のものを食べている(ate_max: bool) 状態から始めたとき，最終的に N を食べられる確率 と定義する． dp[N][j][1] が，確…

問題文 http://codeforces.com/contest/516/problem/D 問題概要 木 T が与えられる．また，クエリが q 回投げられる．それぞれのクエリは L を投げてくる． 木 T の頂点 i に対して，i からそこから最も遠い葉までの距離を D(i) とする． 各クエリに対し，T …

問題文 http://joisc2015.contest.atcoder.jp/tasks/joisc2015_a 問題概要 文字列 S が与えられる． S に対して，クエリが N 個投げられる． 各クエリは A, B, C を持ち，これは S の部分文字列 [A, B) を位置 C の直前にコピー挿入することを意味する． 最…

問題文 https://csacademy.com/contest/archive/task/xor-closure/ 問題概要 N 項からなる数列 {a_n} が与えられる．この数列にいくつか数を追加して，以下の性質を満たすようにする． 相異なる任意の i, j に対して，a_i XOR a_j もまた数列 {a_n} に含まれ…

問題文 http://arc025.contest.atcoder.jp/tasks/arc025_3 解法 制約をみて，なんとなく全頂点を始点としてダイクストラできるなーと検討はつく． とりあえず，目的地を決め打ちしてしまって，目的地を始点にダイクストラする． その後，得られた距離 d[i] …

問題文 http://arc035.contest.atcoder.jp/tasks/arc035_c 解法 頂点数が小さいので，ワーシャルフロイドでよい． ただし，建設するたびにワーシャルフロイドすると間に合わない．よく考えると，x-y 間に橋を作ったときに最短経路が変わるのは，x-yを経由す…

問題文 http://arc023.contest.atcoder.jp/tasks/arc023_3 解法 典型 of 典型みたいな問題．L -1 -1 ... -1 R みたいな区間に分けて考えて，R - L を -1 にうまく分配するという問題になる． これはいわゆる重複組合せというやつ．高校数学でも頻出． という…

問題文 http://codeforces.com/contest/679/problem/B 問題概要 整数 m があたえられる．m 以下の整数 X で，以下を満たす (n, X) を求める． X を超えない最大の a^3 （立方数）を選び，X = X - a^3 と更新する． X に対して上記の操作を繰り返す． 上記の…

問題文 http://agc004.contest.atcoder.jp/tasks/agc004_d 解法 首都が自己辺でなければならないのは，すぐ分かる．（ぱっとわからなくても実験すればわかるようになってる．） あとは制約から，与えられたグラフが首都を根とする木になっていることがわかる…

問題文 http://codeforces.com/contest/698/problem/C 解法 10^100なので実質無限大の時間がたったと考えて良い． 正規マルコフだし，十分大きな時間が経過したあとは定常状態に落ち着く． この時，過渡状態にいる確率はほぼ0で，キャッシュは（できるかぎり…

問題文 http://codeforces.com/contest/587/problem/E 問題概要 n 個の数からなる数列 {a_n} が与えられる． また，q 個のクエリが投げられるものとする．クエリは以下の2種類． ただし，以降は + を XOR, * を AND とする． 1. l 2. a_l, ..., a_r からいく…

問題文 http://arc006.contest.atcoder.jp/tasks/arc006_3 解法 貪欲解で解くひとが多いと思うので，それ以外の解法を． この問題は，よく考えると「与えられたDAGの最小パス被覆を求めよ」と言い換えられる． 実際，x が y の上に積める，を y -> x という…

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 番目の状態から始めた時の，(その瞬…