【シミュレーション 4】位置情報システム

Posted at 2025-09-19

今回は paiza の「【シミュレーション 4】位置情報システム」の問題に挑戦！

問題概要

目的

与えられた時間ごとのユーザー位置情報をもとに、時刻 0 〜 100 のすべての座標を計算する。

入力

n（位置情報の数）
続く n 行で t_i y_i x_i（時刻とその時点の座標）

出力

時刻 0 〜 100 の各座標を順番に出力
- 例: y_0 x_0, y_1 x_1, …, y_100 x_100

座標計算のルール

T = t_i の場合
- その時刻の座標はそのまま y_i, x_i
t_i < T < t_{i+1} の場合
- 等速直線移動を仮定して座標を計算
- 小数になったら切り捨てまたは切り上げ

入力例:

2
0 0 0
100 100 100

出力例:

✅ OK例:

const rl = require('readline').createInterface({ input:process.stdin });
const lines = [];
rl.on('line', (line) => lines.push(line));
rl.on('close', () => {
    const n = Number(lines[0]);
    const locationInfo = lines.slice(1).map(l => l.split(' ').map(Number));

    const result = [];

    for (let i = 1; i < n; i++) {
        const [t1, y1, x1] = locationInfo[i - 1];
        const [t2, y2, x2] = locationInfo[i];
        const dt = t2 - t1   // 時間の差 = t1 ~ t2 の区間で移動した時間
        const dy = y2 - y1   // Y方向の差 = y1 = y2 の区間でy方向に移動した距離
        const dx = x2 - x1   // X方向の差 = x1 = x2 の区間でx方向に移動した距離


        for (let T = t1; T <= t2; T++) {
            // T時の進行割合    
            const ratio = (T - t1) / dt;
            
            // t1〜Tまで、yとxの方向で動いた距離
            const moveY = dy * ratio;
            const moveX = dx * ratio;
            
            // 区間の始めの位置に足す　→ 小数が出たら floor/ceil で丸める
            const y = Math.floor(y1 + moveY);
            const x = Math.floor(x1 + moveX);

            result[T] = [y, x];
        }
    }

    result.forEach(([y, x]) => console.log(`${y} ${x}`));
});

各区間ごとに座標を計算
- 各区間の差分を計算：
  - dt = t2 - t1（時間の長さ）
  - dy = y2 - y1（Y方向の移動量）
  - dx = x2 - x1（X方向の移動量）
区間内の各時刻 T の座標を計算
- for T = t1; T <= t2; T++ でループ
- T時点での進行割合を計算： ratio = (T - t1) / dt
- 移動距離を計算：
  - moveY = dy * ratio
  - moveX = dx * ratio
- その時刻の座標を計算して丸める：
  - y = Math.floor(y1 + moveY)
  - x = Math.floor(x1 + moveX)
- result[T] に [y, x] を格納
最終的に全時刻 T = 0〜100 の座標を出力
- result.forEach(([y, x]) => console.log(${y} ${x}))

累積方式は小数点を切り捨てたり丸めたりすると誤差が次のステップに伝播していく → 最終的に大きくずれる
比率方式は常に初期値 + 区間全体の比率で計算するので、各時刻の誤差が「その時点だけ」に収まる

「現在時刻が区間全体に対してどれくらい進んだかの割合」を使う
→ 累積誤差を避けつつ、等速直線移動を正確に再現できる

🗒️ まとめ

累積方式

各ステップで移動距離を足す → 小数を丸めると誤差が次に伝播

比率方式

現在時刻 T が区間 [t_i, t_{i+1}] に対してどれだけ進んだかを割合で計算
座標 = 初期座標 + 差分 × 進行割合
各時刻の誤差がその時点に収まる → 累積誤差なし

コード実装の流れ

各区間 [t_i, t_{i+1}] の差分を計算
- dt = t2 - t1、dy = y2 - y1、dx = x2 - x1
区間内の各時刻 T で進行割合 ratio = (T - t1)/dt を計算
移動距離 moveY = dy * ratio、moveX = dx * ratio を求める
現在時刻の座標 y = floor(y1 + moveY)、x = floor(x1 + moveX)
配列に格納して最後にすべて出力

僕の失敗談(´;ω;｀)と解決法🐈

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