競プロ

AOJ 1338 Clock Hands

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1338 解法 まず,それぞれの針がなす角を求めましょう.短針が1周するのに$H$時間かかるとします. 今時刻が $h:m:s$ である時,針が上を向いている状態を 0 度とすると,長針,短針,秒針…

ARC057 D - 全域木

問題文 http://arc057.contest.atcoder.jp/tasks/arc057_d 解法 メモ化再帰で解きます. $rec(C) := $連結成分の状態が $C$ であるような状態から始めたときに,条件を満たすような辺の張り方の総数$A[i]$ を小さい方から張って順に張っていくとき,$A[i]$に…

AOJ 2436 Card

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2436 解法 カードの数字同士を足すわけではなくそのまま並べるので,桁に注目したいなーという気持ちになります. しかも $a[i]$ は高々4桁なので嬉しいです.こういう問題は,すべての数…

AOJ 2725 Live Programming

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2725 問題概要 催し物を時間 $T$ だけ開催することになった. そこで歌う歌の候補が $N$ 個あり,それぞれの歌はパラメーター $t[i], p[i], f[i]$ を持つ.$t[i]$ は歌の長さ,$p[i]$ は歌…

Codeforces Round #185 (Div. 1) B. Cats Transport

問題文 http://codeforces.com/problemset/problem/311/B 問題概要 N個の地点があり,順に 0 から N-1 とする.地点 i と i + 1 の間の距離は d[i] である. また,猫が m 匹いて,猫 j は時刻 t[j] に地点 h[j] にあらわれるものとする.それぞれの猫は,餌…

AOJ 2606 Perm Query

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2606 解法 まず,制約を読むと,ある項についてたかだか40回の遷移で元に戻ることがわかるので,愚直にこれを求めます. このとき,それぞれの項が c[i] 回 で元に戻るとします. すると,…

AOJ 2617 Air Pollution

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2617 解法 この問題を解く上でポイントとなるのは,大気を循環させたときに,(p[i-1], p[i], p[i+1]) の累積和が不変であるということです.今大気の状態が (a, b, c, d) であるとしましょ…

ARC058 E - 和風いろはちゃん

問題文 http://arc058.contest.atcoder.jp/tasks/arc058_c 解法 X, Y, Z が小さいので bitDP でやります. dp[i][S] := i 番目まで見たときに,直前の和が X + Y + Z 以下になるところまでの状態が S であるような場合の数 とします. たとえば,X = 5, Y = …

AOJ 1301 Malfatti Circles

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1301 解法 まず,一つの円を決め打ちします. すると,残りの2円の位置は,二分探索などをして求めることが出来ます. ここで,残りの2円が離れすぎている場合,最初に決め打ちした円が小…

ARC067 E - Grouping

問題文 http://arc067.contest.atcoder.jp/tasks/arc067_c 解法 dp[i + 1][j] := i 人以下のグループのみを用いて,あと j 人グループ分けされてない人がいるときの場合の数 という dp で解けます. 遷移は,use == 0 または C $$\displaystyle dp[i + 1][j …

AOJ 2309 Vector Compression

問題文 まず問題読解が難しかった. http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2309 問題概要 N次元のベクトルが M 個与えられる.これを v[1], ..., v[M] とする. M 個のベクトルを好きな順番に並べ替え,その順に記録していく.記録する…

