Distribute Candies [CSAcademy #70 D]

https://csacademy.com/contest/round-70/task/distribute-candies/

N個をK箱に分けるが以下のルールで分ける

• 隣接する箱の数は異なっている
• 箱には最低1個は入っている
• 箱の中に入っている数の最大値と最小値の差が最小化されている

作るのが不可能なら"-1"

解法

とんでもコードで通しているので、方針だけ説明する。
まず"-1"はどのような場合になるかを考えてみる。
例えば「3 3」は"-1"であるが「4 3」は「1 2 1」が答えである。
最小の数で構築することを考えてみると「1 2 1 2 …」のように作るのが、個数最小である。
そのため、これをやってみて構築できないなら、"-1"である。
　
このように箱に入れても余る場合はそれをなるべく均等に分けるようにアルゴリズムを考えてみる。
K箱あり、それぞれの箱について均等に1個ずつ入れていくとする。
すると、最大値と最小値の差を1のまま維持できる。
そのため、floor(残り/K)をそれぞれの箱に入れておこう。
端数をなるべくばらして入れていくが、順番に気をつけないと「隣接する箱の数が異なっている」が破れる。
まずは、偶数番目に入れていこう（最初に2個入れていた所）。
まだ余る場合は奇数番目に入れていこう。
こうすると、最大値と最小値の差を最小化しつつ、ばらばらに入れることができて、答え。
　
コーナーケースは最初に「1 2 1 2…」と入れるのではなく「2 1 2 1 2…」と入れるのが最適な場合である。
下の実装では関数fでは「1 2 1 2…」と入れて、関数gでは「2 1 2 1 2…」と入れている。
最適な方を答えとして採用しよう。

ll N; int K; ll ans1[101010], ans2[101010];
//---------------------------------------------------------------------------------------------------
int f() {
    ll n = N;
    rep(i, 0, K) {
        if (i % 2 == 0) ans1[i] = 1, n--;
        else ans1[i] = 2, n -= 2;
    }

    if (n < 0) return -1;

    ll d = n / K;
    rep(i, 0, K) ans1[i] += d, n -= d;
    rep(i, 0, K) if ((i % 2) == 1 and 0 < n) {
        ans1[i]++;
        n--;
    }
    rep(i, 0, K) if ((i % 2) == 0 and 0 < n) {
        ans1[i]++;
        n--;
    }

    assert(n == 0);

    ll mi = infl, ma = -infl;
    rep(i, 0, K) {
        chmin(mi, ans1[i]);
        chmax(ma, ans1[i]);
    }
    ll dd = ma - mi;
    return dd;
}
//---------------------------------------------------------------------------------------------------
int g() {
    ll n = N;
    rep(i, 0, K) {
        if (i % 2 == 0) ans2[i] = 2, n -= 2;
        else ans2[i] = 1, n -= 1;
    }

    if (n < 0) return -1;

    ll d = n / K;
    rep(i, 0, K) ans2[i] += d, n -= d;
    rep(i, 0, K) if ((i % 2) == 0 and 0 < n) {
        ans2[i]++;
        n--;
    }
    rep(i, 0, K) if ((i % 2) == 1 and 0 < n) {
        ans2[i]++;
        n--;
    }

    assert(n == 0);

    ll mi = infl, ma = -infl;
    rep(i, 0, K) {
        chmin(mi, ans2[i]);
        chmax(ma, ans2[i]);
    }
    ll dd = ma - mi;
    return dd;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;

    int r1 = f();
    int r2 = g();

    if (r1 < 0 and r2 < 0) {
        printf("-1\n");
        return;
    }

    if (r1 < 0) {
        rep(i, 0, K) {
            if (i) printf(" ");
            printf("%lld", ans2[i]);
        }
        printf("\n");
        return;
    }

    if (r2 < 0) {
        rep(i, 0, K) {
            if (i) printf(" ");
            printf("%lld", ans1[i]);
        }
        printf("\n");
        return;
    }

    if (r1 < r2) {
        rep(i, 0, K) {
            if (i) printf(" ");
            printf("%lld", ans1[i]);
        }
        printf("\n");
    }
    else {
        rep(i, 0, K) {
            if (i) printf(" ");
            printf("%lld", ans2[i]);
        }
        printf("\n");
    }
}