シーザー配列

今回は paiza の「シーザー配列」の問題に挑戦！

問題概要

• 配列 A が与えられる
  • 長さ N
  • 各要素は 0 以上 M 未満の整数
• シーザー配列操作
  • 配列全体に対して好きな回数「1 を足して M で割った余りに置き換える」を行える
• Q 個のクエリが与えられる
  • 各クエリには (ind_i, S_i) がある
  • 「配列の ind_i 番目の要素が S_i になるようなシーザー配列を作れ」
• 出力
  • 各クエリに対して、シフト後の配列を空白区切りで出力
    
    
    

入力例:

3 5
1 4 0
3
1 3
2 0
3 3

出力例:

3 1 2
2 0 1
4 2 3

✅OK例：

const rl = require('readline').createInterface({ input: process.stdin });

const lines = [];
rl.on('line', line => lines.push(line));

rl.on('close', () => {
    const [N, M] = lines[0].split(' ').map(Number);
    const A = lines[1].split(' ').map(Number);
    const Q = Number(lines[2]);
    const q = lines.slice(3).map(q => q.split(' ').map(Number));
    
    for (let i = 0; i < Q; i++) {
        let [idx, S] = q[i];
        idx--;
        
        if (S === A[idx]) {
            console.log(A.join(' '));
            continue;
        }
        
        const arr = [...A];
        
        while (S !== arr[idx]) {
            for (let j = 0; j < arr.length; j++) {
                arr[j] += 1;
                arr[j] %= M;
            }
        }
        
        console.log(arr.join(' '));
    }
});

while で 1 回ずつ増やすやり方だと M が大きくなると非効率

✨OK例：

const rl = require('readline').createInterface({ input: process.stdin });

const lines = [];
rl.on('line', line => lines.push(line));

rl.on('close', () => {
    const [N, M] = lines[0].split(' ').map(Number);
    const A = lines[1].split(' ').map(Number);
    const Q = Number(lines[2]);
    const queries = lines.slice(3).map(line => line.split(' ').map(Number));

    for (let i = 0; i < Q; i++) {
        let [idx, S] = queries[i];
        idx--; // 0-indexedに直す

        // Sになるまでの加算回数
        const k = (S - A[idx] + M) % M;

        // 配列を k だけ加算
        const ans = A.map(x => (x + k) % M);
        console.log(ans.join(' '));
    }
});

🔍コードの流れ

• 標準入力の準備
• readline モジュールを使って、入力された行を lines 配列に順番に格納。
• 入力の読み取り
  • 1 行目から N と M を取得（配列の長さと modulo の値）
  • 2 行目から配列 A を取得
  • 3 行目からクエリの数 Q を取得
  • 4 行目以降から各クエリ [ind_i, S_i] を取得して queries 配列に格納
• クエリごとの処理
  • クエリのインデックスを 0 始まりに変換（idx--）
  • 指定された要素が S になるまでの加算回数 k を計算
    → (S - A[idx] + M) % M で求める
    ※負の値が出ないように「M を足してから % M」を取る
• 配列全体に加算
  • 配列 A の各要素に k を加算して mod M を取る
  • 新しい配列 ans を作成
• 結果出力
  • 配列 ans を空白区切りで出力

📝まとめ

• シーザー暗号的な配列操作
  • 配列全体を「1 ずつ増やす % M」の操作で変換できる
  • 指定された要素を S にするために必要な操作回数は 差を % M で計算して求める
• 操作回数 k の計算
  • k = (S - A[idx] + M) % M
  • + M は負の値を避けるため
  • % Mで範囲を0～M-1` に収める
• 配列全体に一括加算で効率化
  • while で 1 回ずつ増やすより、計算した k を一括で加算する方が速い
  • 配列 A.map(x => (x + k) % M) で簡単に実現可能
• インデックス調整
  • 入力は 1 始まりなので、プログラム内では 0 始まりに直す（idx--）