【JavaScript】ABC400まとめ（A~C）

AtCoder Beginner Contest 400

前回参加分の寄稿となります。
ABCの3完（21分0ペナ）でした。
957perfでレートは1054->1045（-9）となりました。
ABCを高速に解けたので、D問題より先に配点上有利なE問題を解こうとした結果、ドツボにハマってしまい挽回不可能な状況となってしまいました。
今回はA,B,Cをまとめます。

A - ABC400 Party

$400$人を$A$行$B$列で長方形状に並べたいとのことですので、まずは$A$行が入力として与えられた時に$A×B=400$となる正整数$B$が存在するかを調べる必要があります。

すなわち、$400$が$A$で割り切れない場合はその時点で長方形状にすることが不可能なので-1を出力し、割り切れる場合は$400/A$の結果を出力します。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const A = Number(input[0]);
  if (400 % A !== 0) return console.log(-1);
  console.log(400 / A);
}

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

B - Sum of Geometric Series

$N=10^8$のようなときに、$X=N^0+N^1+N^2$でJavaScriptのNumber型の上限値を超える心配があるため、BigInt型で計算しましょう。
$X=0$で初期化して、$i=0$から累積的に$N^i$を加算していき、$10^9を$超えたらinfを出力し、超えなければ$\sum N^i$をそのまま出力します。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, M] = input[0].split(" ").map(BigInt);
  let ans = 0n;
  for (let i = 0; i <= M; i++) {
    ans += N ** BigInt(i);
    if (ans > 10n ** 9n) return console.log("inf");
  }
  console.log(ans.toString());
}

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

C - 2^a b^2

まず、変数が$a,b$の二種類あるため、どちらかを全探索して、もう片方は二分探索により整数範囲の上限を調べることで変数の組み合わせを求めるという定石的な解法を検討します。

まず、$a$について全探索する場合、$2^{60}>10^{18}$であるため、全探索の回数は高々$60$回で済みます。一方で、$b$について全探索する場合、${10^9}^2=10^{18}$であるため、全探索の回数が最大$10^9$回となってしまいTLEがほぼ確定してしまいます。したがって、最初の第一歩としては$a$の全探索で$2^a$を個別に確定し、その上で$2^a×b^2≦N$を満たすような$b$の上限はどこまでかを二分探索によって調べます。

ここで、仮に$b$の上限が$b_{max}$のような値だったとして、「$2^a b^2 ≦N$となるような$b$の範囲が$1≦b≦b_{max}$だから$b_{max}$通りを加算」のようにしてしまうと整数が重複してしまうためうまくいきません。例えば、$2^1 6^2$は$72$ですが、$2^3 3^2$も$72$なのでダブルカウントが発生してしまいます。

このダブルカウントを回避するためのコツは、$1≦b≦b_{max}$の範囲のうち、奇数のものだけをカウントするということです。$b_{max}=5$であれば、$b=1,3,5$の3通りだけをカウントします。$1≦b≦b_{max}$を満たす偶数の個数は$\lfloor \frac{b_{max}}{2} \rfloor$個なので、奇数の個数としては$b_{max}-\lfloor \frac{b_{max}}{2} \rfloor$と書けます。なお、直接$\lceil \frac{b_{max}}{2} \rceil$と書いても結果は同じです。JavaScriptのBigInt型の制約として天井関数が計算しにくいためあえて偶数の個数を全体から差し引くという方法をとっているだけです。

この方法で正しくカウントされる理由は、仮に$b$が偶数であり、$2^x$の成分を含むとしても、結局$2^a b^2$と$2^{a+2x} (b/2^x)^2$の結果が重複してしまうためです。
要するに、偶数の数え上げは$2^a$側に任せて、$b$は奇数の探索に専念して全く問題ありません。

以上で、この問題を$O(logN^2)$で十分高速に解くことができました。

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

  const isOK = (mid, key) => key * (mid ** 2n) <= N;
  const lower_bound = (key) => {
    let ok = -1n; //「index = 0」が条件を満たすこともあるので、初期値は -1
    let ng = 10n ** 18n + 9n; // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()
  
    while (ng - ok > 1n) {
      let mid = (ok + ng) / 2n;
      if (isOK(mid, key)) ok = mid;
      else ng = mid;
    }
    return ok;
  };
  
  let ans = 0n;
  for (let a = 1n; a < 60n; a++) {
    let l = 2n ** a;
    if (l > N) break;
    let rmax = lower_bound(l);
    ans += rmax - (rmax / 2n)
  }
  console.log(ans.toString());
}

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

まとめ

1ヶ月ほど精進の手が止まっているとはいえ、まあまあ耐えているのではないでしょうか。
ただE問題が解けなかったのは、精進不足の証です。
記事投稿が一週間遅れているので、まずはその遅れを取り戻すところからぼちぼちとやっていきます！