大吉数列 (Array of Fortune) [DISCO presents ディスカバリーチャンネル コードコンテスト2019 本戦 B]

https://atcoder.jp/contests/ddcc2019-final/tasks/ddcc2019_final_b

解法

https://atcoder.jp/contests/ddcc2019-final/submissions/4045691

構築系にはいくつか考え口がある。
まずは、最大ケースを考えてみる。
すると、降順に並べるのが、最大ケースであると分かる。
昇順に並べれば、最小ケースR=0になる。
ここで「最小～最大の間なら全て作れるのではないか」という推測を立てる。
　
構築の手段として、何らかの操作をして、数を調整していく方法が取れないか考えてみる。
N=7, R=3で考えてみる。
「7 6 5 4 3 2 1」は7と4～1, 6と3～1, 5と2～1, 4と1が対応していて、4+3+2+1=10が最大ケース。
この式を見てみると、1～Mの総和が最大ケースで、その中の一部をある操作で消すことができそうという方針で考える。
R=8を作る場合は、2を消して、4+3+1で8を作っていく。
この例で4を消すには、7をうまく動かせば良さそう。
昇順に近づけるには大きい数を後ろに動かせばいいので、7を末尾に持っていくと4が消える。
この状態で3も消したい場合には、同様に6を後ろに動かす。
後ろでは「5 4 3 2 1 7 6」のようにしてもいいのだが、後ろに動かしたあとに数が増える可能性が出てくる。
なので、後ろの方で数を増やさないために、後ろは昇順にすればいい。
　
つまり、アルゴリズムとしては、
1. 降順にソートする
2. 先頭から順にその数に関係する組の個数cntを計算して、cntがR以下であればそのまま残し、Rより大きいなら後ろに動かす
3. 後ろに動かした数は昇順に置く

int N, K; ll R;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K >> R;
 
    queue<int> top;
    stack<int> back;
 
    rrep(i, N, 1) {
        int cnt = i - K;
        if (0 < cnt and cnt <= R) {
            R -= cnt;
            top.push(i);
        }
        else back.push(i);
    }
 
    if (0 < R) printf("No Luck\n");
    else {
        while (!top.empty()) {
            printf("%d ", top.front()); top.pop();
        }
        while (!back.empty()) {
            printf("%d ", back.top()); back.pop();
        }
        printf("\n");
    }
}