【ABC410 C問題】考察から実装(c++)まで

Last updated at 2025-06-17Posted at 2025-06-17

AtCoderBeginnerContest410の解説＆感想です。
コンテストリンク

問題一覧

C問題 - Rotatable Array

問題リンク

問題概要

長さ$N$の数列$A$があり、はじめは$A_i=i$となっている。$Q$個のクエリを順番に処理せよ。クエリの種類は以下の三つ。

タイプ1：$A_p$をxに変更
タイプ2：$A_p$を表示
タイプ3：「$A$の先頭の要素を取り除き末尾に追加」という処理を$K$回やる

制約

$1 \le N \le 10^6$
$1 \le Q \le 3 \times 10^5$
全てのクエリは以下の制約を満たす
- $1 \le q \le N$
- $1 \le x \le 10^6$
- $1 \le k \le 10^9$

考察

簡単そうなクエリから処理したくなるのが人情。
クエリ1と2は変数を一個書き換えたり表示したりするだけなので、$O(1)$でちゃちゃっとできそう。
問題はクエリ3だけど、$k$の制約がデカくてシミュレーションできない。困った...。
困ったのでよく考えてみると、「配列が左にkずれる」のと、「視点が右にkずれる」のは本質的には同じそう。
つまり配列自体は操作せずに、添字をずらしてやればいい。具体的には$A_{(1+k)\%N}, A_{(2+k)\%N}...A_{(N+k)\%N}$みたいな感じで、全部の添字に$k$足してmodとればいけそう。小さいケースで試してみて、いけてそうなので実装開始！
計算量は、クエリ1,2,3どれも$O(1)$なので、全体で$O(Q)$。

実装

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;

int main(){
    //入力
    ll N,Q;
    cin>>N>>Q;
    
    //配列Aを1,2,3...の連番で用意
    vll A(N);
    iota(A.begin(), A.end(), 1);
    
    //視点が先頭からいくつずれたか
    ll offset = 0;
    
    while(Q--){
        ll type;
        cin>>type;
        
        if(type == 1){
            ll p,x;
            cin>>p>>x;
            A[(offset+p-1)%N] = x;
        }
        else if(type == 2){
            ll p;
            cin>>p;
            cout<<A[(offset+p-1)%N]<<endl;
        }
        else{
            ll k;
            cin>>k;
            offset = (offset+k)%N;
        }
    }
}

その他問題

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up