Atcoder灰色の為のアルゴリズムノート【1/3】

Atcoder灰色から茶色になるために必要な知識をまとめたノートを公開します。灰色帯では基本文法をおさえることが求められますが、中には知識があれば容易に解くことが出来る問題もあるので、それについて本記事では紹介します。

目次

  • はじめに
  • 要素の分布を求める
  • 約数列挙
  • 素数判定
  • おわりに

はじめに

まずは具体的にAtcoder茶色が「どの問題がどのぐらいの速度で解く必要があるのかどうか」を示します。

Atcoder茶色はA問題、B問題、C問題をコンテスト中に解けるレベルです。

  • A, B問題はプログラミング言語の基本文法を理解していれば解けます。
  • C問題はdiff300になるように作問されているらしいです。(C以降はdiff500差になる)

実際、作問陣もdiff推定には苦戦しているらしく、あくまで目安としてとらえてください。Atcoder Ploblems を見て分かる通り、diffにはばらつきがあります。

#1 -> 本記事
#2 -> 近日公開
#3 -> 近日公開

「補足」の項は必須ではないので、分からなければ読み飛ばしてください。

要素の分布を求める

辞書を用いて配列の要素の分布を数えます。Atcoderでも頻出であり、C問題によく出題されます。詳しい計算量解析については省略しますが、計算量は`O(N)`です。

・ソースコード

A = list(map(int,input().split()))
cnt = {}
for i in range(N):
    ele = A[i]
    if(ele in cnt):
        cnt[ele] += 1
    else:
        cnt[ele] = 1
print(cnt)

A : 配列
N : 配列の長さ

・入出力例

入力

1 2 3 3 2


出力

{1:1, 2:2, 3:2}

・説明

辞書のキーは要素、値はその個数です。
上の例でいうと「1が1個、2が2個、3が2個」であることを表しています。

  1. cntという配列を用意します。
  2. 配列Aの要素を舐めます。(配列の全ての要素をfor文でアクセスすることを舐めるといいます)
  3. i番目の要素A[i]eleとし、cntのキーに存在しているかによって場合分けします。
    • 存在している場合 : cnt[ele]に1を加算します。
    • 存在していない場合 : eleのキーを作成し、初期値を1にしまう。

・問題例

C – Socks (ABC295) (diff122)
C – Collision 2 (ABC243) (diff409)

・補足

collecitionsライブラリののCounterメソッドでも同様のことが出来ます。一つの配列から分布をカウントするなど簡単なものではこちらを使う方法もあります。しかしながら、最初のうちは使い分けをするのが難しいと思うので、上の実装でよいと思います。ソースコードを示します。

import collections
cnt = collections.Counter(A)

約数列挙

ある数 N の正の約数を列挙します。Atcoderでは数学の知識が必要な問題が多くあり、約数列挙もそのひとつです。C問題では簡単な計算量解析を行う能力が問われ、約数列挙アルゴリズムの計算量削減のテクニックはすごく有名であるので、出題される頻度が多いです。

・ソースコード

def divisor(n):
    if(n == 1):
        return [1]
    lower = []
    upper = []
    for i in range(1,n):
        if(i*i > n):
            continue
        if(n%i == 0):
            lower.append(i)
            if(i == n//i):
                continue
            upper.append(n//i)
    return lower + upper[::-1]

n = int(input())
A = divisor(n)
print(A)     

・入出力例

入力

60

出力

 [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60]

・説明

約数はAB=Nとなる(A, B)の組と言い換えられるので、片方が求まればもう片方を求めることが出来ますA≦Bとしたとき1≦A≦√Nであるので、√Nまで試行すれば約数をすべて求めることができます。
よって計算量はO(√N) です。

  1. 小さい数を入れるリスト、大きい数を入れるリストをそれぞれ作成する。
  2. i を 1 から √N まで回し、割り切れたら約数としてリストに格納する。(i*i≧Nとなるとループを抜けるという実装をしています)
    • i = N//i となる場合に注意してください。格納するのはリスト1か2のどちらかにします。
  3. リスト1とリスト2の逆順を結合し、返り値とします。

・問題例

C – Cream puff (ABC180) (diff142)
C – Four Variables (ABC292) (diff404)

・補足

今回はO(√N)の約数列挙を紹介しました。Googleで「約数列挙 高速」と検索すると同じような記事がヒットしますが、これのほかにも約数列挙のアルゴリズムが存在します。それは素因数分解アルゴリズムを利用します。ロー法を用いた約数列挙ではN≧10^7の場合、かなり高速になると考えられます。

ポラード・ロー素因数分解法について

素数判定

ある数 N が素数であるか判定しています。

素数とは、2 以上の整数のうち、1 と自分自身以外では割り切れない整数のことです。

素数とは | アルゴ式

Atcoderでは素数判定のアルゴリズム単体で出題されるケースはあまりありませんが、素数の性質を利用する問題がよく出題されます。素数判定アルゴリズムはそれらの基礎となります。

・ソースコード

def is_prime(n):
    if(n < 2): return False
    for i in range(2,n):
        if(n%i == 0):
            return False
    return True

n = int(input())
print(is_prime(n))

・入出力例

入力

12

出力

False

入力

17

出力

True

・説明

約数列挙の時と同様に√Nまでを試行すればよいです。証明をアルゴ式から引用します。

N が素数ではないとき、ある整数 xN​ が存在して、N が x で割り切れることを示せばよいです。

仮にそのような整数 x が存在せず、代わりに N が N​ より大きい整数 a で割り切れるとしてみましょう。このとき、

N=a×b (N を a で割った商を b とする)

と表したときに、N は b でも割り切れることに注意しましょう。a>N​ より、b=aN​<N​ ですので、これは矛盾です。

以上より、N が素数でないのならば、i=2,3,…,N​ までを調べれば、その中にかならず N の約数が含まれていることがわかりました。

素数判定のアルゴリズム | アルゴ式
  1. nが2未満のときは例外処理をします。
  2. i を 2 から √N まで回し、割り切れたら素数ではないので、返り値をFalseとします。
  3. 最後まで割り切れなかったら素数なので、返り値をTrueとします。。

・問題例

C – Next Prime (ABC149) (diff172)

・補足

今回は基本的なO(√N)の判定を紹介しました。素数判定法にはミラーラビン素数判定法というものがあり、こちらは上位互換で計算量はO(logN)です。先ほどの項で紹介したロー法にもこれが使われています。
Miller–Rabin(ミラーラビン)素数判定法について理解したい

おわりに

私が灰色のときは、結構大雑把に理解しているだけでコードコピペなどを多用していたのですが、Atcoderのレートが昔と比べてかなり上げにくくなりました。(Atcoderのレーティングシステムは相対評価なのでみんなが賢くなった)。昔はA問題ではfor文なしでも解ける問題しか出題しない規定みたいなものがあったのですが、それも撤廃されたので、今の灰色帯は大変だと思います。茶色目指して頑張ってください。