競プロ

Codeforces Round #429 (Div. 2) E. On the Bench

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

Codeforces Round #296 (Div.1) D. Fuzzy Search

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

Typical DP Contest G - 辞書順

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

Typical DP Contest O - 文字列

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

AOJ 0627 Train Fare (鉄道運賃)

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

Typical DP Contest J - ボール

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_ball 解法 期待値を求める問題.bitDP か線形方程式を解くところだが,|S| = 1024 なので後者は厳しい.なので bitDP でやる.dp[S] := すでに倒れたものが S の状態である時からはじめて,すべてのものを…

Typical DP Contest N - 木

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

ARC065 E - へんなコンパス

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

Typical DP Contest H - ナップザック

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

ARC081 E - Don't Be a Subsequence

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

Typical DP Contest L - 猫

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

Typical DP Contest 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) が完全に取…

AOJ 2751 BaseBall (野球観戦)

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

ARC044 C - ビーム

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

ARC054 C - たい焼き

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

ARC050 C - LCM 111

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

ARC055 B - せんべい

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

Codeforces Round #292 (Div. 1) D. Drazil and Morning Exercise

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

JOI 春合宿2015 コピー&ペースト2

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

CSAcademy - Xor Closure

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

ARC025 C - ウサギとカメ

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

ARC035 C - アットコーダー王国の交通事情

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

ARC023 C - タコヤ木

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

Codeforces Round #356 (Div. 1) B. Bear and Tower of Cubes

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

AGC004 D - Teleporter

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

Codeforces Round #363 (Div. 1) C. LRU

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

Codeforces Round #326 (Div.1) E. Duff as a Queen

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

ARC006 C - 積み重ね

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

ACM-ICPC 2017 国内予選 参加記

ICPC国内予選にチーム KazumaDragon として参加しました. チームメンバーは suibaka(僕), kazuma, nakano の3人. 結果は全体で 18 位,大学内で 2位 でした. 目標は20位以内に入ることだったので,達成できて良かったです.以下本番終了までの流れを書き…

AOJ 1358 Sibling Rivalry

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1358 解法 終点から更新していくベルマンフォードのように解いた. まず,各頂点から a, b, c で行ける頂点を予め求めておく. d[v] := その頂点から終点に必ずたどり着けるなら,その時の…