AtCoder Regular Contest 084E: Finite Encyclopedia of Integer Sequences

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

0-originでfloor((X+1)/2)-1番目を求める問題です。Xが十分大きければ、最初の文字は(K+1)/2になり、
Nを１つ減らした時の((X+1)/2)-1-(X%2)番目を求めればいいです。なので、X%2の累積分を考えると必ずNよりも小さいので((X+1)/2)-1がNよりも大きい間は必ず最初の文字は(K+1)/2になります。なので、その間は(K+1)/2を取り続け、N未満になったらXの値は普通にlong longに収まるので愚直に計算すればいいです。

床関数の扱いが下手で無限に±1の差で悩んだ…考察の際||だとわかりにくいのでfloor()と書くようにしましょう。
辞書順の問題が苦手という先入観もさっさと取りさらいたい。

int N, K;
ll powK[300010];
ll powS[300010];

void solve() {
	cin >> K >> N;
	if(K % 2 == 0) {
		cout << (K + 1) / 2 << " ";
		rep(i, 0, N - 1) {
			cout << K << " ";
		}
		return;
	}
	memset(powK, -1, sizeof(powK));
	memset(powS, -1, sizeof(powS));

	powK[0] = 1;
	powS[0] = 0;
	rep(i, 1, N + 1) {
		powK[i] = powK[i - 1] * K;
		powS[i] = powS[i - 1] + powK[i];
		if((powS[i] + 1) / 2 > N) break;
	}
	int at = 0, off = 0;
	while(powS[N - at] == -1) {
		cout << (K + 1) / 2 << " ";
		off += (N - at - 1) % 2;
		at++;
	}
	ll m = (powS[N - at] + 1) / 2 - 1 - off;
	while(true) {
		ll xnext = powS[N - at] / K;
		cout << (m / xnext) + 1 << " ";
		m %= xnext;
		if(m == 0) return;
		else m--;
		at++;
	}
}

rep(i,1,N+1)をrep(i,1,N)にしてREした。朝起きて見たら気づいたけど、絶対コンテスト中気づかない…
あと(i%2)を全部足し合わせると(N-1)/2になるので(K+1)/2,(K+1)/2,...,(K+1)/2の(N-1)/2だけ前の数列を考えればいいだけですね…無駄に再帰的に考えてしまった。