AtCoder精選良問「D - Shipping Center」Diff 945
この記事はAtCoderの精選良問集マガジンの中の記事です。
私が良問だと思った問題を解説付きでまとめています。
問題リンク
問題概要
1からNの番号がついたN個の荷物と、1からMの番号がついたM個の箱がある。
荷物iの大きさはWiで、価値はVi。
箱iには大きさがXi以下の荷物を入れることができる。1つの箱に2つ以上の荷物を入れることはできない。
Q個のクエリが与えられ、各クエリでは2つの整数L,Rが与えられる。
L, L+1, ..., RのR-L+1個の箱は使えない。
残りの箱の中に同時に入れることができる荷物の価値の合計の最大値を出力する。
考え方
考えるファクターが多すぎて頭がこんがらがる人が多いのではないかと思う。
この問題の難しいところは、競プロをやっている人なら齧ったことのある「ピン」とくるキーワードを散りばめて誤った解法に導かれてしまいそうになるところだ。
例えば荷物の重さ、価値、価値の最大というキーワードからは有名なナップサック問題が連想される。
また、LからRが使えないという意味ありげな条件からは累積和を使ってなんやかんやするんじゃないか、という考えも生まれやすい。
これらの解法を使って解けるのかもしれないが、もっとシンプルな問題なように思う。意味ありげなLとRのことや重さのことは忘れて以下のように考えてみる。
箱がいくつかある
箱には一つしか荷物を入れられない
価値を最大化するにはどうすればいいか
明らかに価値がでかいものからつめていくのが正解だ。
ここに重さというファクターが入っても同じことだ。
箱には１つしか荷物が入らないので、重かろうが軽かろうがとにかく価値がでかいものを入れた方がいい。
注意するのはいま注目している荷物を入れるときに、なるべく容量がぎりぎりの箱に入れるようにすること。その方が次の荷物を入れられる可能性が高くなり有利になる。
累積和や動的計画法のようなオシャレな感じのするアルゴリズムはついつい使いたくなってしまう。それがこの問題を難しくさせている。
しかし、泥臭く貪欲に実装するだけで答えが出せる。
実装
制約に目をむけてみるとN,M,Qの制約は50以内ととても小さいので、愚直にループを回しても高速に動作する。
どうでもいい話だが過去に港湾現場の監督をしていたことがあるので、こういう港の現場を連想させる問題には心がときめいてしまう。そのためついつい、packingList(積荷明細)、container(コンテナ)などの普通なら使わない長めの変数を採用させてもらった。
import { createInterface } from "readline";
import * as fs from "fs";
import { log } from "console";
function main() {
const [n, m, q] = nextNums(3)
// 荷物
const packingList: number[][] = []
for (let i = 0; i < n; i++) {
// [weight,value]
const item = nextNums(2)
packingList.push(item)
}
// 価値の低い順にsort
packingList.sort((a, b) => a[1] - b[1])
// 箱の配列
const containers = nextNums(m)
// クエリを繰り返す
for (let i = 0; i < q; i++) {
let [left, right] = nextNums(2)
// 0インデックスのため
left--
right--
// 使える箱
const canUseBoxies: number[] = []
for (let j = 0; j < m; j++) {
// L,Rの範囲外なら使える
if (j < left) canUseBoxies.push(containers[j])
if (j > right) canUseBoxies.push(containers[j])
}
// 小さい箱につめてくためsort
canUseBoxies.sort((a, b) => a - b)
// packingListの中身を別配列に
const items: number[][] = []
for (const item of packingList) {
items.push(item)
}
let ans = 0
while (items.length > 0) {
// 価値が小さい順に並んでいるのでpop()したものが一番価値が大きい
const [weight, value] = items.pop()!
for (let j = 0; j < canUseBoxies.length; j++) {
const boxSize = canUseBoxies[j]
// 箱に詰められる
if (boxSize >= weight) {
ans += value
// 次に詰められないようにサイズ-1にしておく
canUseBoxies[j] = -1
break
}
}
}
log(ans)
}
}
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();
}