【JavaScript】ABC389まとめ（A~E）

AtCoder Beginner Contest 389

ABCDの4完（57分1ペナ）でした。
977perfでレートは977->977（+0）となりました。
C問題とD問題で配列外参照にハマってペナり、E,Fともにかなり難しく解けなかったのでパフォが伸びず足踏みとなりました。
今回はA~Dとコンテスト後にupsolveしたEをまとめます。

A - 9x9

入力の1文字目と3文字目の積を出力しましょう。
なお、JavaScriptは文字列の積は自動で数値に変換してくれるため安全です。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const s = input[0].split("");
  console.log(s[0] * s[2]);
}

Main(require("fs").readFileSync(0, "utf8"));

B - tcaF

$1!,2!,3!,…$の順に$X$と同じかどうかを確認します。
JavaScriptのNumber型は$10^{14}$あたりでオーバーフローするため、BigInt型を使う必要があります。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const X = BigInt(input[0]);

  let cur = 1n;
  for (let i = 0; i < 30; i++) {
    cur *= BigInt(i + 1);
    if (cur == X) return console.log(i + 1);
  }
}

Main(require("fs").readFileSync(0, "utf8"));

C - Snake Queue

クエリ2がない場合を考えると、ヘビの長さの累積和$arr$を用意しておき、クエリ1と3を以下のように処理します。

• $(1, l)$で$arr$に$arr[-1]+l$を追加する
• $(3, x)$で$arr$の$x$番目を出力する

3,5,7のヘビを追加した場合
arr = [0,3,8,15] ※先頭の0はあらかじめ追加しておく

例えば、クエリ[3, 2]となった場合、arr[1]の3を出力

では、クエリ1がある場合はどうすれば良いかを考えましょう。
クエリ1は一旦このままにしておいて、どうすればクエリ3に対応できるかを考えます。
クエリ2で退出したヘビの個数$cnt$と、長さの合計$sum$さえ記録しておけば、$x$番目のヘビは$x+cnt$番目、ヘビの合計値は$arr[x-cnt]-sum$と表すことができます。
$x$を0-indexedに直すことだけ気をつけて実装しましょう。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const Q = Number(input[0]);

  // arr:= ヘビの長さの累積和
  // cnt:= ヘビが退出した回数、sum:= 退出したヘビの長さの合計
  const arr = [0];
  let [cnt, sum] = [0, 0];
  for (let i = 0; i < Q; i++) {
    const query = input[i + 1].split(" ").map(Number);
    // クエリ1: ヘビを最後尾に追加する。arr.at(-1)はarr[arr.length - 1]と同じ
    if (query[0] == 1) arr.push(query[1] + arr.at(-1));
    // クエリ2: ヘビを先頭から取り出す代わりに、cnt+=1, sum+=arr[cnt]とする
    else if (query[0] == 2) sum = arr[++cnt];
    // クエリ3: 該当するヘビはquery[1] - 1 + cnt番目のヘビ。また、退出したヘビの長さも引く
    else console.log(arr[query[1] - 1 + cnt] - sum);
  }
}

Main(require("fs").readFileSync(0, "utf8"));

D - Squares in Circle

まず、正方形の四方の点が小数点だと誤差が怖いので$x$軸、$y$軸両方二倍しておきます。このとき、例えば中心の正方形の四隅の点の座標は$(-1,1),(1,1),(1,-1),(-1,-1)$です。
この時重要な事実として正方形の四隅の$x$座標、$y$座標ともに奇数となります。
以下、二分探索を使って一番ナイーブに解いた例を説明します。

正方形の右上の点が第一象限にあるような正方形の個数

考えやすくするために、正方形の右上の点が第一象限$(x>0,y>0)$にあるときだけを考えましょう。
このとき、$x=1,3,5,...,2R-1$それぞれについて、$x^2+y^2≦(2R)^2$が成り立つような$y$の個数が、「右上の点が第一象限にあるような正方形の個数」となります。

※補足
正方形の右上の点は座標中心からの最遠点なので、正方形の右上の点が円に内包される時正方形全体が円に内包されることがいえます。

そして、$x^2+y^2≦(2R)^2$が成り立つような$y$の上限は二分探索で高速に探索することができます。
例えばこれを$ymax$とおけば、求める個数は$(ymax-1)/2+1$です。

これを$x=1,3,5,...,2R-1$それぞれについて行うことで、正方形の右上の点が第一象限$(x>0,y>0)$にあるような正方形の個数が求まりました。

正方形の右上の点が第一象限、第四象限にあるような正方形の個数

次に、対象範囲を広げて円の上半分での正方形の個数を求めましょう。
$x=1,3,5,...,2R-1$それぞれについて第一象限のみを考慮した場合の正方形の個数が$(ymax-1)/2+1$のとき、左右二倍するのですが$y$軸に重なる正方形一つだけダブルカウントになるため$-1$する必要があります。
したがって、$((ymax-1)/2+1)×2-1=(ymax-1)+2-1=ymax$と、整理された結果$ymax$で表せることが分かりました。

円の内部に含まれる全ての正方形の個数

