C++で解く!カードを昇順に公開するデッキの並べ方

一意の番号が書かれたカードで構成されるデッキがあるとします。デッキは任意の順序に並べ替えることができ、最初はすべてのカードが裏向き(未公開)の状態で1つの山になっています。ここで、すべてのカードが公開されるまで、以下の手順を繰り返し実行します。

• デッキの一番上のカードを取り出して公開し、デッキから取り除きます。
• まだデッキにカードが残っている場合は、次の一番上のカードをデッキの一番下へ移動します。
• 未公開のカードが残っている場合は手順1に戻ります。そうでなければ処理を終了します。

求めるのは、この操作を行ったときにカードが昇順で公開されるようなデッキの並び順です。答えの最初の要素はデッキの一番上とみなされます。

具体例で理解する

入力が [17,13,11,2,3,5,7] の場合、出力は [2,13,3,11,5,17,7] になります。

デッキを [2,13,3,11,5,17,7] と並べ替えた場合を追いかけてみましょう。まず2が一番上にあるので、2を公開して取り除きます。次に13を一番下へ移動すると、デッキは [3,11,5,17,7,13] になります。続いて3を公開して取り除き、同じ手順を繰り返すと、デッキは [5,17,7,13,11] → [7,13,11,17] → [11,17,13] → [13,17] → [17] と変化し、最後に17を公開して終了です。結果として、カードは 2, 3, 5, 7, 11, 13, 17 の順に公開され、昇順になっています。

解法のアプローチ

この問題を効率的に解くには、以下の手順に従います。

• まずデッキをソートし、n をデッキのサイズとします。
• キュー q と、サイズ n の配列 ans を定義します。
• 0 から n-1 までの連続するインデックス i を q に挿入します。
• i を 0 から n-1 まで繰り返します。
  • x := q の先頭要素を取得して削除
  • ans[x] := deck[i](i番目に小さいカードを配置)
  • x := q の先頭要素を取得して削除
  • x を q の末尾に戻す
• ans を返します。

このアルゴリズムのポイントは、「公開プロセスを逆算しながら答えを構築する」という発想です。ソート済みのカードを、実際の公開手順を再現する形で順番に配置していくことで、目的の並び順が自然に得られます。キューを使って「次にどの位置へカードを置くべきか」を管理しているのが巧妙な点です。

C++実装例

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<int> v){
    cout << "[";
    for(int i = 0; i < v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]" << endl;
}

class Solution {
public:
    vector<int> deckRevealedIncreasing(vector<int>& deck) {
        sort(deck.begin(), deck.end());
        int n = deck.size();
        queue<int> q;
        vector<int> ans(n);
        for(int i = 0; i < n; i++) q.push(i);
        int x;
        for(int i = 0; i < n; i++){
            x = q.front();
            q.pop();
            ans[x] = deck[i];
            x = q.front();
            q.pop();
            q.push(x);
        }
        return ans;
    }
};

int main(){
    vector<int> v1 = {17,13,11,2,3,5,7};
    Solution ob;
    print_vector(ob.deckRevealedIncreasing(v1));
}

入力

[17,13,11,2,3,5,7]

出力

[2,13,3,11,5,17,7]

計算量

• 時間計算量: O(n log n) — ソートのコストが支配的です。
• 空間計算量: O(n) — キューと結果配列が必要です。