AtCoder精選良問「D - LRUD Instructions」Diff 1119
この記事はAtCoderの精選良問集マガジンの中の記事です。
私が良問だと思った問題を解説付きでまとめています。
問題リンク
問題概要
まず、最大で10^9 x 10^9からなるグリッドの広さと、高橋君の初期位置が与えられる。グリッド上にはN個の壁があり、(r1,c1),(r2,c2)…(rN,cN)で位置が示される。
高橋君はQ個のL,R,U,Dのいずれかの方向と移動回数を示す指示を与えられる。高橋君はいずれかの方向に壁にぶつかるまで、与えられた回数分の移動をする。
それぞれの指示が与えられた後、高橋君の位置を出力する、という問題。
考え方
まずは入力例1の状況をみてみる
与えられるグリッドと高橋君の初期位置は下記の通りです。 ここで、# は壁のマスを、T は高橋君がいるマスを表し、. がその他のマスを表します
...#.
.#...
.....
...T.
..#..この場合5 x 5のマスなので、それぞれの指示ごとにシミュレーションをしても答えを出すことは可能だ。
ただ、与えられるグリッドは、制約を見ると最大で10^9 x 10^9まであるので、シミュレーションを愚直に実装すると明らかにTLE。
そこで、壁の数の最大値をみてみる。
200,000程と、小さくはないもののなんとか処理ができそうという感じの数字。
ここで、高橋君の移動は上下左右のいずれにしか行われないということに注目をしてみる。
ということは、左右に移動するときは、高橋君がいる行にある壁だけを考えればよい。上下に移動するときは今いる列にある壁だけを考える。
...#..
#..#.#
......
......
...#..例えば特定の列にある壁を示すtateと特定の行にある壁を示すyokoという
辞書を用意する。上記の図を示すとこんな形になる。
// 4列目の上から1,2,5マス目に壁がある
tate={4:[1,2,5]}
// 2行目の左から1,4,6マス目に壁がある
yoko={2:[1,4,6]}いい感じになってきた。
後は高橋君のいまいる位置からどこまで移動できるかを考えればよい。
調べるべきインデックスは二分探索をして高速に求める。
Pythonなどではbisect_leftなどの標準ライブラリを用いればいい。
TypeScriptには標準ではないので、似たようなものを自作しておく。
/**
*
* @param arr ソート済みの配列
* @param x 検索値
* @returns
* 値 x が最初に現れるインデックスを返す。
* x が arr 内に存在しない場合は、x を挿入するためのインデックスを返す
*/
export const bisectLeft = (arr: number[], x: number, lo: number = 0, hi: number = arr.length): number => {
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (arr[mid] < x) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
}この関数に配列と値xを与えると、x を挿入するためのインデックスを返す。
// 壁
[2, 6, 9, 15]例えばこんな感じの壁を示す配列と、今いる位置の８を渡したとする。
挿入されるべきインデックスは6の次なので、2となる。
後は左もしくは上に移動する場合は壁[2-1]=6と移動先を比較すればいいし、右もしくは下に移動する場合は、壁[2]=9と比較する。
二分探索をするためには配列がソートされている必要があるので、一度値を保存したら、再度キーを繰り返してソートする。
その直前に答えの最小の値-1である0と最大の値+1であるh+1, w+1、通称"番兵"を入れておくとよい。こうしておくと、今の位置のインデックスを取得した際に、必ず配列の間に収まるので、その後の計算がおこないやすい。
L,R,U,Dの4パターンで条件を書くので、重実装となるが、根気強く書けば答えにたどり着ける。
実装
import { createInterface } from "readline";
import * as fs from "fs";
import { log } from "console";
import { exit } from "process";
/**
*
* @param arr ソート済みの配列
* @param x 検索値
* @returns
* 値 x が最初に現れるインデックスを返す。
* x が arr 内に存在しない場合は、x を挿入するためのインデックスを返す
*/
export const bisectLeft = (arr: number[], x: number, lo: number = 0, hi: number = arr.length): number => {
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (arr[mid] < x) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
}
function main() {
const [h, w] = nextNums(2)
// 高橋君の位置
let [r, c] = nextNums(2)
const n = nextNum()
// ある列にある縦方向の壁
const tate: Record<number, number[]> = {}
// ある行にある横方向の壁
const yoko: Record<number, number[]> = {}
for (let i = 0; i < n; i++) {
const [rw, cw] = nextNums(2)
if (yoko[rw]) {
yoko[rw].push(cw)
} else {
yoko[rw] = [cw]
}
if (tate[cw]) {
tate[cw].push(rw)
} else {
tate[cw] = [rw]
}
}
// 配列をソートする
// ついでに両端に壁の最小値-1と最大+1を加える。
// こうしておくと後の二分探索時のインデックスが、かならず配列内に収まる。
for (const key in yoko) {
yoko[key].push(0)
yoko[key].push(w + 1)
yoko[key].sort((a, b) => (a - b))
}
for (const key in tate) {
tate[key].push(0)
tate[key].push(h + 1)
tate[key].sort((a, b) => (a - b))
}
const q = nextNum()
for (let i = 0; i < q; i++) {
const d = next()
const cnt = nextNum()
// 左方向へ移動
if (d == 'L') {
// 移動後の場所、左端の１が最大となるのに注意
const cNext = Math.max(1, c - cnt)
if (!yoko[r]) {
// 壁がない場合は移動できる
c = cNext
} else {
// 壁を取り出す
const walls = yoko[r]
// indexを取得
const idx = bisectLeft(walls, c)
// 左にある壁
const wall = walls[idx - 1]
// 一番近い壁の一つ手前か、行ける場所の大きい方まで移動可能
c = Math.max(wall + 1, cNext)
}
} else if (d == 'R') {
// 右に移動する場合。右端まで最大で行ける
const cNext = Math.min(w, c + cnt)
if (!yoko[r]) {
c = cNext
} else {
const walls = yoko[r]
const idx = bisectLeft(walls, c)
// 右にある壁
const wall = walls[idx]
// 右にある壁の手前もしくは行ける場所の小さい場所までいける
c = Math.min(wall - 1, cNext)
}
} else if (d == 'U') {
// 上下移動。考え方は左右と同じ
const rNext = Math.max(1, r - cnt)
if (!tate[c]) {
r = rNext
} else {
const walls = tate[c]
const idx = bisectLeft(walls, r)
const wall = walls[idx - 1]
r = Math.max(wall + 1, rNext)
}
} else if (d == 'D') {
const rNext = Math.min(h, r + cnt)
if (!tate[c]) {
r = rNext
} else {
const walls = tate[c]
const idx = bisectLeft(walls, r)
const wall = walls[idx]
r = Math.min(wall - 1, rNext)
}
}
// 答えの出力
log(r, c)
}
}
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();
}この記事が気に入ったらサポートをしてみませんか？