頭が \(N\) 個だと思うと全ての頭を移動させる処理が必要になり、ランダムアクセス可能なDequeが無い場合には実装が難しくなります。

そこで、問題文を次のように言い換えましょう。

龍は頭を一つ持ち、最初の頭の座標は \((N, 0)\) です。 龍が移動するたび、頭の残像が元々頭があった座標に最大 \(N-1\) 個まで残ります。

この言い換えの元では全ての頭を管理する必要はなく、1個の頭の軌跡が分かれば良いことになります。 これは頭の軌跡を履歴として保持すればよく、必要な操作は以下の二つになります。

• 末尾に新しい頭の座標を追加する
• 末尾から見て \(p\) 個目に入っている座標を出力する

これはどちらも動的配列(vectorやArrayListなど)を用いれば \(O(1)\) で解くことができます。

import java.util.Scanner
import java.awt.Point
fun main() {
  Scanner(System.`in`).use { sc -> 
    val N = sc.nextInt()
    val Q = sc.nextInt()
    val heads = MutableList(N) { Point(N - it, 0) } // 最初の頭の座標を、N-1回の頭1の移動だと思って設定する
    repeat(Q) {
      if (sc.nextInt() == 1) {
        when(sc.next()) { // Rの途中まで書いたらGitHub Copilotが全部書いてくれて便利だった
          "R" -> heads.add(Point(heads.get(heads.size - 1).x + 1, heads.get(heads.size - 1).y))
          "L" -> heads.add(Point(heads.get(heads.size - 1).x - 1, heads.get(heads.size - 1).y))
          "U" -> heads.add(Point(heads.get(heads.size - 1).x, heads.get(heads.size - 1).y + 1))
          "D" -> heads.add(Point(heads.get(heads.size - 1).x, heads.get(heads.size - 1).y - 1))
        }
      } else {
        val p = sc.nextInt() // 末尾から見てp個目=p-1個前の頭の残像の座標
        println("${heads.get(heads.size - p).x} ${heads.get(heads.size - p).y}")
      }
    }
  }
}