paizaラーニング レベルアップ問題集 ソートメニュー応用編 JavaScript 座標圧縮

座標圧縮 (paizaランク B 相当)

JavaScriptで解いてみました。

解答例(単純に探索する)

色を塗ったマスが左から何番目かわかりやすいように、Aを昇順にソートする。

数列Xの質問に答えていく時、単純に「数列Aの中から、X[i]を探して、出力する」を繰り返す。時間はかかるが時間内に処理がされる。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
//N 個のマスに色を塗る, 全部で Q 回行われる質問
const [N, Q] = lines[0].split(" ").map(Number);
//色を塗ったマス番号の数列 A
const A = lines[1].split(" ").map(Number);
//質問の数列 X, X_iは色が塗られているマスの何番目か知りたい
const X = lines[2].split(" ").map(Number);

//数列Aを昇順に並べ替える
A.sort((a, b) => a - b);

//数列Xの質問に答えていく
for (let i = 0; i < Q; i++) {
    console.log(A.indexOf(X[i]) + 1);
}

解答例(辞書を使う)

条件より、Aの要素数 1 ≦ N ≦ 100,000, Xの要素数 1 ≦ Q ≦ 100,000なので、計算量が多くなり、多少時間がかかる。

辞書を使って、処理時間を短縮してみた。

辞書に登録するときは、キーを"マスの番号"、値を"左から数えて何番目か"、にする。
すると、数列Xの質問に答えていくとき、"マスの番号"から、一発で答え"左から数えて何番目か"がわかる。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
//N 個のマスに色を塗る, 全部で Q 回行われる質問
const [N, Q] = lines[0].split(" ").map(Number);
//色を塗ったマス番号の数列 A
const A = lines[1].split(" ").map(Number);
//質問の数列 X, X_iは色が塗られているマスの何番目か知りたい
const X = lines[2].split(" ").map(Number);

//数列Aを昇順に並べ替える
A.sort((a, b) => a - b);

//辞書に登録していく
let compressed = new Map();
for (let i = 0; i < N; i++) {
    //キーをマスの番号、値を左から数えて何番目か、にする
    compressed.set(A[i], i + 1);
}

//数列Xの質問に答える
for (let i = 0; i < Q; i++) {
    //左から X_i 番目のマスは色が塗られているマスのうち左から何番目のマスか出力
    console.log(compressed.get(X[i]));
}