Codeforces

Codeforces Round #213 (Div. 1) D. Ghd

問題文 https://codeforces.com/contest/364/problem/D 解答 https://github.com/Suikaba/procon-solved/blob/master/Codeforces/Round200-249/Round213/Div1-D.cpp 感想 計算量と TL の割に配列サイズでかすぎない?

Lindström–Gessel–Viennot lemma

概要 格子点上で、n 組の始点と終点 $(a_1, a_2, \ldots, a_n), (b_1, b_2, \ldots, b_n)$ が定まっているとして、それらが交差しないようなパスの選び方をカウントできる定理である。($a_i$ をどの $b_j$ と対応付けるか、まで含めて。) 後にこの定理を用…

Codeforces Round #320 (Div.1) C. Weakness and Poorness

* 問題文 http://codeforces.com/contest/578/problem/C 解法 max 取ってるし、x についての weakness を f(x) とすると、下に凸な関数になりそう。 なので3分探索する。 x を決めたときの a[i] - x 列の区間和最大、最小は線形で解ける。 左から累積和を見…

Codeforces Round #319 (Div.1) B. Invariance of Tree

問題文 http://codeforces.com/contest/576/problem/B 解法 自分は直感で、どうせ p に周期3以上のサイクルがあると困るんじゃないの、みたいに考えた。 周期3以上のサイクル内部で辺を張るとループができて困るので、そういう意味では正しい。 また、2つの…

Bubble Cup 8 - Finals G. Run for beer

問題文 http://codeforces.com/contest/575/problem/G 解法 1ステップごとにコストが10倍になり、かつ辺のコストは高々9であることから、通った道を前から見て10進表記したものがコストなので、できるだけ短いほうがいいことにはすぐ気がつく。同じ長さなら…

Codeforces Round #322 (Div.2) F. Zublicanes and Mumocrates

問題文 http://codeforces.com/contest/581/problem/F 解法 (知っていれば)二乗の木DPっぽいな~となり、実際そうである。 ひとまず普通に木DPをする。 dp[v][cnt][c] := v の部分木だけ考えて、その中の葉を cnt だけ黒く塗り、v の色が c であるときの最…

Codeforces Round #318 (Div.1) B. Bear and Blocks

問題文 http://codeforces.com/contest/573/problem/B 解法 1ステップ後の h[i] の高さは min(h[i - 1], h[i] - 1, h[i + 1]) になる。 一般化して、k ステップ後の h[i] の高さは min(h[i - k], h[i - k + 1] - 1, ..., h[i] - k, ..., h[i + k]) になる。 …

VK Cup 2015 - Finals A. Matching Names

問題文 http://codeforces.com/contest/566/problem/A 問題概要 n 個の名前と、n 個のペンネームが与えられる。これらを1対1対応させることを考える。 名前 a とペンネーム b をペアにした時の満足度を lcp(a, b) と定義する。 lcp(a, b) の総和が最大となる…

Codeforces Round #316 (Div.2) E. Pig and Palindromes

問題文 http://codeforces.com/contest/570/problem/E 解法 前と後ろの状態を同時に持たないことにはどうしようもなさそうだが、愚直に持つとオーダーが悪い。 よく考えると、現状態から i ステップ後の位置は、列か行の位置のどちらか一方を持てばもう一方…

Codeforces Round #316 (Div.2) D. Tree Requests

問題文 http://codeforces.com/contest/570/problem/D 解法 部分木の特定の高さのノードだけ取り出すのもオイラーツアーでできる。 この場合は高さごとにノードを管理すればよい。 各ノードが持つ区間は普通のオイラーツアーと同じで、各高さごとに持つデー…

Codeforces Round #310 (Div.1) E - Case of Computer Network

問題文 http://codeforces.com/contest/555/problem/E 解法 二重辺連結成分分解をしてくださいと書いてあるので、先にやっておく。 ただし、与えられるグラフは単純グラフとは限らないので、多重辺にも対応しておく。 するとグラフは森になるので、結局木の…

Codeforces Round #309 (Div.1) D. Nudist Beach

問題文 http://codeforces.com/contest/553/problem/D 解法 二分探索して BFS で解ける。 最大化したい値を例えば仮に x とおく。 最初、使える集合 S には k 頂点以外のすべての頂点を入れておく。 queue には使えなくなった頂点(初期は k 頂点)を入れる…

