[AtCoder 参加感想] 2020/08/09:AGC047

	A	B	C	D	E	F
問題文	■	■	■	■	■	■
自分の提出	■		■		■
結果	AC		AC		AC

◆公式の解説 → https://atcoder.jp/contests/agc047/editorial?lang=en

言語設定を English にすると存在します。

◆コンテスト後提出
・B（ローリングハッシュ）：https://atcoder.jp/contests/agc047/submissions/15800655
・B（Trie）：https://atcoder.jp/contests/agc047/submissions/15801318
・D：https://atcoder.jp/contests/agc047/submissions/15794970

全体感想
問題A – Integer Product
問題B – First Second
問題C – Product Modulo
D – Twin Binary Trees
E – Product Simulation

全体感想

90分、ACE の 3 完で、44位でした。

A：9分。

A を解いたあと、一通り読む。Cがすぐ分かったので解く。：25分

B はやるべきことはすぐに分かって、Trie などで出来そうだと思うが、今まで一度しか実装したことがなくて、ここでまごつくと面白そうな D, E が考えられずに終わってしまう気がして、飛ばします。短時間で確実に解けないのは実力不足なところですが…。

DとEを並行して考えていると、Eが解けそうに思ったので解きます。細かいバグらせや方針の変更はたびたびやらかして、時間はかかりましたが、一段階一段階ずつテストしながら進めてACできました。：90分。行数の出力を忘れて1ペナ。

残り 50 分。B, Dの両立は厳しそうなため、Dを選択します。解ける確率自体は B の方が高いと思ったのですが、2900点の中での速度勝負では上位であったことから、ぎりぎりで 700 点増えてもうまみが少ないという考えもありました。

Dは、解法の大筋・計算量が見えたところで残り15分ほど。細かい計算式や実装方針が整えようとしているうちにあっという間に時間がなくなりました。

問題Eの過剰な配点に救われて、3000+パフォです。

なんというか結局、練習量の活きそうな B と D を落として、競プロ始めた頃でも解けそうな問題ばかりで稼いだので、達成感はちょっと少なめです。

「前から解く」を厳守しなかったり、不相応に思える高配点に挑戦して、結果損をしたこともありますが、その姿勢がプラスに働いたように思います。

手前3問、特にBとCはただの典型という感じで、悪い問題だとは思わないですが、非典型・創造的な思考力を問うことを目指しているAGCの思想とは合っていないように思いました。

問題A – Integer Product

整数論の問題です。整数論の問題って、整数を使って書き表した方がたいてい良いです。今回であれば、整数 $B_i = 10^9A_i$ を用いて小数 $A_i$ を、$\frac{B_i}{10^9}$ のように整数の 2 つ組として捉えます。

すると、「$10^{18} \mid B_iB_j$ となる $(i,j)$ を数えよ」という問題になります。これは $B_i$ を $2, 5$ で割りきれる回数だけで判定できます。$B_i$ が $2, 5$ で割り切れる回数を $X_i, Y_i$ とすれば、

組 $(X_i, Y_i)$ が $N$ 個与えられる。
$X_i + X_j \geq 18$ かつ $Y_i + Y_j \geq 18$ となる $(i,j)$ を数えよ
$N\leq 200000, X_i\leq \log_{2}10^{13}, Y_i\leq \log_5{10^13}$

という問題と言い換えられます。ひとつの $(X_i, Y_i)$ に対して解を高速に求めることを考えると，各 $(a,b)$ に対して $(a,b) = (X_j,Y_j)$ となる $j$ の度数分布を事前計算しておくと良いことが分かります。組 $(a,b)$ の個数は十分すくない（$20\cdot 44$ 以下、$18$ 以上のものを固めると $19^2$ 通りで済む）ので、あとはある程度下手に計算しても答が求められると思います。

[入力の受け取り] 今回は、浮動小数点数で受け取って、

x = float(input())
x = int(round(x * 10**9))

のようにすれば OK です。

ただし、切り捨て（x * 10^9 をそのまま long にキャストする等）だとダメです。整数に誤差を加えて切り捨てると、誤差が微小（123 と 122.999999 とか）でも値が変わってしまいます。

