概要

\(N\) 個のサイコロに対して \(Q\) 回の転がし操作をシミュレートし、各サイコロの最終的な位置と上面の数を求める問題です。操作を素直に一つずつ実行するだけで解けます。

考察

この問題は「操作を実際にシミュレーションするだけ」で解ける、いわゆるシミュレーション問題です。難しいアルゴリズムは必要なく、問題文で与えられた転がしの規則を正確にコードに落とし込むことが本質です。

重要なポイントは以下の2つです。

1. サイコロの状態は「位置・上面・前面」の3つで完全に管理できる

サイコロには6面ありますが、転がす方向を決定するために必要なのは「上面の数 \(u\)」と「前面の数 \(f\)」だけです。向かい合う面の和は必ず \(7\) なので、上面が \(u\) なら下面は \(7-u\)、前面が \(f\) なら背面は \(7-f\) というように、\(u\) と \(f\) が決まれば全ての面が自動的に決まります。

したがって、各サイコロについて 位置 pos・上面 up・前面 front の3つの値を持っておけば十分です。

2. 各操作は \(O(1)\) で処理できる

1回の転がし操作で更新するのは1個のサイコロの状態だけです。問題文の規則をそのまま適用すると、

• + 方向（位置 \(+1\)）：新しい上面 \(= 7-f\)、新しい前面 \(= u\)
• - 方向（位置 \(-1\)）：新しい上面 \(= f\)、新しい前面 \(= 7-u\)

となります。ここで注意すべきは、更新前の \(u\) と \(f\) を使って両方を計算することです。先に上面を書き換えてしまうと、前面の計算に古い \(u\) が使えなくなるため、一時変数に \(u, f\) を退避してから更新します。

素朴なシミュレーションでも、1操作 \(O(1)\)・全体で \(O(N+Q)\) に収まるため、制約（\(N+Q \leq 2\times 10^5\)）に対して十分高速です。

なお、位置が \(1\) 未満や \(M\) 超になることは制約で保証されているので、範囲チェックは不要です。ただし \(M \leq 10^9\) なので、位置は int ではなく long long で扱う方が安全です（実際には範囲内に収まりますが、余裕を持たせています）。

アルゴリズム

1. 各サイコロ \(i\) の初期状態 \((S_i, U_i, F_i)\) を配列 pos, up, front に読み込む。
2. \(Q\) 回の操作を順に処理する。操作 \((d_j, c_j)\) に対して：
   • 現在の上面 \(u = \text{up}[d_j]\)、前面 \(f = \text{front}[d_j]\) を退避する。
   • + なら pos[d]++, up[d] = 7-f, front[d] = u。
   • - なら pos[d]--, up[d] = f, front[d] = 7-u。
3. 最後に各サイコロの pos と up を出力する。

具体例：上面 \(u=1\)、前面 \(f=2\) のサイコロを + に転がすと、新しい上面は \(7-2=5\)、新しい前面は \(1\) になります。続けて - に転がすと、新しい上面は前面 \(1\)、新しい前面は \(7-5=2\) となり、上面が元の \(1\) に戻ることが確認できます（+ と - は逆回転なので整合しています）。

計算量

• 時間計算量: \(O(N+Q)\)
• 空間計算量: \(O(N)\)

いずれも制約の上限 \(2\times 10^5\) に対して余裕を持って高速に処理できます。

実装のポイント

• 更新順序に注意：+ 方向では新しい前面に古い上面 \(u\) を使い、- 方向では新しい前面に古い上面 \(u\) を使います。上面を先に書き換えると前面の計算が壊れるため、必ず更新前の \(u, f\) を別変数に保存してから両方を計算します。

• 入出力の高速化：\(N, Q\) が最大 \(2\times 10^5\) 程度なので致命的ではありませんが、出力を1回にまとめてバッファリングする（string に貯めて最後にまとめて出力する）ことで、大量の出力による低速化を防いでいます。

• 位置の型：\(M \leq 10^9\) に対応するため、位置は long long で管理しています。

  ソースコード

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

int main(){
    int N, Q;
    long long M;
    scanf("%d %lld %d", &N, &M, &Q);
    vector<long long> pos(N+1);
    vector<int> up(N+1), front(N+1);
    for(int i=1;i<=N;i++){
        scanf("%lld %d %d", &pos[i], &up[i], &front[i]);
    }
    for(int j=0;j<Q;j++){
        int d;
        char c[4];
        scanf("%d %s", &d, c);
        int u = up[d], f = front[d];
        if(c[0]=='+'){
            pos[d]++;
            up[d] = 7 - f;
            front[d] = u;
        } else {
            pos[d]--;
            up[d] = f;
            front[d] = 7 - u;
        }
    }
    string out;
    out.reserve(N*12);
    char buf[64];
    for(int i=1;i<=N;i++){
        int len = sprintf(buf, "%lld %d\n", pos[i], up[i]);
        out.append(buf, len);
    }
    fputs(out.c_str(), stdout);
    return 0;
}

---

この解説は claude4.8opus-high によって生成されました。