競プロ

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] := その頂点から終点に必ずたどり着けるなら,その時の…

AOJ 1613 Deciphering Characters

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1613&lang=jp 解法 包含関係は,一番背景連結成分を根とした木構造になっていることがわかる. よって,背景連結成分を根として,各再帰段階でBFSをするDFSを行えば,その木構造が得られる…

AOJ 1615 Gift Exchange Party

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1615 解法 友人の助けを借りて解いた.この問題は最大流の問題に帰着させることができる.(想定解は違う方法だった.) まず,二部グラフ {V1, V2} をつくる.V1 は n 頂点からなり,各人…

AOJ 2237 The Castle

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2237 解法 bitDP.dp[i][S][j] := i 番目(0-indexed) の敵と j 番目のねこが戦っていて,生き残っている猫が S であるときの勝てる最大確率とする.このDPテーブルを最後の敵から最初の敵…

Typical DP Contest F - 準急

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_semiexp 解法 dp[i][j] := i 番目の電車まで考えた時,右端が j である (j=0: 停車, j=1: 通過) 場合の数 として更新していく. 右端で停車しない場合は単純に dp[i-1][0] + dp[i-1][1] でよい. 停車する…

Typical DP Contest E - 数

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_number 解法 いわゆる桁DPというやつ. dp[i][j][leq] := 下から i 桁目まで見た時,各桁の総和の余りが j であり,かつ N 以下である可能性がある (less equal) 場合の数 としておいて,遷移をする. こ…

Typical DP Contest D - サイコロ

問題文 D: サイコロ - Typical DP Contest | AtCoder 解法 サイコロの出た目の積の素因数には 2, 3, 5 しかない. つまり,D にそれ以外の素因数があればダメ. そうでなければ,D = 2^a * 3^b * 5^c と一意的に表すことができる. dp[x][y][z] := 今現在,2…

Typical DP Contest C - トーナメント

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_tournament 解法 まず各山について考える.たとえば,8人いるなら [0, 7], [0, 3], [4, 7], [0, 1], … などが各山にあたる. ある山 X に属する個人が,X の中で優勝する確率と,次に X が対戦することに…

