結果

問題 No.3038 シャッフルの再現
ユーザー bfs84
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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"));
0