今回は paiza の「【シミュレーション 1】反復横跳び」の問題に挑戦！
今日から解いていく問題のテーマは、シュミレーション！
問題概要
◯ 反復横跳びのルール
- 中央線から始めて、
- 右 → 中央 → 左 → 中央 → 右 … の順で線を跨ぐ。
- つまり「4回で1往復（右・中央・左・中央）」になる。
◯ paiza 君が悪戯したタイミング
- ちょうど 4 ×
N回目の直前に「左の線」を 外側にXcm ずらした。
◯ 影響
- 4 ×
N回目以降、「左に行く動き」と「左から中央に戻る動き」それぞれがXcm 余分に移動することになる。
◯ 目的
- 計測結果が
K回のとき、
「正規の反復横跳び」と比べて 何 cm 余分に動いたか を求める。
入力例：
1 3 10 // N X K
出力例：
6
✅ OK例：
const rl = require('readline').createInterface({ input: process.stdin });
const lines = [];
rl.on('line', (input) => lines.push(input));
rl.on('close', () => {
const [N, X, K] = lines[0].split(' ').map(Number);
// 左に行くときと左から真ん中に戻るときにXが加算される
let sum = 0;
for (let i = 4 * N; i <= K; i += 4) {
if (i + 3 <= K) sum += X;
if (i + 4 <= K) sum += X;
}
console.log(sum);
});
-
i = 4 * NからKまで、4回ごとのサイクルを見ていく。 - 各サイクルで以下を判定：
- 左 – 中央 の間に追加距離が発生している
-
if (i + 3 <= K)→ 中央から左に行く動作が含まれているなら+X。 -
if (i + 4 <= K)→ 左から中央に戻る動作が含まれているなら+X。
※ ただし K が最大 10 億なので、ループで 1/4 まで回すと最悪 2.5 億回のループになり、効率は良くない。
✅ OK例：数式
const rl = require('readline').createInterface({ input: process.stdin });
const lines = [];
rl.on('line', (input) => lines.push(input));
rl.on('close', () => {
const [N, X, K] = lines[0].split(' ').map(Number);
let result;
if (K % 4 === 3) {
result = 2 * X * Math.floor((K - 4 * N) / 4) + X;
} else {
result = 2 * X * Math.floor((K - 4 * N) / 4);
}
console.log(result);
});
🔍 解説
🔹 反復横跳びの動きのサイクル
- 跨ぐ順番は → 右 → 中央 → 左 → 中央 → … と繰り返されます。
- 4 回跨ぐと「元の位置（中央）」に戻ります。
- つまり「4 回を 1 セット」として考えられる。
🔹 いたずらで距離が伸びるタイミング
- 友達が 左の線に行くとき
- 左の線から 中央に戻るとき
の 2 回、余分にXcm ずつ移動距離が増えます。
→ 1 セット(= 4回)ごとに2×Xの追加距離が発生する。
🔹 いたずらが始まるタイミング
- いたずらは「
4×N回目を跨ぐ直前」に発生する。 - よって、そこから数えて
(K - 4N)回分の動きに余分な距離が影響する。
🔹 計算方法
-
(K - 4N)回の動きを「4 回 1 セット」に分けて数えると、 -
((K - 4N) / 4)セット分になる。 - 1 セットごとに
2×X増えるので、 -
2 * X * ((K - 4N) / 4)で計算できる。
🔹 余りが出る場合の処理
-
(K - 4N)を 4 で割った余り（K % 4）によって増加分が変わる。 -
K % 4 = 0,1,2の場合
→ セット分の増加だけでOK。 -
K % 4 = 3の場合
→ 「左の線に行く途中」まで進むので、もう+Xが必要。
🔹 まとめると式は：
-
K % 4 = 0,1,2のとき
2 * X * ((K - 4N) / 4)
-
K % 4 = 3のとき
2 * X * ((K - 4N) / 4) + X
つまり数式は「1 セットごとに 2X 加算、ただし最後に余りが 3 のときだけ追加で X」ということを表している。
🗒️ まとめ
- 反復横跳びの動作
- 跨ぐ順番は「右 → 中央 → 左 → 中央 → …」。
- 4回で1セット、元の位置（中央）に戻る。
- よって「4回ごとに同じ動きの繰り返し」。
- いたずらの発生
- 友達が「4×N回目を跨ぐ直前」に左の線が X cm外へ動かされる。
- 影響が出るのはそれ以降の動き。
- 余分な移動が発生する場面
- 中央 → 左に行くとき（+X）
- 左 → 中央に戻るとき（+X）
→ 1セット（4回）ごとに 合計 +2X cm の余分な移動。
- 計算の考え方
- 「いたずら後に何回動いたか」= (K - 4N) を基準にする。
- (K - 4N) // 4 セット分で 2X を繰り返し加算。
- 余りの動き（(K - 4N) % 4）に応じて調整。
余りが3のとき → 中央から左に行く途中まで到達 → さらに +X。
- 最終式のイメージ
result = 2 * X * ((K - 4N) // 4)- もし (K - 4N) % 4 >= 3 なら +X を加える。
- アルゴリズムの工夫
- K の最大値が10億 → 単純ループは非効率（最大2.5億回）。
- 規則性を使って 数式化（O(1)解法） すれば高速に計算可能。