有効数字を増やしても同じことです。四捨五入とか、0.5 を足して切り捨てるなどで解決です。
— maspy (@maspy_stars) August 9, 2020

問題B – First Second

やることは単純です。

集合 $A$ ： $\{S_1, \ldots, S_N\}$
多重集合 $B$ ：各 $S_i$ に対して、「prefix $k$ 文字からひとつ選んだもの」 + 「suffix $|S_i|-k$ 文字」と書ける文字列全体の集合を $B_i$ としたとき、$B = \amalg B_i$。
$A\cap B$ の要素数を求めよ。（次の方法がある）
- 各 $S\in A$ に対して $B$ での出現回数を数えて、$S$ について和をとる
- 各 $S\in B$ であって、$A$ に含まれているものの個数を数える

最後に $i=j$ に相当する場合を除くなどの細かい処理はあります。prefix からとってくる文字数が $\sigma = 26$ 種までありえて、最終的に $26\cdot 10^6$ 種程度の文字列を管理（一致するものの検索ができるようにする）できればよいです。

文字列を、空間計算量や時間計算量がその長さに比例する方法で管理すると上手くいきません。今回は、ひとつの文字列の suffix、あるいはその変形として多くの文字列が作られるので、ローリングハッシュ、あるいはTrieの1ノードとして表すことで解決します。

[Rolling Hash 解法]
$10^9$ 程度の単一の mod でローリングハッシュをとると、$26\cdot 10^6$ 件程度の文字列を区別しきるのは困難です。例えば $\pmod{p}$ での一様乱数でハッシュ化した場合、$O(\sqrt{p})$ 件の相異なるデータに対して無視できない衝突確率が生じます（誕生日攻撃）。

複数のハッシュの組を使うか、より巨大な素数を mod とすると良いです。私は keymoonさんの記事を参考に実装しました。

私の関連記事：Rolling Hashについて

[Trie 解法]
公式解説の C++ コードが簡潔で読みやすかったです。実装経験が少なくちょっと苦手意識がありましたが、久しぶりに挑戦したら簡単でびっくりしました。

問題C – Product Modulo

剰余の和ってあまり性質が良くないので、基本的には全ての $A_iA_j\pmod{P}$ を全部作って足すことが求められていそうです（式変形でまとめてから mod をとるようなことはできなさそう）。

とはいえ $\Theta(N^2)$ 件の計算は厳しいので、$A_iA_j\pmod{P}$ の度数分布を得ることを考えます。これは、群 $(\mathbb{Z}/p\mathbb{Z})^{\times}$ における畳み込みの問題です（集合 $\{1,2,\ldots,p-1\}$ に、積 $\pmod{p}$ で群構造を入れたものと思えばよい）。

群同型 $(\Z/p\Z)^{\times} \cong \Z/(p-1)\Z$ がありますから，$\Z/(p-1)\Z$ での畳み込みが出来ればよくて、これは FFT により解決します。

初等整数論とFFTを少し知っていれば非自明な考察ポイントはほとんどない問題がこの位置に出題されたのはびっくりしました。

基本的なロジックで、割と色んなところで再生産されていそうです。私の知っている範囲ですと、

yukicoder での出題例：[yukicoder] Multiplicative Convolution

kirika_comp さんの整数論テクニック集でも取り上げられています。

[Python + FFT]

記事を書きました。

[数学・numpy] 高速フーリエ変換(FFT)による畳み込み

D – Twin Binary Trees

えー、あまりスムーズに解けなかったので、公式解説の方がすっきり行くと思います。

問題D。コンテスト中に考えた方針を整理する。
整理するのに1時間かかっちゃいます。

5時間あれば高確率で解けそうだけど、1時間で倒すのはとても難しいです。考察が下手かなあ。 pic.twitter.com/vnuLLgomHY
— maspy (@maspy_stars) August 9, 2020

頂点 $v$ に対して、$v = lca(a,b)$ となる $(a,b)$ を調べるのが難しそうだと思った一方、$lca(a,b)\geq v$ となる $(a,b)$ を調べるのは分かりやすそうだと思ったため、包除原理を想定します。

包除原理で意味づけみたいなことを考えてパニックにならないように、「計算したいもの」「計算できそうなもの」をなるべく明示的に数式にしました。関係式を書いて、包除して、と。

