デンソークリエイトプログラミングコンテスト2024（AtCoder Beginner Contest 361）F,G問題メモ

デンソークリエイトプログラミングコンテスト2024（AtCoder Beginner Contest 361）

$361=19 \times 19$ なだけあって、囲碁に関する問題が数問あった。

F - x = a^b

• $1$ 以上 $N$ 以下の正整数 $x$ であって、ある正整数 $a$ と $2$ 以上の 正整数 $b$ を用いて $x=a^b$ と表現できるものはいくつありますか？

• $1 \le N \le 10^{18}$

メビウス関数を知っていれば楽に解ける問題。

$b$ を決めれば、$a=1～ \lfloor \sqrt[b]{N} \rfloor$ が全て条件を満たすので、 基本的な方針としては、様々な $b$ に対して $\lfloor \sqrt[b]{N} \rfloor$ を足し合わせたものが答えとなる。
（以降、単に $\sqrt[b]{N}$ で、$\lfloor \sqrt[b]{N} \rfloor$ を指すとする）

$b$ として取り得る値は、$2^{60} \gt 10^{18}$ より、$2～59$ を考えればよい。

また $b$ が素数で無い場合、$b=kb'$ と2数の積に分解できるとして、 $a^b=(a^k)^{b'}$ と、より小さい指数による表現ができてしまうので $b$ は素数のみ考えればよい。

しかし、$4^3 = 8^2 = 64$ など、異なる $(a,b)$ が同じ $x$ になってしまうことがある。

これは、$(2^2)^3=(2^3)^2$ のように、$a$ 自体が $c^d$ と表せる場合に発生しうる。

$b=2$ でも $b=3$ でも表せてしまう数は、$b=6$ でも表せるので、 $\sqrt[2]{N}$ + $\sqrt[3]{N}$ - $\sqrt[6]{N}$ とすれば重複を除けることになる。

このような事をするのに便利なのが、メビウス関数（を、約数系包除原理用にカスタマイズしたもの）である。

• ABC230 G 解説

これで、$\displaystyle \sum_{b=2}^{59} \tilde{\mu}(b) \times \sqrt[b]{N}$ が答えとなる。

（なんか、1だけずれるので、微調整したら通る）

Python3

ご丁寧に、サンプルに $N$ が最大の $10^{18}$ のときがあって、答えは $10^{9}+10^{6}+\alpha$ 程度である。

このうち $a^2$ と表せる数が $10^9$ 個あるので、残りは $10^6+\alpha$ 個程度である。

つまり、$3$ 以上の素数の $b$ と、$\sqrt[b]{N}$ 以下の $a$ について、 素直に $a^b$ を計算して set（重複しない集合を表現するデータ構造）に放り込んでいっても、 対象は $10^6$ 個程度であり、TLEやMLEにはならないことがわかる。

重複除外はsetの機能に任せてよくなり、（最終的なsetのサイズ + $\sqrt[2]{N}$）が答えとなる。

ただし、$a=c^2$ と表現されるような $a$ は、$\sqrt[2]{N}$ の方で数えられているので、$a$ が平方数の場合は除外する。

G - Go Territory

• $2$ 次元平面上に $N$ 個の石が置かれています。$i$ 番目の石は座標 $(X_i,Y_i)$ にあります。石は全て第一象限(軸上含む)の格子点にあります。
• 石の置かれていない格子点 $(x,y)$ であって、石に囲われているものの個数を求めてください。
  • つまり、上下左右のいずれかに $1$ 移動することを繰り返すことで、石の置かれている座標を通らずに $(-1,-1)$ に到達することができない $(x,y)$ の個数を求めてください。

• $0 \leq N \leq 2\times 10^5$
• $0 \leq X_i,Y_i \leq 2\times 10^5$
• $(X_i,Y_i)$ は相異なる

ひたすら泥臭く頑張ればできるのはできるんだけど、なかなか上手く実装するのが難しい問題。

公式Editorialを自分用にメモしただけ。なるほど！この発想は気がつかなかった。

• 解説 - デンソークリエイトプログラミングコンテスト2024（AtCoder Beginner Contest 361）

「石の置かれていない格子点」を空格子点とする。

この問題は、愚直には、範囲内の隣り合う空格子点同士をUnion-Findで結ぶなどすることで、 外 $(-1,-1)$ と同じグループにならない空格子点の個数を数えればよい。
ただ、$O(X_{max}Y_{max})$ の頂点ができるので、TLEとなる。

考慮する空格子点を石の周囲最大8つに限定すると、石により分断されているかの判定ができる情報量を保ったまま、頂点数を $O(N)$ とできる。
しかし、どっちが内か外かの判定や、入れ子構造になった場合を見つけて除外するのに、地道な実装が必要となる。（公式Editorial 1つめの解法）

Union-Find上の頂点数を減らすもう1つの方法として、 互いに行き来できることが明らかな空格子点のカタマリは、まとめてやることが考えられる。

具体的には、横に連続する空格子点のカタマリは、1つの頂点としてまとめる。

|-----------------------------
|--|■■■■■||■■|---------
||■|--------|■|--|■|-------
||■|----------------|■|-----
||■|--|■■|------|■|-------
|--|■■|--|■■■■|---------
|-----------------------------

こうすると、頂点数は $O(X_{max}+N)$ に抑えられ、愚直とほぼ同じ解法が使える。
入れ子構造とかも考えなくて済み、楽に実装できる。

外周に1個分、確実に空格子点である列を作る必要がある点に注意。

Python3