paizaラーニング レベルアップ問題集 二分探索メニュー応用編 JavaScript カードゲーム (paizaランク S 相当)

カードゲーム (paizaランク S 相当)

考え方

好きな順番でカードを出せるので、好きな順にソートできる。
考えやすいように、paizaの手札を小さい順にソートする。

xで二分探索をする。
仮にx=midとして、ゲームをしてみる。

自分のカードの一次関数はx=midを代入し計算して整数値にしておく。
考えやすいように、自分の手札を小さい順にソートする。

ゲームにできるだけ勝つ方法。
自分のカードを小さい順に見ていく。
相手のカードも小さい方から順に比較する。相手の見ているカードのインデックスを変数posとする。
今見ている自分のカードが、相手のカードより大きければ、勝ち。
勝ったら、相手の次に小さいカードと、自分の次に小さいカードを比較する。
負けたら、相手のカードはそのままに、自分の次に小さいカードを比較する。
これを繰り返す。
このやり方だと、posの値がそのまま自分の得点になっている。

ゲームが終了したら、勝敗判定をする。
自分の得点が過半数N/2得点を超えれば勝ち。
それ以下なら負け。

以上、二分探索が終わったら、xの最小値rightを出力する。

解答例(C++の場合参考)

考え方に沿って実装。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const [N] = lines[0].split(" ").map(Number);
//自分のカードA,B paizaくんのカードC
const [A, B, C] = [[], [], []];
for (let i = 0; i < N; i++) {
  [A[i], B[i], C[i]] = lines[i + 1].split(" ").map(Number);
}
//好きな順番でカードを出せるので、考えやすいように昇順ソート
C.sort((a, b) => a - b);

//xについて二分探索
let [left, right] = [-1000000001, 1000000001];//条件より1 ≦ A_i, B_i, C_i ≦ 1,000,000,000 = 10^9なので

while (right - left > 1) {
  const mid = Math.trunc((right + left) / 2);

  //自分のカードについて
  const myCards = [];
  for (let i = 0; i < N; i++) {
    myCards[i] = A[i] * mid + B[i];//一次関数を計算しておく
  }
  myCards.sort((a, b) => a - b);//考えやすいように昇順ソート
  
  //ゲーム開始
  //自分がが出すカードについて順番に見ていく
  //paizaのカードと先頭から比べていく
  let pos = 0;//見ているpaizaのカードのインデックス
  for (let i = 0; i < N; i++) {
    //勝ち
    if (myCards[i] > C[pos]) { //自分のカード＞paiza君のカード
      pos++;//paiza君のカードの次を見る=posの値が自分の得点
    }
  }
  
  //ゲーム終了後、勝敗判定
  //自分が勝ったら、x小さくできる
  if (pos > N / 2) { //自分の得点posが過半数N/2を取れば勝ち
    right = mid;   
  //自分が負けか、引き分けだったら、x大きくする  
  } else {
    left = mid;
  } 
}
//勝ちなのでright出力
console.log(right);

解答例(pythonの場合参考)

xについて二分探索関数を定義して実装。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const [N] = lines[0].split(" ").map(Number);

const [A, B, C] = [[], [], []];
for (let i = 0; i < N; i++) {
  [A[i], B[i], C[i]] = lines[i + 1].split(" ").map(Number);
}
//あらかじめソートしておく
C.sort((a, b) => a - b);

//xについて二分探索関数を定義
//自分が勝った時は true, paiza 君が勝った時は flase を返す
const check = x => {
  //ab : x の時の自分の整数
  const ab = [];
  for (let i = 0; i < N; i++) {
    ab.push(A[i] * x + B[i]);
  }
  ab.sort((a, b) => a - b);//考えやすいように昇順ソート
  
  let pos = 0;//見ている相手のカードのインデックス
  //自分がが出すカードについて順番に見ていく
  //paizaのカードと先頭から比べていく
  for (let i = 0; i < N; i++) {   
    if (ab[i] > C[pos]) { //勝ち
      pos++;//paizaのカードの次を見る＝見ていたpaizaカードを消す=自分の得点
    }
  }
  
  //ゲーム終了後、勝敗判定
  //自分の半分以上のカードがpaiza君が持っている c の配列のカードより大きい => 自分の勝利
  if (pos > N / 2) { //自分が勝ったら、x小さくできる
    return true;   
  } else { //自分が負けか、引き分けだったら、x大きくする  
    return false;
  } 
};

let [left, right] = [-1000000001, 1000000001];
while (right - left > 1) {
  const mid = Math.trunc((right + left) / 2);
  //ゲーム開始
  if (check(mid)) {
    right = mid;
  } else {
    left = mid;
  }
}
//勝ちなのでright出力
console.log(right);