概要

\(N\) 個のサイコロを一直線のマス目の上で \(Q\) 回転がす操作をシミュレーションし、最終的な各サイコロの位置と上面の数を出力する問題です。

考察

問題文に、サイコロを転がした際の位置と姿勢（上面、前面）の変化規則が明確に定義されています。各操作で指定されたサイコロについて、この規則通りに状態を更新していくだけで解くことができます。

制約を見ると、サイコロの数 \(N\) と操作の回数 \(Q\) はそれぞれ最大 \(2 \times 10^5\) です。したがって、1回の操作を \(O(1)\) で処理できれば、全体でも \(O(N+Q)\) となり制限時間内に十分間に合います。複雑なデータ構造を用いる必要はなく、素朴なシミュレーションで解くことができます。

アルゴリズム

各サイコロごとに、現在の位置 \(S\)、上面の数 \(U\)、前面の数 \(F\) を記録する配列を用意します。 \(Q\) 回の操作を順番に読み込み、以下の手順で状態を更新します。

操作対象のサイコロ番号を \(d\)、方向を \(c\) とします。

1. \(c\) が + の場合（マス番号が増える方向）:

   • 位置を \(1\) 増やします（\(S \leftarrow S + 1\)）。
   • 新しい上面の数は \(7 - F\) となり、新しい前面の数は現在の上面の数 \(U\) となります。

2. \(c\) が - の場合（マス番号が減る方向）:

   • 位置を \(1\) 減らします（\(S \leftarrow S - 1\)）。
   • 新しい上面の数は現在の前面の数 \(F\) となり、新しい前面の数は \(7 - U\) となります。

全ての操作が終わった後、各サイコロの位置 \(S\) と上面 \(U\) を順に出力します。なお、問題の保証により操作中にマスからはみ出ることはないため、移動の可否判定は不要です。

計算量

• 時間計算量: \(O(N + Q)\)
  • サイコロの初期状態の入力に \(O(N)\)、各操作の処理に \(O(Q)\) かかります。
• 空間計算量: \(O(N)\)
  • 各サイコロの状態を配列で保持するためです。

実装のポイント

• サイコロの状態を更新する際、新しい上面を計算するために元の前面を、新しい前面を計算するために元の上面を使用します。したがって、更新前の値を使って両方を計算するか、一時変数を用いてから代入する必要があります。

  
  // + 方向の更新例
  new_U = 7 - F;
  new_F = U;
  U = new_U;
  F = new_F;
  

• 入力で与えられるサイコロ番号 \(d\) は \(1\) インデックス（\(1\) から始まる）ため、配列のインデックス（\(0\) から始まる）に合わせるために \(-1\) する減算を忘れないようにしましょう。

• \(M\) の最大値は \(10^9\) と大きいですが、実際の移動回数は高々 \(Q\) 回であるため、位置を保持する変数は int 型でも十分ですが、long long 型を使用するとより安全です。

  ソースコード

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, M, Q;
    if (!(cin >> N >> M >> Q)) return 0;
    
    vector<long long> S(N), U(N), F(N);
    for (int i = 0; i < N; ++i) {
        cin >> S[i] >> U[i] >> F[i];
    }
    
    for (int i = 0; i < Q; ++i) {
        int d;
        char c;
        cin >> d >> c;
        --d;
        
        if (c == '+') {
            S[d]++;
            int new_U = 7 - F[d];
            int new_F = U[d];
            U[d] = new_U;
            F[d] = new_F;
        } else {
            S[d]--;
            int new_U = F[d];
            int new_F = 7 - U[d];
            U[d] = new_U;
            F[d] = new_F;
        }
    }
    
    for (int i = 0; i < N; ++i) {
        cout << S[i] << " " << U[i] << "\n";
    }
    
    return 0;
}

---

この解説は or-glm-5.2-high によって生成されました。