ケーキ同好会でも、プログラミングは必須スキルです！

ケーキ同好会9

「ゆいちゃん、フレンドになろーー！！」

感心していると、ひまり先輩が突然部室に入ってきて抱き着いてきた！

「PBC何問解けたの？」

「四問解けました」

「初めてで四問はすごいじゃん！」

あの、ひまり先輩、もうちょっと力を緩めてもらえると助かります......ほら、哀先輩も苦笑いしてるし。

「そういえば、先輩方のランクってどれくらいなんですか？」

ひまり先輩が情報オリンピックの日本代表ってことは知ってるけど、哀先輩はどうなんだろう。

「私は青(A)」

競プロのランクの説明もちゃんとしとかないとね。と哀先輩が部室の前のホワイトボードの方に移動し、ペンを右手に取る。

競技プログラミングは、実力に応じてランクがつけられる。

登録したばかりの人はF級から始まって、コンテストで良い成績を取るとどんどん上がっていく。

ランクは慣例的に色で表す。

\[\text{\ltjruby{黒}{F} < \ltjruby{灰}{E} < \ltjruby{茶}{D} < \ltjruby{緑}{C} < \ltjruby{水}{B}

< \ltjruby{青}{A} < \ltjruby{黄}{S} < \ltjruby{橙}{SS} < \ltjruby{赤}{SSS}}\]

の順だね。右にいくほど強くて、赤色が一番強い。

\ltjruby{緑色}{C級}以上ならプログラマとしては十分な実力で、このランクが実力を測る一つの目安となる。

S級以上は日本で400人くらいしかいない。その色から暖色コーダーといって特別視されてる。

哀先輩がホワイトボードに文字を書きながら説明してくれる。

哀先輩は青色ってことは、A級なんだ。......哀先輩もふつうに強くない？

ひまり先輩ばっかり褒めてたけど、哀先輩も競技プログラミング強いんだね。

「ひまちゃんと同じ色の高校生は、ひまちゃんとあと一人しかいない」

「何色なんですか？」

「赤色」

「え！？すごい！」

「高校生に限らなくても、日本で100人もいない」

あまりのすごさに、私は目を丸くしてしまった。

「ゆいちゃんも、今から頑張れば私と同じ色までなれるかもよ？」

「善処します......」

さすがに、高校生で二人だとなれる気が全然しません。

そういえば、ひまり先輩と同じレベルのもう一人の高校生ってどんな人なんだろう。

ひまり先輩は出会ったことがあるのかな。

「じゃあ、今日は計算量の話をしようかな」

「PBCの5問目からは、計算量を意識しないと解けない問題が出るんだよね」

「計算量を意識する？」

「ざっくり言うなら、名前の通りプログラムが計算する回数のことを計算量っていうよ」

「実際に体験した方が早い」

「前回のPBCのE問題を見てみよー！」

E - Largest Prime Factor

実行制限時間:$2$sec/メモリ制限:$1024$MB

配点:$250$点

問題文

$2$以上の整数$N$が与えられます。$N$の素因数のうち、最も大きいものを出力してください。

制約

入力はすべて整数

$2 \leq N \leq 10^{12}$

入力形式

$N$

入力例1

$\texttt{35}$

出力例1

$\texttt{7}$

入力例2

$\texttt{97}$

出力例2

$\texttt{97}$

えっと、とりあえず問題文を読もう。

$N$の最大の素因数が欲しいから、$N$を素因数分解して、一番大きな素因数を答えればいいかな。

例えば、入力例1は、

\[35 = 5 \times 7\]

だから、7を出力すればいいんだよね。

素因数分解って、プログラムでどうすればできるんだろう。

「ゆいちゃんにはこの問題に限らずまず考えてもらいたい解法があるんだけど、何だったかな？」

「あ、「全探索」ですよね、これで昨日のPBCのD問題が解けました」

「お、偉いね！」

「何度も言うけど、競技プログラミングの基本は「全探索」だからね」

「じゃあ、この問題を全探索で解くプログラムを書いてみて！」

全探索ね......。

実際に素因数分解をするときみたいに、小さい数から割る数を全部試していけば良さそう。

【挿絵表示】

同じ素数で何回も割るかもしれないから、昨日やったwhile文で書こう。

一番最後に出てくる素数がこの問題の答えになるね。

N = int(input())

i = 2

while i < N:

if N % i == 0:

N //= i

else:

i += 1

print(N)

入力例を試してみよう。

>python main.py

>35

7

一つ目の入力例はあってる。

>python main.py

>97

97

うん。二つ目もあってる。よし、できた！

「ゆいちゃんみたいな若い子が成長するのを見ると昔を思い出すのお、ふぉっふぉっふぉ」

「ひまちゃんはまだそんな年じゃないでしょ」

「じゃあ、「計算量」を実感してもらおうかな、パソコン借りるね」

試しに大きな素数を入力してみるね、とひまり先輩が言って、私のパソコンに値を打ち込んだ。

>python main.py

>998244353

あれ、答えが返ってこない......

「まあ、こんな感じだね」

「今書いたプログラムに998244353を入力すると、while文が何回実行されるか分かる？」

哀先輩が私に尋ねた。

