スクリーンショット_2019-09-28_23

ABC142:素数の個数と復習について

競技プログラミングAtCoderで開催されたAtCoder Beginner Contest 142に参加した。出題された問題は問題Aから問題Fまでの6問。問題Aは簡単で、問題Fへ進むにつれてどんどん難易度が上がる。

今回の小さな目標は「問題A、問題B、問題Cの3問は1発ACを出す。そして、問題DでACを出す」でした。「問題A、問題B、問題Cの3問は1発ACを出す。」はやや遅かったものの達成。しかし、「問題DでACを出す」は達成できず。順位は 5235人中3219位。上位61%くらいで、満足いかない結果。敗因を振り返る。

素因数分解したら素数の個数は簡単に計算できる。

競技プログラミングでは、数学の知識がないとなんともできない問題がよく出る。今回解くことができなかった問題もその類。今回できなかった問題では、
・AとBの最大公約数を計算する
・最大公約数の約数の中で、素数の数を数える
という問題が出題された。

AとBが小さい数字なら大したことがない。しかし、問題ではAとBの最大値は10の12乗に設定されている。ということは最大公約数も10の12乗くらいの数値になる可能性があり、その10の12乗くらいの数値から約数を探して、素数をチェックする。一体、何回チェックする必要があるんだろう?きっと多いだろうということはわかる。

競技プログラミングでは、実行時間制限が設定されている。実行時間制限が2秒と設定している場合は、2秒でプログラムが終わらないといけない。例えば、1,2,3,4と順番にカウントしていき、10の12乗まで続けたとすると、計算量が10の12乗回となり、まぁ2秒では終わらない。計算量が1,000,000(10の6乗)くらいだったら、まぁ問題なく、2秒以内に終わる。今回は、計算量を少なくする工夫でも、数学というか算数の知識が問われた。

例えば、100の約数を調べるとする。
1回目の調査:100は1で割り切れる。
2回目の調査:100は2で割り切れる。
3回目の調査:100は3で割り切れない。
4回目の調査:100は4で割り切れる。
5回目の調査:100は5で割り切れる。
...
20回目の調査:100は20で割り切れる。
...
100回目の調査:100は100で割り切れる。
100回調査して、約数は9個(1,2,4,5,10,20,25,50,100)あることがわかる。

この調査を次のように考え直す。

1回目の調査:100 ÷ 1 = 100 あまり 0 なので、1でも100でも割り切れる。
2回目の調査:100 ÷ 2 = 50 あまり 0 なので、2でも50でも割り切れる。
3回目の調査:100 ÷ 3 は割り切れない。
4回目の調査:100 ÷ 4 = 25 あまり 0 なので、4でも25でも割り切れる。
5回目の調査:100 ÷ 5 = 20 あまり 0 なので、5でも20でも割り切れる。
...
10回目の調査:100 ÷ 10 = 10 あまり 0 なので、10で割り切れる。
...
20回目の調査:100 ÷ 20 = 5 あまり 0 なので、20でも5でも割り切れる。
...
以下省略。

調査を上記のように考え直すと20回目の調査の結果は、5回目の調査の結果と同じことを言っているので、やる意味はない。今回、意味がある調査は10回目までである。
すなわち、100回調べていたことが10回調べればいいということになる。

少し考えたらわかることですが、なかなか気がつかない。

今回の敗因は、数学や算数の知識というかセンスというか、その辺の感覚。

競技プログラミングでは復習が重要だ。特に手をつけてみたものの不正解だった問題は必ずできるようになっておく。これから先、全く同じ問題は出ないと思うけど、テーマというか必要な知識が、過去の問題と同じになる可能性はある。幸い過去問も公開されているので、たくさん復習しようと思う。

この記事が気に入ったら、サポートをしてみませんか?気軽にクリエイターを支援できます。

ありがとうございます!
4

Takahiro Nakamori

三重県伊勢市でiOS・AndroidアプリのUX設計・UIデザイン・実装、Webサイト、Webアプリの情報設計、UIデザイン、実装を行なっています。また、競技プログラミングに参加したり、読書をしたり、2羽の文鳥と遊んだり、写真を撮ったり、洋菓子を作ったりしています。
コメントを投稿するには、 ログイン または 会員登録 をする必要があります。