競プロ参戦記 #70 Flatten | ABC 152

AtCoder Beginner Contest 152に参加したので、着手した問題の考察を書いていきます。結果は遅めの E 完でした。

- 前回: [競プロ参戦記 #69 Swap and Flip | キーエンス 2020](https://qiita.com/vain0x/items/16fda27325275d0ece92)
- 問題一覧: https://atcoder.jp/contests/abc152/tasks

## A - AC or WA

問題概要: 非負整数 N, M が与えられる。N 個のテストケースがあり、すべてのテストケースに正解した提出は AC となる。ある提出は、そのうち M 個のテストケースに正解した。この提出が AC であるか判定せよ。

### A: 考察

A問題にしばしばある、問題文を読解する問題です。(問題概要をどう書くか悩む。)

AC になる条件「すべてのテストケースに正解」を「N 個のテストケースに正解」と言い換えると、「M 個のテストケースに正解した」提出が AC かどうかは M == N と同値であることが分かります。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc152/submissions/9617938

## B - Comparing Strings

問題概要: 1桁の整数 a, b が与えられる。a を b 個並べた文字列と、b を a 個並べた文字列のうち、辞書順で小さい方を出力せよ。

### B: 考察

文字列の辞書順 (辞書式順序) は、2つの文字列の前から1文字ずつ比較し、最初に異なる文字の大小を文字列の大小とみなす順序です。

前方に小さい文字を含む文字列ほど辞書順では小さいので、a < b なら「a を b 個並べた文字列」の方が「b を a 個並べた文字列」より辞書順で小さくなります。

a > b のケースも同様で、a = b のケースは自明です。

もう少し考えると、「min(a, b) を max(a, b) 個並べた文字列」を出力すればよいことが分かり、場合分けが減ります。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc152/submissions/9606372

## C - Low Elements

問題概要: 正の整数 N と、1 以上 N 以下の整数の順列 P が与えられる。以下の条件を満たす 1 以上 N 以下の整数 i の個数を数えよ。

条件: 1 以上 i 以下のすべての整数 j について、P(i)≤P(j) が成り立つ

制約: N≤2×10^5

### C: 考察

例えば N=4 なら、各 i が満たすべき条件は以下のようになります。(j = i の場合は常に成立するので省略。)

- i=1 無条件成立
- i=2 P(2)≤P(1)
- i=3 P(3)≤P(1) かつ P(3)≤P(2)
- i=4 P(4)≤P(1) かつ P(3)≤P(2) かつ P(4)≤P(3)

ようするに P(1), P(2), ..., P(i-1) がすべて P(i) 以上なら条件を満たします。

i についてループを回し、内側で j についてループを回す2重ループを書けば解けそうに見えますが、これは不正解です。全体で100億回以上の計算が必要になり、実行時間制限(2秒)を超過するからです。

「すべてが X 以上」は「最大値が X 以上」と言い換えられます。そのため、i について 1 からループを回す際に「最大値」を変数としてもっておくと、各 i が条件を満たすか高速で判定できます。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc152/submissions/9604044

## D - Handstand 2

問題概要: 正の整数 N が与えられる。N 以下の正の整数 A, B の順序対で、以下の条件を満たすものを数えよ。

条件: A の末尾の桁が B の先頭の桁に等しく、A の先頭の桁が B の末尾の桁に等しい。(10進数で表記する。0 は先頭の桁にしない。)

### D: 考察

例えば A = 31415 なら先頭・末尾の桁はそれぞれ 3, 5 なので、B が 5...3 という形の整数 (例えば 53, 513, 523, など) なら (A, B) は条件を満たします。

(A, B) が条件を満たすとき、A ≠ B なら (B, A) も数えなければいけません。A < B のケースを数えて2倍し、A = B は別途数えるのがよさそうです。

整数に関して問題になるのは (先頭の桁, 末尾の桁) だけなので、これが等しいもの同士は区別せずにまとめて考えてよいです。

- 35, 305, 31415, ... → (3, 5)

結局、以下の手続きにより数え上げられます。1 以上 N 以下の整数 B (先頭・末尾は x, y) を小さい順に列挙し、整数を (先頭の桁, 末尾の桁) ごとに表 map でカウントしていきます。map には B 未満の整数だけがカウントされているので、(A, B) のペア (ただし A < B) は map(y, x) 通りです。

(B, A) もあるので、計上するのは `map(y, x) * 2` です。x == y のときは (B, B) もありうるのでさらに +1。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc152/submissions/9617788

## E - Flatten

問題概要: N 個の正の整数 A(1), ..., A(N) が与えられる。以下の条件を満たす正の整数 B(1), ..., B(N) のうち、総和 B(1) + ... + B(N) の最小値を求めよ。(1000000007 で割った余りを出力)

条件: すべての i < j について、A(i)・B(i) = A(j)・B(j) が成り立つ。

制約: N≤10^4, A(i)≤10^6

### E: 考察

条件は言い換えると A(1)・B(1) = A(2)・B(2) = ... = A(N)・B(N) です。この値を X とおくことにします。

A(i)・B(i) = X から、X はすべての A(i) の公倍数です。そのような X で B の総和を最小にするには、最小公倍数を選ぶのがベストです。

問題は X の値が巨大であり、64ビット整数では表現できないことです。(任意精度整数を使えば計算できるという噂もある。)

掛け算と割り算しかしないので、対数 (のようなもの) を使うことで数字を小さくできます。

素因数分解の一意性から X = 2^p(1)・3^p(2)・5^p(3)... となるベクトル p が一つだけ存在します。これを X の素数指数表現と呼んで L(X) と書くことにします。

素数指数表現は対数のようなもので、整数の掛け算はベクトルの足し算になり、割り算は引き算になり、**最小公倍数は成分ごとの max** になります。

```
    L(X * Y) = L(X) + L(Y)

    L(X / Y) = L(X) - L(Y) (ただし X は Y の倍数)

    L(LCM(X, Y)) = max(L(X), L(Y))) (ただしベクトルの max は成分ごとの max)
```

そういうわけで L(B(i)) = L(X/A(i)) = max(L(A(1)), ... L(A(N))) - L(A(i)) を計算して、整数に戻せば OK です。

整数 n の素因数分解は、n を 2 以上 √n 以下の各整数 i で小さい順に割っていくことにより、全体として O(√n) 時間でできます。

i で m 回 (m≥1) 割れたとき、もとの n は「素因数 i を m 個含む」といえて、最終的に n≥2 なら「素因数 n を1個含む」といえます。

小さい順に割っていくのが重要で、このおかげで i が素数かどうか調べる処理が不要になります。i が素数のとき n から素因数 i がすべて消えるので、i が合成数のときは n を1度も割れないからです。ループ終了後の n も √n 以下の素因数を持たないことから素数といえます。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc152/submissions/9621481

参考: [「互いに素」という概念](http://www.hyuki.com/dig/relprime.html)