「998244353って数が素数なのが重要だね！」

2から$(998244353 - 1)$までの数をwhile文で試すとき、全部素数の998244353を割れないから$N$は最後まで同じ数になる。

while文は2から$(998244353 - 1)$まで一回ずつ実行されることになるから、2から$(998244353 - 1)$までの数の個数を数えればいいね。

終わりから始まりの数字を引いて$(998244353 - 1) - 2$回かな。

「惜しい、それだと3を入力したときに0回になっちゃうよ」

「ほんとだ、じゃあ1を足して、$(998244353 - 1) - 2 + 1$回ですね」

「正解！」

「1回程度の計算ならパソコンの計算時間はほとんど変わらないから、計算コストを考えるときは無視したい」

「だから、計算コストが何の変数に比例しているかをざっくり知りたいときに、計算量の記法を使うよ」

「このプログラムを例にして言うと、最悪ケースとして、

$N$が素数だった場合を考えると、だいたい$N$回の計算をすることが分かる。

このことを、「最悪計算量がO(N)」と言う」

「えっと......計算量と計算コストって何が違うんですか？」

「計算コストという言葉は「計算コストが高い」とか「計算コストが低い」くらいにざっくりした意味で使われることが多い。計算量は、計算コストを分かりやすく表す指標の一つ」

「「$O(N)$の計算量」って言うと、入力される$N$の大きさと同じくらいの速度で計算コストが増えていくってことを表せるんだよ」

なるほど。計算量についてちょっとわかった気がする。

「今回の制約を見てみて」

制約

入力はすべて整数

$2 \leq N \leq 10^{12}$

「1秒間に実行できるプログラムの命令数は$10^8$くらいだよ」

「ほうほう」

「この問題では$N$の上限が$10^{12}$で$10^8$より1万倍大きいから、

$O(N)$のアルゴリズムではおおざっぱに1万秒くらいかかる計算になる」

「計算量を考えると、実装する前から計算コストの見積もりができるのが嬉しいところだね」

へえ～。問題が難しくなってくると、そのプログラムの計算量を考えないといけなくなってくるんだね。

「それじゃあ、今回の問題で計算量？を良くするには、全く別の方法を考えないといけないんですか？」

「いや、全然悪くない。今のアルゴリズムはすぐに高速化できる」

「素数のときに最後まで調べてしまうことが問題だから、そこを直せばいいよ」

N = int(input())

i = 2

# while文の条件を変えたよ！

while i * i <= N:

if N % i == 0:

N //= i

else:

i += 1

print(N)

「実際に実行してみるね」

>python main.py

>998244353

998244353

すごい、すぐに答えが返ってきた。

でも、今変えたところって一行だけだったよね。while文の条件。

while i < N:

↓

while i * i <= N:

素数であるかを調べるのに、私のプログラムだと割る数を2から$N-1$まで全部試してた。

だけど、新しい方のプログラムはどういう条件なんだろう。

「ある数$N$が素数であるかどうかって、実は最後まで調べなくても分かるんだよね。

例えば、25が素数かどうかを調べるには、2から5までで十分だよ」

「え、全部調べなくていいんですか？」

「例えば、122を61で割ると、\[122 = 2 \times 61\] だから、61で割る前に2で割れるよね」

「確かに」

「割る数が割った商以下になる数字だけ考えたらいいよね。

だから、割る数を2乗して$N$より大きくなる直前まで調べることにしようよ」

$割る数\times 商 = 割られる数$と書くと、

\[1\times30 = 30 \]

\[2\times15 = 30 \]

\[3\times10 = 30 \]

\[5\times6 = 30 \]

ここから下はひっくり返せば同じになるから、考えなくて大丈夫だよ。

\[6\times5 = 30 \]

\[10\times3 = 30 \]

\[15\times2 = 30 \]

\[30\times1 = 30 \]

「すこし変えただけだけど、このプログラムの最悪計算量は$O(\sqrt{N})$になった」

入力が素数のときに割る数として調べる最大の整数を$x$と書くと、

\[x^2 \propto N \]

\[\Rightarrow x \propto \sqrt{N}\]

$\propto$は比例する、って意味の記号。

最大の整数のまでfor文で1つずつ数えるから、計算量は$O(\sqrt{N})$になるよ。

「実は、一般的には素因数分解は難しい問題なんだよ」

「そうなんですか？中学校でやるから簡単なんだと思ってました」

「ある数が素数であるか確かめるのが難しいことを利用したRSA暗号があるくらいだからね」

「今やったみたいに、計算量を減らして行ったら解けちゃったりしないんですか？」

「RSA暗号の鍵は4096bitくらいの数だから、全く心配いらない」

「4096bit！......ってどれくらいの大きさなんですか？」

「今計算した素数が32bitくらいだね。

1bit増えることに表現できる数は2倍になっていくから、

4096bitなら今の数字の$2^{4000}$倍くらい大きい数になるよ」

「$2^{67} - 1$の素因数分解をパソコンを使わずに解いてる人もいたけどね......

さすがにこれくらいが人間の限界だと思うよ」

print(2**67 - 1)

>python main.py

147573952589676412927

「本当にこれを手計算で因数分解したんですか......」

「さすがに真似できないね～」