AOJ 2446 Enumeration

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2446&lang=jp 解法 簡単のために,試しに2つの数字 a, b を用意して考えてみます.a, b が選ばれる確率をそれぞれ p, q とします. まず,a のみを選んだ場合の期待値は, (m / a) * p * (…

Codeforces Round #230 (Div.1) B. Tower of Hanoi

問題文 http://codeforces.com/contest/392/problem/B 問題概要 ハノイの塔のパズルの最小手数は 2^n - 1 であることは有名な事実であるが,今回は以下の問題を考えるとする. ある段を位置 i から位置 j に移すのにコストが t[i][j] かかるとするとき( 1 ・…

AOJ 2611 Ordering

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2611&lang=jp 解法 問題文を丁寧に読まなければならない問題です. 「それぞれの塔は自分自身よりも大きな塔とは高々1回しか比較されていない」とあるので,与えられた関係 (a, b) を有向…

ACPC2014 Day2 I Hard Beans

問題文 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2014Day2&pid=I 解法 WaveletMatrixで殴ると通ります. 具体的には,区間の何番目の値が D との大小関係の境界になっているか quantile で二分探索するだけです. ソースコード #inc…

Codeforces Round #433 (Div. 2) D. Jury Meeting

問題文 http://codeforces.com/contest/853/problem/B 問題概要 街が n + 1 あり,それぞれナンバリングされている.また人が n 人いて,人 i は街 i に存在する.0番目の街は首都であり,人はいない. ここで,飛行機のスケジュールが m 個与えられる.スケ…

AOJ 2372 IkaNumber

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2372 解法 問題文を言い換えると,フィボナッチ数同士の積で表される数で K 番目に小さいものは何か?という問題です. 実験すればなんとなく規則性が見えてきます. 自分は fib(n) * fib(…

AOJ 2159 Symmetry

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2159 問題概要 点が N 個与えられる.これらすべての点で,自己交差しないように辺を結ぶことで線対称な多角形を構成できるか判定せよ. ただし,点は多角形の順番(反時計回り or 時計回…

Typical DP Contest Q - 連結

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_concatenation 解法 同じ文字列を複数選んでも良いので,何を使ったかを保存する必要はないです. 今作っている文字列の状態がどうか,がわかれば十分.そこで突然ですが,以下のような dp をします. dp[…

AOJ 2336 Spring Tiles

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2336 解法 最適な戦略を取った場合,各マスの移動は確率的に決まるわけではなく,ある基準によってバネに向かうかゴールに直接向かうか定まっているはずです. 問題はなにが基準なのかです…

Typical DP Contest R - グラフ

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_graph 解法 どう考えても閉路は一つにまとめたいな~という気持ちになるので,とりあえずSCCしたあとのDAGの上で解くことを考えます. 一番端っこから引いていくのが当然良いので,トポロジカルソートして…

Typical DP Contest P - うなぎ

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_eel 解法 木の上でのDPなので,やはり根を適当に決めたあとのDFS木上で,部分木の結果を統合していくのが鉄則となります.根として適当に頂点 0 を選んで,そのDFS木上で考えます. 以下のような dp を考…

AOJ 0636 フェーン現象(Foehn Phenomena)

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0636&lang=jp 解法 B[i] = A[i] - A[i + 1] という数列 B[i] を考えるのが良いです. すると,A[l] から A[r] の変化が x だとすると,B[l - 1] と B[r] にしか影響を及ぼさないことがわか…

TopCoder SRM 720 Div1 Easy SumProduct

問題文 リンクがまだない 問題概要 あなたは 0 から 9 までの数字をそれぞれ a[i] 個使えるとします. これらの数字から,A 桁の数字 X と B 桁の数字 Y の2つの数字を作るとします. このとき,考えられる (X, Y) について,X * Y の総和を求めなさい. た…

Typical DP Contest T - フィボナッチ

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_fibonacci 解法 今なら,通称きたまさ法とよばれている方法でやります. きたまさ法自体の説明は省略します.アイデアとしては,一般項を最初の K 項の線形結合で表そう,というものです. ソースコード #…

Typical DP Contest S - マス目

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_grid 解法 まず,この問題を解くにあたって以下の記事を大いに参考にさせていただきました.ありがとうございます. algoogle.hadrori.jpH が小さいので,それぞれのマスの連結関係をもちながら,列を左か…

Typical DP Contest M - 家

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_house 解法 まず階段を使うまえに,各階で部屋i -> j の移動経路が何パターンあるかを計算します. これは普通に dp[S][i][j] := 今まで訪れた部屋の集合が S である,i -> j の移動パターン とすれば求め…

Codeforces Round #238 (Div. 1) D. Hill Climbing

問題文 http://codeforces.com/problemset/problem/406/D 問題概要 山が一直線上に n 山ならんでいる.それぞれの山の座標は x[i],高さは y[i] である. 山と山にはスロープがかかっている.スロープは以下のようにかかっている. 各山 a は,a の頂上から…

Typical DP Contest K - ターゲット

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_target 解法 それぞれの円の左端と右端のpairである (x + r, x - r) を昇順ソートする. そのあと,-(x - r) についての最長増加部分列( (x - r) のまま考えるなら,最長減少部分列.右から左の向き)を…

Codeforces Round #313 (Div. 1) C. Gerald and Giant Chess

問題文 http://codeforces.com/contest/559/problem/C 問題概要 H * W のグリッドがある. このグリッドのうち,ある N マスは使えないようになっている. この時,左上から右下まで行く方法は何通りあるか.ただし,マスを移動するときは,右または下にしか…