概要

各サイコロについて「位置・上面・前面」を管理し、指定されたサイコロへの転がし操作を順番にシミュレーションします。各操作は定数時間で処理できます。

考察

サイコロ同士は互いに影響せず、複数のサイコロが同じマスに存在することもできます。そのため、マスごとに状態を管理する必要はなく、サイコロごとに現在の状態を管理すれば十分です。

また、転がした後の状態は、現在の上面を \(u\)、前面を \(f\) とすると次のように決まります。

• + 方向：

  • 位置を \(1\) 増やす
  • 新しい上面は \(7-f\)
  • 新しい前面は \(u\)

• - 方向：

  • 位置を \(1\) 減らす
  • 新しい上面は \(f\)
  • 新しい前面は \(7-u\)

向かい合う面の数の和が \(7\) なので、前面の反対側である背面は \(7-f\)、上面の反対側である下面は \(7-u\) と求められます。したがって、左右の面を含む6面すべてを管理する必要はありません。

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

• 新しい上面：\(7-2=5\)
• 新しい前面：\(1\)

となります。

マス数 \(M\) は最大 \(10^9\) なので、マスごとの配列を作る方法は使えません。また、操作のたびに対象のサイコロを探索すると、最悪で \(O(NQ)\) となり間に合いません。サイコロ番号を配列の添字に対応させれば、対象の状態を \(O(1)\) で更新できます。

アルゴリズム

1. 各サイコロについて、次の3つを配列に保存する。
   • 現在位置 pos
   • 現在の上面 top
   • 現在の前面 front
2. 各操作 \((d,c)\) を入力順に処理する。
3. サイコロ \(d\) の更新前の上面を \(u\)、前面を \(f\) として保存する。
4. 方向に応じて状態を更新する。
   • + の場合：
     • pos[d] += 1
     • top[d] = 7 - f
     • front[d] = u
   • - の場合：
     • pos[d] -= 1
     • top[d] = f
     • front[d] = 7 - u
5. 全操作終了後、各サイコロの位置と上面を出力する。

計算量

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

実装のポイント

状態を更新する前に、古い上面と前面をそれぞれ変数 u, f に保存する必要があります。先に top を書き換えてから、その値を使って front を更新すると、更新前の上面を失ってしまい誤った結果になります。

また、入力を sys.stdin.buffer.readline で受け取っているため、方向文字は文字列ではなくバイト列です。そのため、+ の判定には c == b'+' を用います。

問題によって位置が常に \(1\) 以上 \(M\) 以下になることが保証されているため、範囲外かどうかを個別に確認する必要はありません。

ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline

    N, M, Q = map(int, input().split())

    pos = [0] * N
    top = [0] * N
    front = [0] * N

    for i in range(N):
        pos[i], top[i], front[i] = map(int, input().split())

    for _ in range(Q):
        d, c = input().split()
        i = int(d) - 1
        u = top[i]
        f = front[i]

        if c == b'+':
            pos[i] += 1
            top[i] = 7 - f
            front[i] = u
        else:
            pos[i] -= 1
            top[i] = f
            front[i] = 7 - u

    sys.stdout.write('\n'.join(
        f'{pos[i]} {top[i]}' for i in range(N)
    ))

if __name__ == "__main__":
    main()

---

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