ABC177-E coprime のPython or PyPyで間に合う解法を4つ記します
AtCoder Problems では緑difficultyらしいのですが(!?)コンテスト中には解けずに苦汁を飲みました
問題概要
- 個の整数が与えられる
- 個の整数の異なるすべてのペアが互いに素 ( ) のとき、
pairwise coprime
と出力する - そうでなくてすべての整数の が のとき、
setwise coprime
と出力する - いずれでもないとき、
not coprime
と出力する
コンテスト中の思考
not coprime
は最初に全体の を取ればok。 ( 以上ならnot coprime
)- (追記) 以下紹介する4つの解法は最初に↑の判定を済ませている前提で書きます
- 本質は
pairwise
かsetwise
の判定 - の異なる要素に共通の素因数が見つかったら
setwise
確定。 - 全部素因数分解、を避ける方法で判定しなきゃいけない! (←思い込み)
- 前計算で までの素数を求めておいてうまくゴリゴリやろう...! (←沼の始まり)
解法1 高速素因数分解
writer の kyopro_friends さんの想定解です。
エラトステネスの篩の進化版みたいなやり方で、osa_k法 とも呼ばれているみたいです。2
MAXN = 10**6+10 sieve = [i for i in range(MAXN+1)] p = 2 while p*p <= MAXN: if sieve[p] == p: for q in range(2*p,MAXN+1,p): if sieve[q] == q: sieve[q] = p p += 1
- まず配列を用意し
- [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15, ...] のようにします 3
- 次にの倍数で書き換えられていないところをで書き換えます
- [0,1,2,3,2,5,2,7,2,9,2,11,2,13,2,15,...]
- 次にの倍数で書き換えられていないところをで書き換えます
- [0,1,2,3,2,5,2,7,2,3,2,11,2,13,2,3,...]`
- 次はですが すでにに書き換えられているのでスキップします
- 次にの倍数で書き換えられていないところをで書き換えます
- ...
のようにして配列を作っておくと、素因数分解がめっちゃ高速にできます!!
tmp = set() while a > 1: tmp.add(sieve[a]) a //= sieve[a]
素因数の列挙は a > 1
である限り sieve[a]
で割り続けるだけ!
(今回は列挙だけなので set
でやっていますが、もちろん dict
や Counter
を使うことで素因数の個数も数えられます)
例えば a=60
として、
sieve[60] == 2
なので を抽出し、a
を で割る。sieve[30] == 2
なので を抽出し、a
を で割る。sieve[15] == 3
なので を抽出し、a
を で割る。sieve[5] == 5
なので を抽出し、a
を で割る。a==1
になったのでおわり。tmp = {2, 3, 5}
が抽出された。
計算量は のようです
配列の前計算が 、素因数分解が です
素因数分解めっちゃ速いですね!!
解法2 等間隔に舐めて調和級数で間に合うやつ
これは解説放送ですぬけさんが説明されていた方法です
詳しくは放送をご覧いただきたいのですが、なんと 素因数分解も素数判定も必要ありません
MAXA = 10**6 B = [0] * (MAXA+1) for a in A: if a==1: continue if B[a]: print('setwise coprime') exit() B[a] = 1
まずヒストグラムみたいのを作ります (上記の B
です)
同じ数値が2度出現したら setwise
確定で exit()
しています。
ただし が複数個あっても なので setwise
とは確定しないことに注意! (コーナーケース!)
結果として B
の要素としては 0
か 1
のいずれかが入る形になります。
for n in range(2,MAXA+1): c = 0 for m in range(n,MAXA+1,n): c += B[m] if c > 1: print('setwise coprime') exit()
さてここが肝です。上のコードでは
2,3,4,5, ... 1000000
までのそれぞれをn
として、n
から始めて2n
,3n
, ... (これをm
とする) のB[m]
をチェックしています- 各
n
のどれかで、B[m]
が 2回以上カウントされたらsetwise
確定です。
一見 までのループを2重に回しているので間に合わなそうに見えるのですが、実は間に合います
よく見ると1回の外側のループでは MAXA // n
回ぐらいしか処理されません。
は調和級数という考え方で になりますよというのが知られています (詳しくは解説放送をご覧ください)
ACコードの全体はこちら(PyPy) 327ms と、こちら(Python) 1320ms※ 4
解法3 愚直に素因数分解しちゃう
えー!間に合っちゃうんですか!
愚直に素因数分解を適用しても時間間に合いますよ。
— ライナス (@Linus_MK) August 30, 2020
慌てて書いたので変数名が酷いのは見逃してください……https://t.co/ISUmpWtBPC
ライナスさんにTwitterでリプライ頂きました
なんと愚直に試し割りして素因数分解しても間に合っちゃうみたいです!
計算量を雑に見積もると で オーダーなんですが、ちゃんと考えると1桁以上落ちるようです
というのも、
- 以下の素数は 個で、 に比べて1桁以上少ない
- 鳩ノ巣原理という考え方を適用すると、(追記)以上の が 個以上存在すると自動的にどれかしらの素因数が重複する! →
setwise
確定 !! - 最悪ケースを一応考えると
- のような素数がならぶ → までの試し割りでok
- の 乗、 の 乗、 の 乗、、、みたいに ( は を超えないような最大の指数) が並ぶことも一応あるけどこれは早く検出できるうえに指数はせいぜい以下
となり、 (追記)程度で に収まるオーダーです
これでPyPyで間に合いました
私も書いてみました(Pythonは間に合いませんでした)
ACコードの全体はこちら PyPy: 678ms
解法4 ゴリゴリスペシャル
きれいな解法ではないのでおまけです
コンテスト中に 2WA までこぎつけたのですがコーナーケースでやられていました
コンテスト後にねちょさんにコーナーケースを見つけていただきました!
1だけのケースでpairwise coprimeにならないのはわかりました
— ねちょ (@netyo715) August 29, 2020
先にコンテスト後のACコードを貼ります (下記2つは同一コードです)
PyPy 425ms、Python 1986ms (!!)
やったこと
- 全体の を取って 以上なら
not coprime
- 重複チェック。 以外で つ以上重複している要素があれば
setwise coprime
- 以外で の部分は本番中で見つけられなかったコーナーケースです...
- エラトステネスの篩で ぐらいまでの素数を検出する。実際に使ったのはそのうちの 以下の素数
- 各 について、
- いずれのチェックにもかからなければ
pairwise coprime
という方法を取りました
ちょっとでも試し割りの回数を減らそうと素数を列挙したのですが、結局解法3で述べた鳩ノ巣原理 による影響の方が大きくて結局計算量的には間に合っています (本番中は鳩ノ巣原理も見破っていなかったです)
おわりです!!
1問でたくさん学びがある良い問題でした!!!!