Typical DP Contest B - ゲーム

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_game 解法 漸化式的にも解けるが,メモ化再帰で書くほうがわかりやすいかもしれない. この場合,minimax法でやる. memo[l][r] := 左の一番上が l 枚目,右の一番上が r 番目の状態から始めた時の,(先手…

Typical DP Contest A - コンテスト

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_contest 解法 基本的なナップサック問題. p(i), N ソースコード #include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; vector<int> p(N); for(int i=0; i<N; ++i) { cin >> p[i]; } vector<bool> dp(10001); dp[0] = true;</bool></n;></int></bits/stdc++.h>…

Typical DP Contest まとめ

Typical DP Contest の全ての問題の解法を書いていきたい.Typical DP Contest A - コンテスト - すいバカ日誌 Typical DP Contest B - ゲーム - すいバカ日誌 Typical DP Contest C - トーナメント - すいバカ日誌 Typical DP Contest D - サイコロ - すい…

AOJ 1359 Wall Clocks

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1359 解法 各点から半直線が2本出て,長方形の周上の2点で交わるが,それをそのまま処理すると面倒. なので,(0, 0) -> (0, d) -> (w, d) -> (w, 0) -> (0, 0) という4辺を展開して,[0, …

AOJ 1348 Space Golf

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1348 解法 完全にやるだけ.多少無駄なことをしても入力サイズが小さいので余裕で通る. ご丁寧に式が書かれているので,それに従って候補を全部列挙し,それらが条件をみたすか(つまり接触…

AOJ 2334 Roads on Towns

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2334 解法 実は,A->B と C->D の少なくともどちらか一方は,直接結んでしまって良いことがわかる.そうすればあとは最短経路問題.以下は自分のイメージ. 例えば図のように,(解が存在し…

AOJ 2592 Flowers

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2592 解法 3分探索.(自分は黄金比探索を持ってたのでそれを貼り付けた.) 使う水の量が決まれば,使う肥料の量は一位に定まる.つまり,コスト関数はWのみを引数とする関数である. グラ…

AOJ 2595 Cookie Counter

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2595 解法 1枚も食べない日を考えるとややこしい(し,Dがでかいのでそのまま求められない)ので,D 日のうち一枚も食べない日はあとで決めることにすればよい. つまり,まずは一日に最低…

AOJ 2570 Shipura

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2570 解法 > が >> なのか S の > なのかは,数字またはSの直前かどうかで判定ができる. なので最初に式を後ろから見ていって,どれがシフト演算なのか確定させておく. それができればあと…

AOJ 2512 Ononokomachi's Edit War

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2512 解法 適当に置換 or 削除でminimax法だと明らかに間に合わないので,すこし考える必要がある. 冷静に考えると,N が偶数のときは2ターン,N が奇数のときは1ターンやるのと変わらない…

AOJ 2255 6/2(1+2)

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2255 解法 BNFどおりに実装する必要はなくて,区間DPをすればよい. その区間で取りうる値の集合を持たせておく. 区間 [l..r] の演算子を全て見ていって [l..i-1] と [i+1..r] に分ける. …

AOJ 1350 There is No Alternative

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1350 問題概要 連結グラフ G が与えられる.一般に G の最小全域木は複数存在しうる.G のすべての最小全域木に必ず含まれている辺を求めよ.・制約 3 N-1 解法 最小全域木 T を一つ求める.…

AOJ 1330 Never Wait for Weights

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1330 解法 基本は union-find をいじるだけ. 各ノードは,親からの相対重さを持つ. クエリで a, b, w が与えられたとする. a と b の代表元が異なる場合は,それぞれの集合の根を r1, r2…

AOJ 1318 Long Distance Taxi

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1318 解法 単純に d[街の番号][残りのガソリン] で通ってしまって悲しいので,少し違う方針で. まず,ガソリンスタンドについたら満タンにしてしまっていいので,ガソリンスタンドから cap …

Codeforces Round #361 (Div. 2) D. Friends and Subsequences

問題文 http://codeforces.com/contest/689/problem/D 問題概要 長さ N の数列 A, B が与えられる. max{A(l), ..., A(r)} = min{B(l), ... B(r)} となる (l, r) (l ・制約 1 解法 Sparse table を書いてみたのでそのテストに使った.なので Sparse table で…

AOJ 2726 Black Company

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2726 問題概要 N 人の従業員がいて,それぞれ成果を c(i) あげたとする.成果に応じて,報酬 p(i) を分配する. ただし,それぞれの従業員には親しい人が何人か存在する. 従業員 i が j と…

AOJ 2680 LR

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2680 解法 メモ化再帰.memo[l][r] で,s[l..r]の取りうる最大値,もし無ければ "invalid" を入れていく. 完全に数字に置き換えられるならそうして(当然それが最適),そうじゃないならLかR…

AOJ 2710 An Equation in a Mine

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2710 解法 区間DP(メモ化再帰). ある演算子に注目して,左と右に分けて,再帰的に処理していくとよい. 演算子が + であれば,左も右も最大値を取るようにすればよい.-であれば,左を…

AOJ 2741 Invisible

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2741 解法 メモ化再帰で解ける. memo[si][sj][i][j][turn][pass] := a(si)からa(i-1),b(sj)からb(j-1)までスタックに積まれていて,手番がturnかつパスの状態がpassであるときの最大値.(p…

AOJ 0575 Festivals in JOI Kingdom

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0575 解法 実装できなかったので,eagletmt さんの解法を参考にした. AOJ 0575 - Festivals in JOI Kingdom - プログラミングコンテストの記録使うアルゴリズムとしては,DijkstraとKruskal…

AOJ 0519 Worst Reporter

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0519 解法 a が b に勝利したことを,a -> b と有向辺で表現することにすれば,この問題はトポロジカル順序を求める問題になる. トポロジカル順序が求まったら,その頂点列のなかで隣り合っ…

AOJ 0526 Boat Travel

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0526 解法 基本はワーシャルフロイドだが,それだと間に合わないので工夫する. 仮に島a, b間の船舶が更新された時,グラフ上の異なる2つの島u, vの最短経路は, u -> a -> b -> v つまり d[…

AOJ 0562 Shopping in JOI Kingdom

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0562 解法 まず,各頂点がショッピングモールからどれだけ離れているかを求める. これは,ショッピングモールの頂点をあらかじめ全てpriority_queueに突っ込んでおいたダイクストラを解けば…

AOJ 0623 Zombie Island

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0623 解法 危険な街を列挙さえすれば,あとはただの単一始点最短路問題. 危険な街を列挙するには,ゾンビに支配された街を全て,最初にqueueにプッシュしておくだけで十分である.計算量…

AOJ 0616 JOI Park

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0616 解法 まず,0を始点としてダイクストラで,各点への最短路重みを求めておく. そして,その重みで頂点をソートしておく.また,あらかじめ辺全体の重みの総和を求めておく. Xの候補…

AOJ 0600 Baumkuchen

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0600 解法 累積和と二分探索. まず,バウムクーヘンの累積和を二周分求めておく. その後,左端を適当に定め,そこから始めて長さが (lb + ub) / 2 以上になるところを2分探索で求める.…

AOJ 0509 Sheets

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0509 問題概要 平面座標に n 個の長方形がある.重なっていることもある. それらがつくる図形の面積と,周の長さを求めよ.・制約 1 長方形の左下,右上の座標の x, y 座標は,共に 0 以…