概要

各サイコロについて「位置・上面・前面」を保持し、指定されたサイコロだけを操作ごとに更新します。サイコロ同士は独立しているため、すべての操作をそのまま順番にシミュレーションすれば求められます。

考察

管理する情報

サイコロを前後に転がしたときの姿勢は、現在の上面を \(u\)、前面を \(f\) とすると、問題文の規則から次のように更新できます。

• + 方向：

  • 上面：\(7-f\)
  • 前面：\(u\)

• - 方向：

  • 上面：\(f\)
  • 前面：\(7-u\)

向かい合う面の和が \(7\) なので、前面の反対側である背面は \(7-f\)、上面の反対側である下面は \(7-u\) と分かります。そのため、6面すべてを管理する必要はなく、上面と前面だけで十分です。

例えば、上面が \(2\)、前面が \(3\) のサイコロを + 方向へ転がすと、

• 新しい上面は \(7-3=4\)
• 新しい前面は \(2\)

となります。ここから - 方向へ転がすと上面が \(2\)、前面が \(3\) に戻ります。

サイコロ同士をまとめて扱う必要はない

複数のサイコロが同じマスに存在しても互いに影響しません。したがって、各操作では指定されたサイコロの情報だけを更新すればよく、他のサイコロを調べる必要はありません。

マス数 \(M\) は最大 \(10^9\) なので、マスごとの配列を用意する方法はメモリ不足になります。また、各操作のたびにすべてのサイコロを確認すると \(O(NQ)\) となり、最大で約 \(4\times 10^{10}\) 回の処理が必要になるため間に合いません。

そこで、サイコロごとに以下の3つだけを配列で保持します。

• 現在位置
• 現在の上面
• 現在の前面

各操作は指定された1個のサイコロだけを \(O(1)\) で更新できます。

アルゴリズム

1. 各サイコロ \(i\) について、初期状態の

   • position[i]：位置
   • top[i]：上面
   • front[i]：前面
     を保存する。

2. 操作を入力順に処理する。

   • 操作対象のサイコロを \(d\) とする。
   • 更新前の上面と前面を、それぞれ oldTop、oldFront に保存する。
   • 方向が + の場合：
     • 位置を \(1\) 増やす。
     • 上面を \(7-\text{oldFront}\) にする。
     • 前面を \(\text{oldTop}\) にする。
   • 方向が - の場合：
     • 位置を \(1\) 減らす。
     • 上面を \(\text{oldFront}\) にする。
     • 前面を \(7-\text{oldTop}\) にする。

3. すべての操作後、各サイコロの位置と上面を出力する。

計算量

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

実装のポイント

• C++の配列添字は \(0\) 始まりですが、入力されるサイコロ番号は \(1\) 始まりです。そのため、操作対象の番号 d を受け取った後に --d します。

• 上面と前面は同時に変化します。更新後の値を次の計算に使ってしまわないように、更新前の値を oldTop と oldFront に保存してから代入します。

• \(M\) は最大 \(10^9\) なので、位置は long long で管理しておくと安全です。

• 位置が範囲外にならないことは問題文で保証されているため、境界判定は不要です。

  ソースコード

#include <iostream>
#include <vector>
using namespace std;

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

    int N, Q;
    long long M;
    cin >> N >> M >> Q;

    vector<long long> position(N);
    vector<int> top(N), front(N);

    for (int i = 0; i < N; ++i) {
        cin >> position[i] >> top[i] >> front[i];
    }

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

        int oldTop = top[d];
        int oldFront = front[d];

        if (c == '+') {
            ++position[d];
            top[d] = 7 - oldFront;
            front[d] = oldTop;
        } else {
            --position[d];
            top[d] = oldFront;
            front[d] = 7 - oldTop;
        }
    }

    for (int i = 0; i < N; ++i) {
        cout << position[i] << ' ' << top[i] << '\n';
    }

    return 0;
}

---

この解説は gpt-5.6-sol-high によって生成されました。