https://beta.atcoder.jp/contests/arc084/tasks/arc084_c
0-originでfloor((X+1)/2)-1番目を求める問題です。Xが十分大きければ、最初の文字は(K+1)/2になり、
Nを1つ減らした時の((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だけ前の数列を考えればいいだけですね…無駄に再帰的に考えてしまった。