AOJ 2884 Tanka Number

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2884 解法 二分探索 + 桁DP ……ではなく貪欲に解く。 基本的に上の桁から順番に数字を確定させていって、 n 番目を超えないギリギリを選択する、というよくあるやり方。 当然だが各桁は小さ…

AOJ 2787 Pipe Fitter and the Fierce Dogs

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2787 解法 一番上の行のすべての家は special pipe 確定だから、(W + 1) / 2 > K なら不可能であり、それ以外は可能である。 それ以外については、一旦 special pipe を使わないとして考え…

AOJ 2432 Sports Days 2.0

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2432 解法 行列累乗で解く。 A[u][v] := u -> v のウォークで最大となるもの と定義すると、A を n 回かけた行列 An は、長さ n のウォークについて考えたものになる。これは超典型。 行列…

AOJ 0389 Dungeon 2

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0389 解法 木DP。つらい。 以下自分の解き方を書くけど、他の人のコード読む限り状態数はまだ減らせそう? すくなくともテーブルでもつ必要のある状態は減らせると思う。まあいいか。まず…

ACM-ICPC 2018 Seoul Regional 参加記 (コンテスト以外)

はじめに 2018年に韓国で行われた ICPC Seoul Regional の参加記です。 自分はチーム Zerokan_Sunshine としてでました。 チームメイトはいつもの kazuma, nakano です。この記事はコンテスト以外の部分に絞って書いたものです。 コンテストの内容はこちらか…

ACM-ICPC 2018 Seoul Regional 参加記 (コンテスト)

はじめに 2018年に韓国で行われた ICPC Seoul Regional の参加記です。 自分はチーム Zerokan_Sunshine としてでました。 チームメイトはいつもの kazuma, nakano です。この記事はコンテストについて書いたものです。チームの役割分担は以下の通り nakano …

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