結果
問題 |
No.3038 シャッフルの再現
|
ユーザー |
|
提出日時 | 2025-02-28 22:01:52 |
言語 | JavaScript (node v23.5.0) |
結果 |
AC
|
実行時間 | 59 ms / 2,000 ms |
コード長 | 3,330 bytes |
コンパイル時間 | 216 ms |
コンパイル使用メモリ | 6,820 KB |
実行使用メモリ | 44,188 KB |
最終ジャッジ日時 | 2025-02-28 22:01:55 |
合計ジャッジ時間 | 2,384 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 21 |
ソースコード
function Main(input) { input = input.split("\n").map((line) => line.trim()); const [N, K] = input[0].split(" ").map(Number); console.log(K - 1); } class FenwickTree { constructor(n) { this.n = n; this.tree = new Array(n + 1).fill(0); } /** * BIT に値を加算する * @param {number} index - 0-indexed の更新位置 * @param {number} value - 加算する値 */ update(index, value) { for (let i = index + 1; i <= this.n; i += i & -i) { this.tree[i] += value; } } /** * index までの和を求めるクエリ(区間 [0, index] の和) * @param {number} index - 0-indexed の位置 * @returns {number} 区間和 */ query(index) { let sum = 0; for (let i = index + 1; i > 0; i -= i & -i) { sum += this.tree[i]; } return sum; } } /** * 配列 arr の転倒数(inversion count)を BIT を利用して求める関数 * @param {number[]} arr - 転倒数を数えたい配列(必ずしも連続整数でなくてもよい) * @returns {number} 転倒数 */ function countInversions(arr) { const n = arr.length; // 座標圧縮(重複があっても大丈夫) const sorted = Array.from(new Set(arr)).sort((a, b) => a - b); const rank = new Map(); for (let i = 0; i < sorted.length; i++) { rank.set(sorted[i], i); } const m = sorted.length; const bit = new FenwickTree(m); let inversions = 0; // 後ろから走査して、各要素より小さい値の件数を足し合わせる for (let i = n - 1; i >= 0; i--) { const r = rank.get(arr[i]); inversions += bit.query(r - 1); bit.update(r, 1); } return inversions; } /** * getInversion 関数 * @param {number[]} aprime - 置換後の配列 A′ * @param {number[]|null} [base=null] - 元の配列 A。指定されない場合は、[1, 2, …, N] を仮定する * @returns {number} base と aprime の間の転倒数 * * ※ base を指定した場合、aprime と base は同じ多重集合である前提です。 * base の各要素の出現順序に対応して、 aprime の中の位置を順に取り出し、 * その順列の転倒数が求める結果となります。 */ function getInversion(aprime, base = null) { const n = aprime.length; // base が指定されなければ、デフォルトは [1, 2, …, n] if (base === null) { return countInversions(aprime); } else { // aprime 内の各値について、登場するインデックスをリスト化 const valueToIndices = new Map(); for (let i = 0; i < n; i++) { const x = aprime[i]; if (!valueToIndices.has(x)) { valueToIndices.set(x, []); } valueToIndices.get(x).push(i); } // base 配列の順序に合わせ、aprime の対応する位置で構成される配列 perm を作成する const perm = []; for (let i = 0; i < n; i++) { const x = base[i]; if (!valueToIndices.has(x) || valueToIndices.get(x).length === 0) { throw new Error("base と aprime の要素(多重集合)が一致していません"); } perm.push(valueToIndices.get(x).shift()); } // perm は 0 〜 n-1 の順列になっているので、これの転倒数を返す return countInversions(perm); } } Main(require("fs").readFileSync(0, "utf8"));