概要

\(N\) 個のサイコロに対して \(Q\) 回の「1マス転がす」操作を行い、最終的な各サイコロの位置と上面の数を求める問題です。操作の規則が明確に与えられているため、その規則通りにシミュレーションすれば解けます。

考察

この問題の重要なポイントは、各操作の内容（位置と姿勢の変化）が問題文で完全に与えられていることです。つまり、複雑な計算や工夫は不要で、書かれている規則をそのまま実装すれば正解が得られます。

各サイコロについて管理すべき状態は次の3つです。

• 位置 pos
• 上面の数 up
• 前面の数 front

操作は「サイコロ番号 \(d_j\)」と「方向 \(c_j\)」で指定されるので、対応するサイコロの状態だけを更新します。転がす直前の上面を \(u\)、前面を \(f\) とすると、規則は次の通りです。

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

ここで注意すべきなのは、上面と前面を同時に更新する際の順序です。例えば + 方向では新しい前面に「古い上面 \(u\)」を使いますが、先に上面を書き換えてしまうと \(u\) の値が失われてしまいます。そのため、更新前の \(u, f\) を一時変数に退避してから両方を計算する必要があります。

素朴なシミュレーションでも、操作回数は \(Q \le 2\times 10^5\) と少なく、1回の操作は \(O(1)\) で処理できるため、計算量的にまったく問題ありません。特別な高速化アルゴリズムは不要です。

なお、下面の数は使いませんが、「向かい合う面の和は \(7\)」という性質から、上面が \(u\) のとき下面は \(7-u\) になる、という関係が規則の中の \(7-f\) や \(7-u\) に現れています。

アルゴリズム

以下の手順で処理します。

1. 各サイコロの初期状態 pos[i], up[i], front[i] を配列に格納する。
2. \(Q\) 回の操作を順に読み込み、指定されたサイコロ \(d\) について:
   • 更新前の上面 \(u = \) up[d]、前面 \(f = \) front[d] を取得する。
   • + なら pos[d] += 1, up[d] = 7-f, front[d] = u
   • - なら pos[d] -= 1, up[d] = f, front[d] = 7-u
3. すべての操作後、各サイコロの pos[i] と up[i] を出力する。

計算量

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

各操作は定数時間で処理でき、初期化と出力に \(O(N)\) かかります。制約 \(N + Q \le 2\times 10^5\) に対して十分高速です。

実装のポイント

• 状態更新の順序: 上面と前面を更新する際は、必ず更新前の値 \(u, f\) を一時変数に取り出してから計算します。片方を先に書き換えると、もう片方の計算で古い値が使えなくなりバグの原因になります。

• 高速な入力処理: \(N, Q\) が最大 \(2\times 10^5\) 程度なので、Python では sys.stdin.buffer.read() で一括読み込みしてトークン分割すると高速です。1行ずつ input() すると遅くなる場合があります。

• 方向の比較: sys.stdin.buffer を使うとバイト列で読み込まれるため、比較対象も b'+' のようにバイトリテラルにする必要があります。

• 位置の範囲: 「位置が \(1\) 未満や \(M\) 超になることはない」と保証されているため、範囲チェックは不要です。単純に \(\pm 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
    up = [0]*N
    front = [0]*N
    
    for i in range(N):
        pos[i] = int(data[idx]); idx += 1
        up[i] = int(data[idx]); idx += 1
        front[i] = int(data[idx]); idx += 1
    
    for j in range(Q):
        d = int(data[idx]) - 1; idx += 1
        c = data[idx]; idx += 1
        u = up[d]
        f = front[d]
        if c == b'+':
            pos[d] += 1
            up[d] = 7 - f
            front[d] = u
        else:
            pos[d] -= 1
            up[d] = f
            front[d] = 7 - u
    
    out = []
    for i in range(N):
        out.append(str(pos[i]) + " " + str(up[i]))
    sys.stdout.write("\n".join(out) + "\n")

main()

---

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