🦔

ABC355 C - Loong Trackingを理解し忘れないようにする

2024/08/30に公開

問題概要

1~Nまで数字のついたN個のパーツがあり、パーツ1を頭とする。
パーツの処理値は(i,0)とする。
Q回のクエリを発行し、type1ならCの方向にパーツ1を動かし、パーツ2以降は前のパーツの位置に移動する。
type2ならpのパーツの位置を求める。

ハマった点

全探索O(NM)以外のソリューションを思いつかず。。

解説見た

type1について、パーツを管理する際に先頭にパーツ1移動後の値を追加して末尾を削除する。
そうすると、パーツ1が移動したことを示せる。
同時にパーツ2は移動前のパーツ1に移動していることになるし、パーツ3も移動前のパーツ2になる。(i>=2の時、パーツiは移動前のパーツi-1となる。)
上記の先頭に追加して末尾を削除する操作がdequeを用いるとO(1)で出来るので、全体計算量はO(Q)となる。

提出コード

https://atcoder.jp/contests/abc335/submissions/52254754

参考元

公式解説記事
https://atcoder.jp/contests/abc335/editorial/9026

Discussion