↓問題のページ↓
AtCoder Beginner Contest 335 C - Loong Tracking
＜内容の振り返り・解法＞
更新クエリがやって来るごとに全パーツに対して座標の情報を更新する方針しか思い浮かばず、TLEしない解法を全く見出すことができず本番AC取得失敗に終わった。解説の内容を見ても理解できない箇所がなかっただけに頗る悔しい。
公式解説 に記載されている通り、添字による要素へのアクセスが可能なdequeを用いれば楽に実装できるが、最終的には配列をdeque擬きとして扱って実装した（Javaが標準でそのようなdequeを用意しているのか理解していないためであるが、そもそも自前で添字アクセス可能なdequeを作っておけよという話でもある）。
例えば\(N = 5\)の場合を考える。また、\(i\)番目のパーツの座標を\(P_i\)と表す。以上を踏まえ、更新クエリがやって来る度に全パーツの座標を愚直に更新する方針を選ぶ時の挙動を考える。初期状態で\begin{align} (P_1,P_2,P_3,P_4,P_5) = (a_1,a_2,a_3,a_4,a_5) \end{align}という値を取っているとする。1回目の更新クエリで\(P_1\)が\(b_1\)に変化するとして、\(i+1\)番目のパーツが\(i\)番目のパーツに追従して動くことを踏まえると、この更新クエリを実行した後の状態における各パーツの座標は以下のようになる。\begin{align} (P_1,P_2,P_3,P_4,P_5) = (b_1,a_1,a_2,a_3,a_4) \end{align}これを見ると、先頭が別の値に更新されている他は、1つだけ添字を隣に移すという操作をしているのと等価であると分かる。そこで、十分な長さを持つ座標の情報書き込み領域を予め確保しておき、「先頭の要素の添字を覚えておき、先頭から\(N\)要素分の領域しか参照しない」ことと定めれば、\(0\)回以上の更新クエリが実行された後の状態における\(i\)番目のパーツの座標を添字によるアクセスで瞬時に取得することができる。より具体的には、上記の例だと書き込み領域を\(8\)要素分確保しておき、ひとまず初期状態では\begin{align} (P_1,P_2,P_3,P_4,P_5) = (a_1,a_2,a_3,a_4,a_5) \end{align}という座標になっており、書き込み領域を\(B\)と命名して\begin{align} (B_1,B_2,B_3,B_4,B_5,B_6,B_7,B_8) = ( (0, 0),(0, 0),(0, 0),a_1,a_2,a_3,a_4,a_5) \end{align}であるとしておく。この時、先頭の要素の添字を\(head\)と名付けると、\(head = 4\)が成立している。この状況下において、\(head\)から\(N\)要素だけ切り出すと以下のようになる。\begin{align} (B_4,B_5,B_6,B_7,B_8) = (a_1,a_2,a_3,a_4,a_5) \end{align}先ほどと同様に「1回目の更新クエリで\(P_1\)が\(b_1\)に変化する」という情報を受け、「\(head\)の値を\(1\)だけ減算し、新しい\(head\)に対応する書き込み領域に\(b_1\)という座標を記録する」という操作を行うと、書き込み領域は以下のように変化する。\begin{align} (B_1,B_2,B_3,B_4,B_5,B_6,B_7,B_8) = ( (0, 0), (0, 0),b_1,a_1,a_2,a_3,a_4,a_5) \end{align}この時、「先頭から\(N\)要素分の領域しか参照しない」と定めていたことに従うと、\(B_3\)から\(B_7\)までが各パーツの座標ということになり、この部分のみ切り出すと\begin{align} (B_3,B_4,B_5,B_6,B_7) = (b_1,a_1,a_2,a_3,a_4) \end{align}であることから、確かにこの方針によって「更新クエリがやって来る度に、全パーツの座標を愚直に更新する」方針と同じ結果を効率良く取得できることが分かるので後は実装するだけとなった。
＜具体的な実装＞
1)\(Q\)個のクエリが全て更新である場合に書き込み領域の長さが最大となるため、予め\(N + Q\)以上に設定しておくと確実に配列外参照を防ぐことができる。
2)書き込み領域の長さを\(L\)とする（以下、0-indexedを前提として記載する）。また、\(head = L - N\)と初期化する。\(i = 0, \dotsc, N - 1 \)について、初期状態における座標の情報を書き込む（即ち\( B_{head + i} = (i + 1, 0) \)とする）。
3)更新クエリがやって来た場合、\(head\)をデクリメントし、その値を用いて\begin{align} B_{head} = 新しい座標 \end{align}とする。
4)出力クエリがやって来た場合、\(B_{head + p -1}\)の値を出力する。
※書き込み領域をリングバッファにすればもっとメモリ効率良く実装は可能であるが、今回の問題では些事であるため考慮は不要とした。
