概要

直線上に並んだ \(N\) 個のサイコロに対し、\(Q\) 回にわたって指定された方向（+ または -）へ 1 マス転がす操作を行い、すべての操作が終わった後の各サイコロの位置と上面の数を求める問題です。

考察

この問題で重要なポイントは以下の 3 点です。

1. サイコロ同士が独立していること 問題文に「サイコロ同士は互いに影響を及ぼさず、それぞれ独立に扱われます」とあります。そのため、あるサイコロを転がしても他のサイコロの位置や向きに影響しません。
2. 1 回の操作が \(O(1)\) 時間でシミュレーション可能であること サイコロを 1 マス転がしたときの「位置」「上面」「前面」の変化ルールは問題文で明確に与えられています。
   • + 方向へ転がす場合：
     • 位置：\(+1\)
     • 新しい上面：\(7 - (\text{旧前面})\)
     • 新しい前面：\(\text{旧上面}\)
   • - 方向へ転がす場合：
     • 位置：\(-1\)
     • 新しい上面：\(\text{旧前面}\)
     • 新しい前面：\(7 - (\text{旧上面})\)

この遷移は単純な数式で表せるため、1 回の操作を \(O(1)\) 時間で直接計算できます。 3. マス目の数 \(M\) の大きさ マス目の数 \(M\) は最大 \(10^9\) と非常に大きいですが、問題文よりサイコロの位置は常に \(1 \le \text{位置} \le M\) の範囲内に収まります。マス目全体の配列を持つ必要はなく、各サイコロの「現在位置」を整数型の変数として保持するだけで十分です。

したがって、\(Q\) 回の操作を順番に愚直にシミュレーションすれば、十分高速に解を得ることができます。

アルゴリズム

1. 各サイコロ \(i\)（\(0 \le i < N\)）について、現在の位置 pos[i]、上面の数 u[i]、前面の数 f[i] を配列で保持します。
2. \(Q\) 回の操作を順に処理します。
   • 操作対象のサイコロ番号 \(d\)（\(0\)-indexedに変換するため入力値から \(1\) を引きます）と方向 \(c\) を読み取ります。
   • \(c = \text{`+`}\) の場合：
     • pos[d] を \(+1\) します。
     • u[d] と f[d] を同時に更新します（u[d] は \(7 - \text{f}[d]\) に、f[d] は \(\text{u}[d]\) に変更）。
   • \(c = \text{`-`}\) の場合：
     • pos[d] を \(-1\) します。
     • u[d] と f[d] を同時に更新します（u[d] は \(\text{f}[d]\) に、f[d] は \(7 - \text{u}[d]\) に変更）。
3. すべての操作終了後、各サイコロの最終位置 pos[i] と上面の数 u[i] を出力します。

計算量

• 時間計算量: \(O(N + Q)\)
  • 初期化に \(O(N)\)、各操作のシミュレーションに \(1\) 回あたり \(O(1)\) かかるため、\(Q\) 回の操作で \(O(Q)\) となります。全体で \(O(N + Q)\) となり、制約の \(N, Q \le 2 \times 10^5\) に対して十分高速（実行時間制限に余裕で間に合う）です。
• 空間計算量: \(O(N)\)
  • サイコロ \(N\) 個ぶんの位置、上面、前面を保持するための配列が必要となるため、\(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N, Q \le 2 \times 10^5\) と入出力の量が多いため、Python では sys.stdin.read().split() を用いて一度に全入力を取得し、出力もまとめて行うことで実行時間を大幅に短縮できます。

• 0-indexed への変換: 問題文のサイコロの番号は \(1\) から始まる \(1\)-indexed です。配列のインデックスとして使う際は、\(1\) を引いて \(0\)-indexed に直すことを忘れないようにしましょう。

• 変数の同時更新: サイコロの上面と前面を更新する際、片方の新しい値が更新前のもう片方の値に依存します。Python では u[d], f[d] = 7 - f[d], u[d] のように多重代入を使うことで、一時変数を用意せずに安全かつ正確に値を入れ替えることができます。

  ソースコード

import sys


def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    M = int(input_data[1])
    Q = int(input_data[2])

    idx = 3

    pos = [0] * N
    u = [0] * N
    f = [0] * N

    for i in range(N):
        pos[i] = int(input_data[idx])
        u[i] = int(input_data[idx + 1])
        f[i] = int(input_data[idx + 2])
        idx += 3

    for _ in range(Q):
        d = int(input_data[idx]) - 1
        c = input_data[idx + 1]
        idx += 2

        if c == "+":
            pos[d] += 1
            u[d], f[d] = 7 - f[d], u[d]
        else:
            pos[d] -= 1
            u[d], f[d] = f[d], 7 - u[d]

    out = [f"{pos[i]} {u[i]}" for i in range(N)]
    print("\n".join(out))


if __name__ == "__main__":
    main()

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