AGC001 C - Shorten Diameter

問題文 https://agc001.contest.atcoder.jp/tasks/agc001_c 解法 解説と(ちょっとだけ)違ったので一応書いておきます. まずBFSで全点対最短路を求めておいて,頂点 v から K より離れた頂点の数を sz[v] とします. あとは sz[v] の大きい方から貪欲に削…

Codeforces Round #407 (Div. 2) D. Weird journey

問題文 http://codeforces.com/contest/789/problem/D 解法 まず,同じ辺を2回通るパスという時点でオイラーツアーが思い浮かびます. 自己辺を考えるのはめんどうなので,とりあえずない場合を考えると,条件を満たすパスがあるかどうかは,「一度のDFSによ…

Codeforces Round #404 (Div.2) E. Anton and Permutation

問題文 http://codeforces.com/contest/785/problem/E 解法 平方分割 + 2次元BITで解いた.[0...m] x [0...n] で二次元.m は n / sqrt(n). l[i] から r[i] の間に完全に含まれているブロックは BIT 上で計算し,端っこの部分は生で持っている配列を使って…

Codeforces Round #404 (Div.2) D. Anton and School - 2

問題文 http://codeforces.com/contest/785/problem/D 解法 条件に合う部分列の,一番右端の "(" の位置を総当りして計算します. その位置から左に(その位置自体も含めて)"(" が $x$ 個あり,右に ")" が $y$ 個ある時,求める答えは $\displaystyle \sum…

Codeforces ECR #31 F. Anti-Palindromize

問題文 http://codeforces.com/contest/884/problem/F 解法 最小費用流で解ける. まず,各アルファベットに対応する26個の頂点と,N / 2 個からなる文字列の前半(ないし後半)に対応する頂点をもつグラフをつくる. それぞれのアルファベットから,文字列…

AOJ 2294 Entangled with Lottery

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2294 解法 ゴールから見るDPでやります.dp[i][j][k] := 高さ (H から) i まで見た時に,位置 j にいて,それまでに猫が k 本引いているような確率とします. 高さ 1 から i までに,うさ…

AOJ 2556 Integer in Integer

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2556 解法 やり方は色々あると思うんですが,僕は桁DPっぽくやりました(正直実装方針かなりミスっていると思う.)まず,[0..N] までの答え f(N) を求めることができれば,f(B) - f(A - 1…

AOJ 2614 Almost Same Substring

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2614 解法 ローリングハッシュでやります.同じ長さの文字列 S, T に対して,「左からみて何文字一致しているか」と「右からみて何文字一致しているか」をそれぞれ二分探索で求めます. も…

AOJ 2605 Social Monsters

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2605 解法 制約をよく読むと,(使えない辺を含める)与えられたグラフにおける各連結成分は,1つのパスまたは閉路になっていることがわかります. 各連結成分において計算して,最後にま…

AOJ 2449 Connect

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2449 解法 これは典型問題です. $i$ 行目の $j$ 番目に文字を置くかどうか考えた時に関係してくるのは,$i$ 行目の $1$ から $j - 1$ 列目と,$i - 1$ 行目の $j$ から $C$ 列目だけです…

AOJ 2376 Disconnected Game

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2376 解法 石取りゲームだからいい感じにわかるんでは?と思ったけどよくわかんなかったのでメモ化再帰で解きます.勝ちが決まるタイミングはは,連結成分の数が2であり,かつ自分の手番で…

AOJ 2313 Box Witch

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2313 解法 ちゃんとフローがわかってるなら解ける問題. まず辺の追加クエリは簡単で,単純に辺を増やすだけ. 問題は辺の削除クエリです.与えられた辺を $\{a, b\}$ とします. 今流れて…

AOJ 2344 Multi Ending Story

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2344 解法 木DPで解きます. まず部分木に注目しましょう. 冷静に考えると,この部分木のすべての葉を回収するのには,以下の3通りだけしかありません.この部分木の根を $v$,左右の子を…

AOJ 2598 Website Tour

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2598 解法 移動に時間がかからないので,各強連結成分においては,好きな広告を(制限以内なら)好きな回数だけ見ることが出来ます.これは典型的な個数制限付きナップザック問題です.あ…

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 個与えられる.スケ…