AtCoder精選良問「D - Jumping Takahashi 2」Diff 1203

この記事はAtCoderの精選良問集マガジンの中の記事です。
私が良問だと思った問題を解説付きでまとめています。

AtCoder 精選良問集 Diff 茶後半～水前半｜Qlitre｜note

問題リンク

D - Jumping Takahashi 2

問題概要

高橋君が住んでいる街にはN個のジャンプ台があり、各ジャンプ台は2次元平面上の一点に位置している。

• i番目のジャンプ台は座標(x_i, y_i)に位置し、ジャンプ台のパワーはP_i。

• ジャンプ力はSで表され、初めはS=0。訓練を一回行うたびにSは1増える。

• ジャンプ台のパワーP_iとジャンプ力Sが、移動先と移動元のジャンプ台間のマンハッタン距離以上であれば、移動できる。

問題は、適切なジャンプ台を始点としたときに、そのジャンプ台からどのジャンプ台にも何回かのジャンプで移動できるようにしたい。そのようなときに、高橋君が最低で何回訓練を行う必要があるかを求める。

考え方

まず、SとかPとか難しいことは考えずに図を適当に書いてみる。

ジャンプ台からジャンプ台へは相互に行き来が可能だが、それぞれにパワーがあるため、飛べる距離が異なる。
上の図のように、３から１に飛べるが、１から３には飛べないというようなケースが存在することを理解する。

ここで、制約に目を向けるとNは200までと小さいので、N個の頂点を始点として、幅優先探索をして全探索しても計算量はそこまで大きくならない。

具体的にはある頂点にいるときにS * その頂点のパワーがマンハッタン距離以上なら移動ができる。これを繰り返して、全部の頂点を訪れることができるかを調べればいい。

ネックになるのが座標の位置。
-10 ^ 9　～ 10^9までと非常に大きい。
そのためSを全探索するのは明らかに厳しい。
こういう一方の全探索は可能そうだけど、もう一方の全探索が厳しそう、という場合は、一方を二分探索しつつ、もう一方を全探索で調べる。

この問題ではSをゼロから最大値までの範囲で二分探索し、その都度BFSを回して答えを狭めていくイメージ。

実装

import { createInterface } from "readline";
import * as fs from "fs";
import { log } from "console";
import { exit } from "process";

class Node<T> {
    public value: T;
    public prev: Node<T> | null;
    public next: Node<T> | null;

    constructor(value: T) {
        this.value = value;
        this.prev = null;
        this.next = null;
    }
}

export class Deque<T> {
    private head: Node<T> | null = null;
    private tail: Node<T> | null = null;
    private length = 0;

    public append(value: T): void {
        const node = new Node(value);
        if (!this.head) {
            this.head = node;
            this.tail = node;
        } else {
            node.prev = this.tail;
            this.tail!.next = node;
            this.tail = node;
        }
        this.length++;
    }

    public appendleft(value: T): void {
        const node = new Node(value);
        if (!this.head) {
            this.head = node;
            this.tail = node;
        } else {
            node.next = this.head;
            this.head!.prev = node;
            this.head = node;
        }
        this.length++;
    }

    public pop(): T | null {
        if (!this.tail) {
            return null;
        }
        const node = this.tail;
        if (this.head === this.tail) {
            this.head = null;
            this.tail = null;
        } else {
            this.tail = node.prev;
            this.tail!.next = null;
            node.prev = null;
        }
        this.length--;
        return node.value;
    }

    public popleft(): T | null {
        if (!this.head) {
            return null;
        }
        const node = this.head;
        if (this.head === this.tail) {
            this.head = null;
            this.tail = null;
        } else {
            this.head = node.next;
            this.head!.prev = null;
            node.next = null;
        }
        this.length--;
        return node.value;
    }

    public getLength(): number {
        return this.length;
    }

    public toArray(): T[] {
        const result: T[] = [];
        let current = this.head;
        while (current) {
            result.push(current.value);
            current = current.next;
        }
        return result;
    }
}

function main() {
    const n = nextNum();
    const pos: number[][] = [];
    // 各点の座標を取得
    for (let i = 0; i < n; ++i) {
        const arr = nextNums(3);
        pos.push(arr);
    }

    let ng = 0
    // 最大のSは(-10^9,-10^9) => (10^9,10^9)の時の10^9 * 4
    // 少し大きめにとっておく
    let ok = 10 ** 10
    while (ok - ng > 1) {
        // 中間値を取得
        const midS = Math.floor((ok + ng) / 2);
        // graphを構築
        const graph: Record<number, number[]> = {};
        // Nは小さいので全通り調べる
        for (let i = 0; i < n; ++i) {
            const [x1, y1, p] = pos[i];
            for (let j = 0; j < n; ++j) {
                if (i === j) continue;
                const [x2, y2, _] = pos[j];
                // マンハッタン距離
                const dist = Math.abs(x1 - x2) + Math.abs(y1 - y2);
                // ジャンプ力
                const jumpPower = p * midS;
                if (dist <= jumpPower) {
                    if (graph[i] === undefined) {
                        graph[i] = [];
                    }
                    graph[i].push(j);
                }
            }
        }
        let okFlg = false;
        // BFSで到達可能かを調べる
        for (let start = 0; start < n; start++) {
            // dequeを初期化
            const que = new Deque<number>();
            // 訪れた頂点を管理
            const vis = new Set<number>();
            que.append(start);
            vis.add(start);
            while (que.getLength() > 0) {
                const now = que.popleft()!;
                if(!graph[now]) continue;
                for (const vertex of graph[now]) {
                    if (vis.has(vertex)) continue;
                    vis.add(vertex);
                    que.append(vertex);
                }
            }
            // 訪れた頂点数がnと等しければ到達可能
            if (vis.size === n) {
                okFlg = true;
                break;
            }
        }
        if (okFlg) {
            // もっとSを小さくできる
            ok = midS;
        } else {
            // もっとSを大きくしないといけない
            ng = midS;
        }
    }
    console.log(ok);
}

let inputs = "";
let inputArray: string[];
let currentIndex = 0;

function next() {
    return inputArray[currentIndex++];
}
function nextNum() {
    return +next();
}
function nextBigInt() {
    return BigInt(next());
}
function nexts(length: number) {
    const arr = [];
    for (let i = 0; i < length; ++i) arr[i] = next();
    return arr;
}
function nextNums(length: number) {
    const arr = [];
    for (let i = 0; i < length; ++i) arr[i] = nextNum();
    return arr;
}
function nextBigInts(length: number) {
    const arr = [];
    for (let i = 0; i < length; ++i) arr[i] = nextBigInt();
    return arr;
}

// デバッグ環境がWindowsであれば条件分岐する
if (process.env.OS == "Windows_NT") {
    const stream = createInterface({
        input: process.stdin,
        output: process.stdout,
    });
    stream.on("line", (line) => {
        inputs += line;
        inputs += "\n";
    });
    stream.on("close", () => {
        inputArray = inputs.split(/\s/);
        main();
    });
} else {
    inputs = fs.readFileSync("/dev/stdin", "utf8");
    inputArray = inputs.split(/\s/);
    main();
}