最後に、下半分の正方形の個数についても考えましょう。
これも基本的には上下二倍で考えれば良いだけなのですが、$x$軸と重なる場合は二倍する必要がありません。
したがって、$y=1,3,5,...,2R-1$それぞれについて、$y=1$のとき$ymax$、$y>1$のとき$2ymax$です。
これを全て合計すれば円の内部に含まれる全ての正方形の個数が求められます。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const R = Number(input[0]);

  let ans = 0;
  // x軸、y軸それぞれ2倍に拡大して考えると、正方形の右上の点のx座標、y座標は奇数になる
  for (let i = 1; i < 2 * R; i += 2) {
    let y = lower_bound(i, R);
    // y座標が偶数の場合は奇数になるように調整する
    if (y % 2 == 0) y--;
    // y>1のときは2倍して下側の正方形も加算する。y=1のときはy軸と重なるため2倍しない
    ans += y * (i > 1 ? 2 : 1);
  }
  console.log(ans);
}

const isOK = (x, mid, R) => {
  // 正方形の右上の点が最も円の中心から遠いため、この点が円の内部にあれば正方形は円の内部に含まれる
  let d = x ** 2 + mid ** 2;
  // 2倍に拡大しているため、半径の2倍の2乗と比較する
  if (d <= (2 * R) ** 2) return true;
  return false;
};

const lower_bound = (x, R) => {
  let ok = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
  let ng = 2 * 10 ** 6; // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()

  while (ng - ok > 1) {
    let mid = Math.floor((ok + ng) / 2);
    if (isOK(x, mid, R)) ok = mid;
    else ng = mid;
  }
  return ok;
};

Main(require("fs").readFileSync(0, "utf8"));

E - Square Price

E問題は一見優先度付きキューで安いものから順に追加していけば良さそうですが、$N=1,M=10^{18},P=1$などとすると購入数が$10^9$くらいになるので簡単にTLEします。

そこで、$x$円までの商品を全て購入するような$x$の決め打ち二分探索を行います。
なお、最適解は商品を購入金額の合計が$M$を超えるギリギリまで安い順に買えるだけ買うという貪欲法で求めることができるため、$x$の上限における商品購入個数が答えとなります

※補足
$x$は$x$以下の商品を全て買う必要があるので、ある$t>0$について$x+t$円の商品が複数存在した場合、その一部を買い漏らす可能性があります。
実際には$t$が何であっても$x$を$x+t-1$に置き換えれば良いだけなので、「$x$円以下の商品を全て買って、$x+1$円の商品をいくつか買えるだけ買う」と考えたら良さそうですね。

JavaScriptで解く際の注意点として$M≦10^{18}$と$M$がかなり大きくBigIntを使う必要があるため、$O(NlogM)$解でも相当定数倍や枝刈りに気を使わないとTLEします。
以下、JavaScriptでのACコードでは高速なNumber型を利用するため$x$の上限を$10^{14}$としていますが、テストケースによっては落ちるかもしれません。

代わりにPythonで同じ実装をしたコードを置いておきます。

// javascript 1725ms
function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, M] = input[0].split(" ").map((x, i) => (i == 0 ? Number(x) : BigInt(x)));
  const P = input[1].split(" ").map(Number);
  let ans = 0;

  const isOK = (mid) => {
    // cur:= 現在の購入金額の合計
    let cur = 0n;
    // i番目の商品のk個目を買うと(2k-1)P[i]円かかると考え、mid円以下の商品を全て買うことを考える
    const cnt = Array(N).fill(0);
    for (let i = 0; i < N; i++) {
      cnt[i] = Math.floor(((mid / P[i]) + 1) / 2);
      cur += BigInt(cnt[i] ** 2) * BigInt(P[i]);
      if (cur > M) return false;
    }

    // res:= 購入した商品の個数の合計
    let res = cnt.reduce((acc, cur) => acc + cur, 0);

    // mid+1円の商品は全て買うことはできないが、いくつか買えるかもしれないので買えるだけ買う
    for (let i = 0; i < N; i++) {
      let nex = BigInt(2 * cnt[i] + 1) * BigInt(P[i]);
      if (nex == BigInt(mid + 1)) {
        if (cur + nex > M) break;
        cur += nex;
        res++;
      }
    }

    // 副作用でansを更新
    ans = Math.max(ans, res);
    return true;
  };
  const lower_bound = () => {
    let ok = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
    let ng = 10 ** 14; // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()

    while (ng - ok > 1) {
      let mid = Math.floor((ok + ng) / 2);
      if (isOK(mid)) ok = mid;
      else ng = mid;
    }
    return ok;
  };

  lower_bound();
  console.log(ans);
}
Main(require("fs").readFileSync(0, "utf8"));

# python 221ms
N, M = map(int, input().split())
P = list(map(int, input().split()))
ans = 0

def is_ok(mid):
    global ans
    cur = 0
    cnt = [0] * N
    for i in range(N):
        cnt[i] = (mid // P[i] + 1) // 2
        cur += cnt[i] ** 2 * P[i]
        if cur > M:
            return False

    res = sum(cnt)
    
    for i in range(N):
        nex = (2 * cnt[i] + 1) * P[i]
        if (nex == mid + 1):
            if (cur + nex > M):
                break
            else:
                res += 1
                cur += nex

    ans = max(ans, res)
    return True


def lower_bound():
    ok = -1
    ng = 10 ** 18 + 1

    while ng - ok > 1:
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok


lower_bound()
print(ans)

F問題は遅延セグ木上二分探索を知らないため説明を割愛します。
E問題はコンテスト後に友人から少しヒントをもらって自力で解くことができました。
最近は青diffを解いていることも多いのですが、ロジックが複雑な問題を実装し切ることが課題だと感じます。
いつか難問を解いて上振れを経験してみたいです。