ARC084 E Finite Encyclopedia of Integer Sequences

問題文

https://beta.atcoder.jp/contests/arc084/tasks/arc084_c

 

Kが偶数のときは,先頭がK/2以下の数列と先頭がK/2より大きい数列が同数あるので,真ん中にあるのはK/2のうしろにKがN-1個並んだ数列だとわかる.

以下,Kは奇数とする.

真ん中にある数列が,K=5 N=3のとき{3,3,2},K=5 N=4のとき{3,3,3,1},K=5 N=5のとき{3,3 3,3,1}であることからわかるように,(K+1)/2=Mとすると,答えはM M M ... M 〇 〇 ... 〇という形になる.

まず,先頭が1,2,...,Kの数列が同数ずつあることから,明らかに答えの先頭はM.

そこで先頭がMの数列についてかんがえると,長さ1の数列が1つあり,長さ2以上の数列については2番目の数が1,2,...,Kの数列が同数ずつある.そこでこの中で真ん中にある数列がどこのグループに入るかかんがえると,Nが十分大きければやはり2番目の数がMのグループに入る.

ただし,長さ1の数列が前にあることで1つ順番がずれることに注意.

今,K=5で,先頭が1,2,...,5である数列がそれぞれ31個ずつあるとしよう.すると,この中で真ん中に来るのは先頭が3である数列の中で15番目にあるものになる(全体で156個の数列があるので真ん中は78番目,78=1+31+31+15より先頭が3である数列の中で15番目).31個の数列の真ん中は16番目であるから,長さ1の数列の分で求める数列が1つ前にずれている.一般に,先頭が1,2,...,Kである数列がそれぞれX個あるとき,Xが奇数なら求める数列は先頭がMの数列のうち真ん中より1つ前になる(偶数なら真ん中).

同様にかんがえて上のケタから決定していくと,すこしずつ真ん中からのずれが増えていく.ずれの量をYとすると,X/2>Yである間はMが並ぶが,ある所でX/2≦Yとなると数列にM以外が現れることになる.

しかし,ここで候補が十分すくなくなっていることを利用すると,真ん中からYだけ前にある数列を気合で求めることが出来て,答えが出る.

自力で800点問題がACできて良かった.アルゴリズム自体は比較的すぐ浮かんだが,ややこしくて細かい所を詰めるのに時間がかかった.

想定解は,MがN個並んだ数列より前にある数列が,後ろにある数列よりN-1個多いので,MがN個並んだ数列の(N-1)/2個前を答えるというものだった.たしかにずっと楽ですごい.

 ソースコード

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1000000007LL;
ll sum[30];
int main() {
    ll K, N;
    cin >> K >> N;
    if (K % 2 == 0) {
        cout << K / 2;
        for (int i = 0; i < N - 1; i++) cout << " " << K;
        cout << endl;
        return 0;
    }
    if (K == 1) {
        cout << 1;
        for (int i = 1; i < (N + 1) / 2; i++) cout << " " << 1;
        cout << endl;
        return 0;
    }
    int k = 0;
    sum[0] = 1;
    ll t = 1;
    while (1) {
        t *= K;
        if (sum[k] + t > N) break;
        sum[k + 1] = sum[k] + t;
        k++;
    }
    sum[k + 1] = sum[k] + t;
    k++;
    int d = (K + 1) / 2;
    cout << d;
    int i;
    int offset = 0;
    for (i = 1; i < N; i++) {
        if (N - i - 1 <= k && sum[N - i - 1] / 2 <= offset) break;
        cout << " " << d;
        if ((N-i) % 2) offset++;
    }
    int idx = (sum[N - i] + 1) / 2 - offset;
    for (int j = N - i - 1; j >= 0; j--) {
        if (idx == 0) idx = sum[j];
        if (idx == 1) break;
        idx--;
        cout << " " << (idx + sum[j] - 1) / sum[j];
        idx %= sum[j];
    }
    cout << endl;
}