問題文 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]|) となり，以降コンパスで点の位置が変わ…

問題文 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桁続いたも…