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]) になる。 …

AOJ 2850 Endless BFS

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2850 解法 01BFSで解いた。 まず、2部グラフだと永遠に終わらないことはわかる。 2部グラフじゃない場合、どこかのタイミングで隣接2頂点が同時に current に入り、そこからそれらの頂点は…

AOJ 2847 Ninja Map

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2847 解法 まず一行目を適当に埋める。次数が 2 の頂点を見つけて、そこから隣接する中で一番小さい次数の頂点をたどっていけば自然に一行埋められる。 一行目が埋まると、下の行の数は一…

AOJ 2858 Prime-Factor Prime

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2858 解法 区間篩の要領で解ける。 [1, 1e5] ぐらいまでの素数を普通に篩で検出し、素数が見つかれば [L, R] にカウントを割り振っていく。 今回の場合は、素数 p が検出できたら、[L, R] …

AOJ 2593 Square in Circles

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2593 解法 辺の長さをまず決め打つと、それぞれの円と交わる部分が区間として求まる。 得られた区間の連結な部分の総長さで、決めうった値よりも長い所があれば、そのような正方形を配置す…

AOJ 1620 Boolean Expression Compressor

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1620 解法 前もってすべての式を生成してしまえばOK。 真理値表は 16bit 分の情報があればよく、bitDP 的な要領で生成していけば良い。 つまり、キーが真理値表で、値がその最小長さである…

AOJ 2373 HullMarathon

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2373 解法 自分は数式で捉えて、ラグランジュの未定乗数法で解いた。 ラグランジュの未定乗数法については以下のサイトがわかりやすい(ただし厳密な証明はない)。 mathtrain.jp与えられ…

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) の総和が最大となる…

AOJ 0353 Sort

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0353 解法 とりあえず観察しないとよくわからない。 僕は観察してもよくわからなかったので、確実に言えることを探すことにした。 まず、一番小さい数は、左端に到達したら以降はもう動か…

AOJ 0323 Ruins

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0323 解法 二分探索するとよい。 海岸からの距離を y とすると、半円 i との交点の x 座標は、x[i] ± sqrt(r[i] * r[i] - y * y) となる。 これを区間と見て、すべての半円に対応する区間…

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 解法 部分木の特定の高さのノードだけ取り出すのもオイラーツアーでできる。 この場合は高さごとにノードを管理すればよい。 各ノードが持つ区間は普通のオイラーツアーと同じで、各高さごとに持つデー…

AOJ 1383 Pizza Delivery

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1383 解法 始点および終点からの最短路を求めておく。それぞれ from_s, from_t とする。次に s-t 最短路グラフを作る。このとき、グラフには s から t へ行くのに必要になるかもしれない辺…

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 頂点)を入れる…

JAG夏合宿2018 参加記

はじめに JAG夏合宿2018の参加記です。今年が初参加だったのですが、結構濃密な3日間だったので参加してよかったです。3日間とも、ICPCのときのチーム Zerokan_Sunshine (@nakano, @kazuma, @suibaka) で出ました。 Day1 当日会場まで 原宿からオリセンまで…

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 であるものだけでよい. なぜ…

ACM-ICPC 2018 国内予選 参加記

はじめに 7/6 に行われた ACM-ICPC 2018 国内予選の参加記です. 忘れないうちに書こうと思います. 今年は大雨で関西勢は大変でしたね.自分の大学もリモート参加推奨,という形になってしまいかなりバタバタしていました. 結果 チーム Zerokan_Sunshine …

AOJ 2702 Alternate Escape

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2702 解法 後退解析で解く. ゲームの探索なので,最初は始点からDFSしたくなるかもしれないが,普通に状態が自分に戻ってくるような遷移があるので困る. こういうときは確定しているとこ…

AOJ 0324 Downhill Race

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0324 解法 ダイクストラで解く. 与えられるグラフはDAGになっていて,この上で2回違う条件で最短経路を求めたい.しかし依存関係にあるので独立にはできない. こういうときは1回目と2回…