日本レジストリサービス（JPRS）プログラミングコンテスト2024（AtCoder Beginner Contest 339）F,G問題メモ

日本レジストリサービス（JPRS）プログラミングコンテスト2024（AtCoder Beginner Contest 339）

8問体制になって以降のABCで初全完。

だけどGはライブラリを使えば一発の問題で、 肝心のライブラリを丸パク他人のものを参考にしたため、あまり自力で解いた感じはしない。。。

（ついでに、はじめて本番中に C++ を使った。気の迷いで環境構築していれば救われることもあるもんだ）

F - Product Equality

• $N$ 個の正整数 $A=(A_1,...,A_N)$
• このうち、$A_i \times A_j = A_k$ となる3数 $(i,j,k)$ の組の個数を求めよ
  • $i,j,k$ の順番も区別するし、$i=j$ など同じ数字があってもよい
• $1 \le N \le 1000$
• $1 \le A_i \le 10^{1000}$

$A_i$ がでかいため、普通に整数として計算できない。どうしましょう。

、、、と思いきや、普通にPythonの多倍長演算が通る。

さすがに $10^{1000} \times 10^{1000}$ のような数を計算していたらTLEとなったが、 あらかじめ $\log_{10}$（桁数）を求めておいて、 桁数の和が1000を超えるような2数は計算しない、という枝刈りを入れれば十分だった。

テストケースに $10^{450}～10^{500}$ くらいの数がいっぱいあるようなケースがなかったみたい。あったらTLEだったかも。

正攻法はmodを取る。

$A_i \times A_j = A_k$ ならば、modをとっても等しい（$a \times b \equiv c \mod{p}$）。
逆に、$a \times b \equiv c \mod{p}$ ならば $A_i \times A_j = A_k$ とは言えないが、複数のmodを試すことで、誤判定の確率を減らす。

※以下の議論で、実際には、誤判定する確率は独立ではないし、 意図的に特定のよく使われそうな $p$ で失敗するような入力を仕込むこともできるので、かなり雑な見積もりではある。

$a \times b \neq c$ である3数が、$a \times b \equiv c \mod{p}$ を成功してしまう確率を $M$ とする。
$ab \mod{p}$ が $0～p-1$ の値をランダムに取ると仮定して、$M=\dfrac{1}{p}$ とする。

$p$ を $K$ 個試すと $M^K$ の確率で誤判定する。
3数の組 $C={}_{1000}C_3 \simeq 1.66*10^8$ 個で全て誤判定が発生しない確率は $(1-M^K)^C$。

テストケース $T$ 個全てで発生しないのは $(1-M^K)^{CT}$。

$p=10^9,K=10,T=100$ で 0.999…9 の9が80個続くくらいになる。

Python3

G - Smaller Sum

• 長さ $N$ の整数列 $A=(A_1,...,A_N)$
• $Q$ 個のクエリに答えよ
  • $L_i,R_i,X_i$ が与えられる
  • $A_{Li},A_{Li+1}...,A_{Ri}$ のうち、$X_i$ 以下であるものの総和を求めよ
• クエリにはオンラインで答える必要がある
  • 擬似的にオンラインを再現する方法として、クエリは1つ前のクエリの答えが復号鍵となる暗号化された形式で与えられる
• $1 \le N \le 2 \times 10^5$
• $0 \le A_i \le 10^9$

ある矩形区間の総和を求めるデータ構造として、FenwickTree on WaveletMatrix というものが存在する。

• Wavelet Matrix | Nyaan’s Library
• data-structure-2d/fenwick-tree-on-wavelet-matrix.hpp | Nyaan’s Library

ので、これを使えば通る。

セグメント木のように区間を分割し、その区間毎に、クエリに高速に答えられるようにしておく。

i    1  2  3  4  5  6  7  8
A  [ 3  1  4  1  5  9  2  6 ]

   [ 3  1  4  1][5  9  2  6 ]
   
   [ 3  1][4  1][5  9][2  6 ]
           ~~~~  ~~~~          ←┬L=2,R=7 のクエリで求める区間
   [ 3][1][4][1][5][9][2][6 ]    │
       ~~~            ~~~      ←┘

各区間では、「①その区間の配列をソートしたもの」「②更にそれの累積和を取ったもの」を事前計算しておく。

     [ 3  1  4  1  5  9  2  6 ]

①[ 0  1  1  2  3  4  5  6  9 ]  (便宜的に0を追加)
②[ 0  1  2  4  7 11 16 22 31 ]

①から、$X$ を超えない最も大きい数のindex $k$ を取得すれば、②[k] がその区間の答えとなる。

$O(N \log^2{N})$ で事前計算を構築し、$O(Q \log^2{N})$ でクエリ全体に答えられる。