2014 Yandex.Algorithm Elimination Stage, Round 2 A - Cycles with Common Vertex
問題概要
n 個の鎖が与えられ,それぞれのサイズは c_i である.
鎖とは,連結グラフであり,かつ両端点以外の頂点の次数が2であるものである.
これらの鎖を,鎖とは別に用意した1つの頂点 X に,その両端をつなげる.
こうしてできたグラフ(Xに輪っかがいっぱいついてるみたいなグラフ)の何箇所かを黒で塗る.
ただし,任意の黒で塗られた頂点間の最短距離が K 以上となるように塗らなければならない.
このとき,最大何箇所を黒で塗ることができるか?
・制約
1 <= N <= 10^5
1 <= K <= 10^5
K <= c_i <= 10^9
解法
各輪っかのサイズは c_i + 1 になり,K個置きに黒く塗る.
すると,各輪っかについて,黒く塗られていない最大の連続した部分があるはずである.
その部分の真中に,X が来るようにする.
すると,X から各鎖について,黒く塗られている場所までの距離は K/2 以上となる(ただし,K / 2 は整数での割り算であり,切り捨てである).
したがって,このように配置すれば,異なる鎖に含まれる黒同士の距離は K / 2 * 2 以上となり,基本的に最大に色をぬることができる.
ただし,切り捨てであるから,実際は K / 2 == (K - 1) / 2 となる鎖がいくつか含まれる可能性がある.
そのような鎖の数を M とすると,それらのうちから M - 1 個選んで,黒く塗る箇所を1つ諦めるしかない.
以上で,O(N) で解けた.
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { int N, K; cin >> N >> K; vector<int> c(N), space(N); int cnt = 0; for(int i = 0; i < N; ++i) { cin >> c[i]; space[i] = (K + ((c[i] + 1) % K)) / 2; cnt += space[i] * 2 < K; } ll ans = 0; for(int i = 0; i < N; ++i) { ans += (c[i] + 1) / K; } ans -= max(0, cnt - 1); cout << ans << endl; }
感想
A問題にしては難しくない?若干迷走してしまった.