本番中もこういう方針で考えていたのですが、ペア $(x_1,x_2)$ がたくさんあるので一度棄却していました。実は $O(H^22^H)$ ペアしかないことに気づいたのが、残り 15 分くらいで。あまり見たことのない計算量解析ですね。

$x_1 \in T_1$ に対して、葉 $v$ が $2^{H – \text{depth}}$ 個ある。
各葉 $v$ から見て、$x_2\in T_2$ が $H$ 個ある。
$\sum_{x_1\in T_1} 2^{H – \text{depth}}$ は、深さごとに計算すると $H\cdot 2^H$ である。

反省点。結果的に、「$lca(a,b) = v$ となる場合」は、「$lca(a,b) \geq v$ となる場合」から、$v$ の子 $c_1,c_2$ に対して「$lca(a,b) \geq c_1$ となる場合」「$lca(a,b) \geq c_2$ となる場合」を引けばよいだけでした。こんなのは数式を書くよりパッと意味づけを考えた方が速かった…。

あと、最終的には $x_1$ を固定して $x_2$ を探索することに。どうせそうなるのだったら、いきなり $2$ 変数関数と向き合うよりも、$x_1$ を固定して場合の $1$ 変数関数と向き合った方が状況が単純化されたようです。計算量解析を発見するのが遅かったので、仕方がなかったかもしれませんが、ずいぶん遠回りをしてしまいました。

E – Product Simulation

1800点で / AGC-E で、最弱だと感じました。解けたからそう感じている部分もあると思いますが、どうでしょう…。初中級者でもかなりチャンスのある問題だったのではないでしょうか？

$A$ との大小比較での分岐が必要でしょうから、大きい数を作って不等式評価をすることを考えます。特に、$2$ べきを使うのも典型です。$A$ と $2$ べきの比較を繰り返して、$A$ に依存するロジックを作りたいので、$A$ の $2$ 進法展開ができればよさそうです。あとは純に考えていきます。

$2^n$ を作れるか？
- $2^{n-1}$ が作れれば、$2^n$ が $1$ 手で作れる
- $1$ が作れるかが問題
- $a[0]=a[1]=0$ だと永遠に作れないが、この場合はどうせ答は合う
- $a[1]>a[0]$ 作れそう。失敗しても、答が $0$ になってくれればよいし何とかなりそう（$a[1]+a[2] > a[0]$ などで確実に作れますが、本番中は答が合わなかったら考えるつもりで、ひとまず $a[1] > a[0]$ を実装しました）。
$A$ を $2$ 進法展開 $A = \sum_{i=0}^{30}a_i2^i$ を計算できるか？
- 上の桁から決めて二分探索したい。
- $2^n$ より上の桁まで決められたとして、$2^n$ の桁を決めたい
- $x = \sum_{i > n}a_i\cdot 2^i$ を作って、$x + 2^n \leqq A$ をテストすれば $a_n$ が出そう。
  - $x= \sum_{i > n}a_i\cdot 2^i$ は作れるか？ → $a_i\cdot 2^i$ が作れればよい
  - $x = a_i\cdot 2^i$ は作れるか？ → yes. $x = a_i > 0$ として、$x ← x+x$ を $i$ 回繰り返せばよい。
  - $x+2^n \leqq A$ は調べられるか？ → yes. はじめ「$2^n-1$ を作っておけばよい」として実装を進めたのですが、途中で、「$x+2^n < A+1$」と言い換えるのが簡潔だと気付きました。
  - $A, B$ を $2$ 進法展開できることが分かった。
$A, B$ の$2$ 進法展開がある。積 $AB$ を計算できるか？
- $(a_0,\ldots,a_n)$ および $(b_0,\ldots,b_n)$ に対して $(\sum a_i2^i)\cdot (\sum b_j2^j)$ を計算できるか？
- → $\sum_{i,j}a_ib_j2^{i+j}$ を計算できるか？
- $a,b\in \{0,1\}$ および $n$ に対して $ab2^n$ を計算できるか？
- これはできる。積 $ab$ は $1 < a+b$ で作れるので、$n$ 回ダブリングすればよい。
解けた