概要

\(N\) 個のサイコロがあり、\(Q\) 回の転がし操作を指示通りにシミュレーションし、各サイコロの最終的な位置と上面の数を出力する問題です。

考察

この問題を解くための重要なポイントは、サイコロ同士が互いに影響を及ぼさないという点です。複数のサイコロが同じマスに置かれることはありますが、それぞれ独立に扱われるため、各サイコロの状態（位置、上面、前面）を個別に配列で管理すればよいことがわかります。

各操作は特定の1つのサイコロに対してのみ行われ、状態の変化も数式で明確に与えられています。制約として \(N+Q \leq 2\times 10^5\) と大きいですが、1回の操作あたりの更新を \(O(1)\) で行うことができれば、全体でも十分に高速に処理できます。

したがって、難しいデータ構造やアルゴリズムを用いる必要はなく、問題文で与えられた更新ルールをそのまま実装してシミュレーションするアプローチで解くことができます。

アルゴリズム

1. \(N\) 個のサイコロの初期位置 pos、上面 top、前面 front をそれぞれ配列に格納します。
2. \(Q\) 回の操作を順番に処理します。\(j\) 回目の操作では、サイコロ \(d_j\) の現在の上面 \(u\) と前面 \(f\) を取得します。
3. 転がす方向 \(c_j\) に応じて、以下のようにサイコロ \(d_j\) の状態を更新します。
   • + 方向の場合：
     • 位置を \(1\) 増やす
     • 上面を \(7-f\) に更新
     • 前面を \(u\) に更新
   • - 方向の場合：
     • 位置を \(1\) 減らす
     • 上面を \(f\) に更新
     • 前面を \(7-u\) に更新
4. すべての操作が終わった後、各サイコロの最終的な位置 pos[i] と上面 top[i] を順に出力します。

計算量

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

実装のポイント

• Pythonでは入出力が多くなると実行時間がボトルネックになるため、sys.stdin.buffer.read().split() を用いて入力を一度にすべて読み込むことで高速化を図っています。

• read().split() で読み込んだ文字列データはバイト文字列として扱われるため、方向の判定を行う際には c == b'+' のようにバイト文字列として比較する必要があります。

• サイコロの番号は \(1\) から始まるため、配列のサイズを \(N+1\) とし、インデックスを \(1\) から使用すると入力との対応が分かりやすくなります。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1
    q = int(data[idx]); idx += 1
    pos = [0] * (n + 1)
    top = [0] * (n + 1)
    front = [0] * (n + 1)
    for i in range(1, n + 1):
        pos[i] = int(data[idx]); idx += 1
        top[i] = int(data[idx]); idx += 1
        front[i] = int(data[idx]); idx += 1
    for _ in range(q):
        d = int(data[idx]); idx += 1
        c = data[idx]; idx += 1
        u = top[d]
        f = front[d]
        if c == b'+':
            pos[d] += 1
            top[d] = 7 - f
            front[d] = u
        else:
            pos[d] -= 1
            top[d] = f
            front[d] = 7 - u
    out = [None] * n
    for i in range(1, n + 1):
        out[i - 1] = f"{pos[i]} {top[i]}"
    sys.stdout.write("\n".join(out))

main()

---

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