AtCoder Beginner Contest 152に参加したので、着手した問題の考察を書いていきます。結果は遅めの E 完でした。
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
参考: 「互いに素」という概念