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

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

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

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

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

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

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

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

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

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

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

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

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

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

問題文 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] にしか影響を及ぼさないことがわか…

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

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

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

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

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

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

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

問題文 http://codeforces.com/contest/841/problem/E 問題概要 数列 {a_n} が与えられる． 任意の 1 並び替えた結果が同じものでも，並び替え方が違えば別として数えるものとする．・制約 1 1 解法 まず，掛け合わせることで平方数になってしまうという関係…

問題文 http://codeforces.com/contest/528/problem/D 問題概要 文字列 S と T が与えられる．それぞれの文字数を n, m とする． また，数 k が与えられるとする． このとき，以下の条件をみたすような位置 p の数を求めよ．すべての i (0 ・制約 1 0 文字列…

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_lexicographical 解法 まず， next_pos[i][c] := i番目以降で，文字 c があらわれる一番前の位置 とします． ここで，dp[i] を dp[i] := i 番目の文字を「使った上で」，i 番目以降のユニークな文字列は何…

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_string 解法 dp[i][j] := i 番目の文字まで見た時，同じ文字が連続している場所が j 箇所あるような場合の数 とする． 例えば，AABBBCDEE なら，連続している箇所は4箇所と数える．次に追加する文字が f[i…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0627 解法 まず首都からの最短経路を求めるほかどうしようもないので，BFSで最初に求めておく． このとき，任意の頂点について，すべての最短経路でのその頂点の親と子を求めておく． 経路…

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_ball 解法 期待値を求める問題．bitDP か線形方程式を解くところだが，|S| = 1024 なので後者は厳しい．なので bitDP を疑う．ただし、このためには遷移をDAGにしないといけない。dp[S] := すでに倒れたも…

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_tree 解法 まず，一番最初に書き始める辺を定めることを考える． そして，定めた辺を縮約したグラフ上で，以下の問題を解けば良い． 「縮約してできた頂点を根として，そこから辺を生やしていく方法は何通…

問題文 http://arc065.contest.atcoder.jp/tasks/arc065_c 解法 とりあえずマンハッタン距離の有名なテクニックである，45度回転みたいなことをする． すると，a と b の距離は D = max(|x[a] - x[b]|, |y[a] - y[b]|) となり，以降コンパスで点の位置が変わ…