結果

問題 No.3680 セグメント釣り
コンテスト
ユーザー yiwiy9
提出日時 2026-09-08 03:11:01
言語 Rust
(1.97.1 + proconio + num + itertools + ACL)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 94 ms / 2,000 ms
+ 49µs
コード長 1,867 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 21,506 ms
コンパイル使用メモリ 190,436 KB
実行使用メモリ 9,928 KB
最終ジャッジ日時 2026-09-08 03:11:34
合計ジャッジ時間 32,781 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use proconio::input;

const INF: usize = 1 << 60;

/// https://yukicoder.me/problems/no/3680
/// - 何ごとの話にすると見やすい？ 何だけ持てばいい？
///   経路そのものではなく、経路中に通る最大の高さ `H` ごとの話にして `H` だけ持つ。
/// - それについて、何が分かれば答えになる？
///   `H` を固定したときの縦移動コストと、高さ `H` で横にまたぐタイル数の和が分かればよい。
/// - 何を捨ててよく、なぜそれで足りる？ 何が効く / 何が禁止？
///   `H` まで上がって横移動してから下れば下界を達成でき、`x < 2^60` なので `H > 60` は縦コストだけ増えて不要。
/// - その情報をどう更新 / 判定 / 集計すれば実装できる？
///   `H = max(Sy, Ty)..=60` を列挙し、縦の `(H-Sy)+(H-Ty)` と横の `|(Sx>>H)-(Tx>>H)|` の最小を取る。
///   `max(Sy, Ty) >= 60` なら横コストは既に `0` なので、答えは `|Sy-Ty|`。
///
/// 高さ `H` のタイルは横幅が `2^H` なので、座標 `x` のタイル番号は `floor(x / 2^H) = x >> H`。
/// 横移動で支払う回数は始点と終点のタイル番号の差だから、`horizontal_cost = |(Sx>>H)-(Tx>>H)|` となる。
fn main() {
    input! {
        t: usize,
        cases: [(usize, usize, usize, usize); t],
    }

    for (sx, sy, tx, ty) in cases {
        let min_height = sy.max(ty);
        if min_height >= 60 {
            println!("{}", sy.abs_diff(ty));
            continue;
        }

        let mut ans = INF;
        for height in min_height..=60 {
            let vertical_cost = (height - sy) + (height - ty);
            let horizontal_cost = (sx >> height).abs_diff(tx >> height);
            ans = ans.min(vertical_cost + horizontal_cost);
        }

        println!("{}", ans);
    }
}
0