概要

\(N\) 個のサイコロの初期状態が与えられ、\(Q\) 回の操作（特定のサイコロを左右に1マス転がす）をシミュレーションして、最終的な各サイコロの位置と上面の数を求める問題です。

考察

マス目の数 \(M\) が最大 \(10^9\) と大きいため、「マス目全体を配列などで保持する」というアプローチではメモリや時間が不足してしまいます。

しかし、以下の点に注目すると非常にシンプルに解くことができます。 1. サイコロ同士は独立している: あるサイコロの動きが他のサイコロに影響を与えることはありません。 2. 追跡すべき情報はわずか: 各サイコロについて管理すべきなのは「現在の位置」「上面の数」「前面の数」の3つだけです。 3. 転がし操作は \(O(1)\) で計算可能: サイコロを1マス転がしたときの新しい上面・前面の数は、転がす前の上面・前面の数から直ちに求まります。

操作回数 \(Q\) は最大 \(2 \times 10^5\) です。1回の転がし操作を \(O(1)\) で処理できれば、全体で \(Q\) 回のシミュレーションを行っても十分実行時間制限に間に合います。

アルゴリズム

各サイコロの情報を構造体やクラス等で管理し、クエリごとにサイコロの状態を更新します。

各サイコロ \(i\) について、以下の情報を保持します。 - pos: 現在の位置 - u: 現在の上面の数 - f: 現在の前面の数

操作 \((d, c)\) が与えられたとき、サイコロ \(d\) の更新前の上面を \(u\)、前面を \(f\) とすると、方向 \(c\) に応じて以下のように更新します。

• c == '+' の場合（マス番号が増える方向）：

  • 位置: \(\text{pos} \leftarrow \text{pos} + 1\)
  • 新しい上面: \(7 - f\)
  • 新しい前面: \(u\)

• c == '-' の場合（マス番号が減る方向）：

  • 位置: \(\text{pos} \leftarrow \text{pos} - 1\)
  • 新しい上面: \(f\)
  • 新しい前面: \(7 - u\)

すべての操作をシミュレーションした後、各サイコロの最終位置 pos と上面 u を出力します。

計算量

• 時間計算量: \(O(N + Q)\)
  • サイコロの初期状態の読み込みに \(O(N)\)
  • 各クエリの処理（シミュレーション）に \(O(1)\) \(\times Q = O(Q)\)
  • 最終結果の出力に \(O(N)\)
  • 全体で \(O(N + Q)\) となり、実行時間制限内に十分収まります。
• 空間計算量: \(O(N)\)
  • \(N\) 個のサイコロの状態（位置・上面・前面）を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 更新時の値の退避: 状態を更新する際、新しい上面の計算に更新前の前面の値が必要となり、新しい前面の計算に更新前の上面の値が必要となります。更新前の \(u\) と \(f\) の値をあらかじめ別の変数に保持してから更新するようにしてください。

• 型の選択: マス目の位置 \(M\) は最大 \(10^9\) であるため、位置を表す変数には 64-bit 整数型（C++の long long など）を使用しておくとオーバフローの心配がなく安全です。

  ソースコード

#include <iostream>
#include <vector>

using namespace std;

struct Dice {
    long long pos;
    int u;
    int f;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    long long M;
    if (!(cin >> N >> M >> Q)) return 0;

    vector<Dice> dice(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> dice[i].pos >> dice[i].u >> dice[i].f;
    }

    for (int j = 0; j < Q; ++j) {
        int d;
        char c;
        cin >> d >> c;

        int cur_u = dice[d].u;
        int cur_f = dice[d].f;

        if (c == '+') {
            dice[d].pos += 1;
            dice[d].u = 7 - cur_f;
            dice[d].f = cur_u;
        } else {
            dice[d].pos -= 1;
            dice[d].u = cur_f;
            dice[d].f = 7 - cur_u;
        }
    }

    for (int i = 1; i <= N; ++i) {
        cout << dice[i].pos << " " << dice[i].u << "\n";
    }

    return 0;
}

この解説は gemini-3.6-flash-high によって生成されました。