Codeforces Round #307 (Div.2) E. GukiZ and GukiZiana

問題文 http://codeforces.com/contest/551/problem/E 解法 平方分割.まあそれはそうだよね. 実装方法はいろいろありそうだけど,10秒制限が意外と厳しいので,map とか set はできるだけ使わないほうが良い. 各塊は2つ目のクエリに答えるために,(val, i…

Codeforces Round #307 (Div.2) D. GukiZ and Binary Operations

問題文 http://codeforces.com/contest/551/problem/D 解法 結論をいうと行列累乗で解ける. まず重要なポイントとして,各ビットは独立に考えて良い(全く同じ条件なので). つまり,結局この問題は1ビットの問題に帰着される. 1ビットの n 個の整数を,…

Codeforces Round #305 (Div.1) C. Mike and Foam

問題文 http://codeforces.com/contest/547/problem/C 解法 与えられた値を素因数分解して出てくる素数の数は高々6個しかない. gcd を考えるときはこれだけで十分である. 今回は直接答えを求めず,gcd(a, b) != 1 となる個数を求めて最後にトータルから引…

Codeforces Round #305 (Div.1) B. Mike and Feet

問題文 解法1 値の大きい方から追加していって,区間やその幅をset, multiset で管理して頑張るだけ. 実装が悲しい感じになる. ソースコード1 #include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; constexpr int inf = 1e9; int main() { int n; cin >> n; </int,></bits/stdc++.h>…

Codeforces Round #305 (Div.1) A. Mike and Frog

問題文 http://codeforces.com/contest/547/problem/A 解法 mod を取っているので,それぞれ高々 m 回でループするのはすぐわかる. とりあえずそれぞれについて目的の高さになるまで愚直にシミュレートする. この時到達できないならそもそも不可能なので -…

Codeforces Round #302 (Div.1) C. Remembering Strings

問題文 http://codeforces.com/contest/543/problem/C 解法 n それは,a-z の26文字より小さいので,各文字は1箇所変更するだけで easy to remember にできるということ. つまり,ある文字列 i を easy to remember にするには,以下のどちらかしかない. …

VK Cup 2015 - Round 3 F. Quest

問題文 http://codeforces.com/contest/542/problem/F 解法 DPで解ける. dp[i][j] := 高さ i に存在するノードが j 個であるようなときの,価値の最大値 とする. ある高さ i のときに考えるべきタスクは,実はコストが T - i であるものだけでよい. なぜ…

Codeforces Round #491 (Div.2) F. Concise and clear

問題文 http://codeforces.com/contest/991/problem/F 解法 冪乗の形を使っていかに短くできるか,という問題. まず,n * m (n, m はただの自然数)のような表現は完全に不利. 例えば 99 * 99 を考えてみるとわかりやすいが,そのまま出力したほうが短い…

Codeforces Round #176 (Div.1) E. Ladies' Shop

問題文 http://codeforces.com/problemset/problem/286/E 解法 FFT. まず,答えの集合から生成できる任意の重さは,ある2個以下のカバンを使って(同じカバンを2つでもいい)作ることができる. なぜなら,もしある重さを p1 + p2 + p3 で生成したとする.…

Helvetic Coding Contest 2018 E2. Guard Duty (medium)

問題文 http://codeforces.com/contest/958/problem/E2 解説 わからなかったので上位陣のコードから解法を得た. とりあえずソートして隣接項の差を作ると,以下の問題になる.n - 1 要素からなる数列から,k 個えらんでその和を最小化せよ.ただし,隣接2要…

Codeforces I. Photo Processing (2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest)

問題文 http://codeforces.com/problemset/problem/883/I 解法 求めたい値は二分探索で求めましょう. あとはある x にたいして題意を満たす分割が可能か調べます. 写真の値はソートしておくと,題意の分割は連続部分列の分割になります. その上で,以下の…

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 個からなる文字列の前半(ないし後半)に対応する頂点をもつグラフをつくる. それぞれのアルファベットから,文字列…

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] にあらわれるものとする.それぞれの猫は,餌…

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 ・…

Codeforces Round #433 (Div. 2) D. Jury Meeting

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