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問題にしては難しくない?若干迷走してしまった.