EX19 - 計算量の見積もり Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

説明ページに戻る

問題文

次のプログラムでは f0 から f5 の 6 つの関数が定義されており、main 関数から呼び出されています。
それぞれの関数の計算量を見積もって、最も計算時間のかかる関数を呼び出している行をコメントアウトし、PyPy で提出してください。

制限時間は 2 秒です。なお、AtCoder のジャッジでは 1 秒あたり 10^8 〜 10^9 回程度の計算が可能です。

最も計算時間のかかる関数を呼び出している行がコメントアウトされていない場合、提出結果は となります。
また、PyPy ではなく CPython で提出すると、正しくコメントアウトされている場合でも となるので注意してください。

制約を読み、各関数の実行時間を見積もりましょう。

プログラム
def f0(N):
    return 1

def f1(N, M):
    s = 0
    for i in range(N):
        s += 1
    for i in range(M):
        s += 1
    return s

def f2(N):
    s = 0
    for i in range(N):
        t = N
        cnt = 0
        while t > 0:
            cnt += 1
            t //= 2
        s += cnt
    return s

def f3(N):
    s = 0
    for i in range(3):
        for j in range(3):
            s += 1
    return s

def f4(N):
    s = 0
    for i in range(N):
        for j in range(N):
            s += i + j
    return s

def f5(N, M):
    s = 0
    for i in range(N):
        for j in range(M):
            s += i + j
    return s

# 標準入力から値を取得
N, M = map(int, input().split())

# 計算結果の変数を初期化
a0, a1, a2, a3, a4, a5 = -1, -1, -1, -1, -1, -1

# 計算量が最も大きいものを 1 つだけコメントアウトする (先頭に # をつける)
a0 = f0(N)
a1 = f1(N, M)
a2 = f2(N)
a3 = f3(N)
a4 = f4(N)
a5 = f5(N, M)

# 結果を出力
print(f"f0: {a0}")
print(f"f1: {a1}")
print(f"f2: {a2}")
print(f"f3: {a3}")
print(f"f4: {a4}")
print(f"f5: {a5}")

制約

  • 0 \leq N \leq 10^6
  • 0 \leq M \leq 10^2

回答例

答え方の例です。

この例では f0 の呼び出しをコメントアウトしていますが、f0 の計算量は O(1) 時間なので、この回答は不正解 となります。

def f0(N):
    return 1

def f1(N, M):
    s = 0
    for i in range(N):
        s += 1
    for i in range(M):
        s += 1
    return s

def f2(N):
    s = 0
    for i in range(N):
        t = N
        cnt = 0
        while t > 0:
            cnt += 1
            t //= 2
        s += cnt
    return s

def f3(N):
    s = 0
    for i in range(3):
        for j in range(3):
            s += 1
    return s

def f4(N):
    s = 0
    for i in range(N):
        for j in range(N):
            s += i + j
    return s

def f5(N, M):
    s = 0
    for i in range(N):
        for j in range(M):
            s += i + j
    return s

# 標準入力から値を取得
N, M = map(int, input().split())

# 計算結果の変数を初期化
a0, a1, a2, a3, a4, a5 = -1, -1, -1, -1, -1, -1

# 計算量が最も大きいものを 1 つだけコメントアウトする (先頭に # をつける)
# a0 = f0(N)
a1 = f1(N, M)
a2 = f2(N)
a3 = f3(N)
a4 = f4(N)
a5 = f5(N, M)

# 結果を出力
print(f"f0: {a0}")
print(f"f1: {a1}")
print(f"f2: {a2}")
print(f"f3: {a3}")
print(f"f4: {a4}")
print(f"f5: {a5}")

ヒント

クリックでヒントを開く

それぞれの関数の時間計算量を示します。

時間計算量
f0 O(1)
f1 O(N+M)
f2 O(N \log N)
f3 O(1)
f4 O(N^2)
f5 O(NM)

N と M の大きさを考えて、最も実行時間が長いものをコメントアウトしましょう。

テスト入出力

書いたプログラムが AC にならず、原因がどうしてもわからないときだけ見てください。

クリックでテスト入出力を見る

テスト入力1

1000000 100

テスト出力1

f0: 1
f1: 1000100
f2: 20000000
f3: 9
f4: -1
f5: 50004900000000

解答例

必ず自分で問題に挑戦してみてから見てください。

クリックで解答例を見る 
def f0(N):
    return 1

def f1(N, M):
    s = 0
    for i in range(N):
        s += 1
    for i in range(M):
        s += 1
    return s

def f2(N):
    s = 0
    for i in range(N):
        t = N
        cnt = 0
        while t > 0:
            cnt += 1
            t //= 2
        s += cnt
    return s

def f3(N):
    s = 0
    for i in range(3):
        for j in range(3):
            s += 1
    return s

def f4(N):
    s = 0
    for i in range(N):
        for j in range(N):
            s += i + j
    return s

def f5(N, M):
    s = 0
    for i in range(N):
        for j in range(M):
            s += i + j
    return s

# 標準入力から値を取得
N, M = map(int, input().split())

# 計算結果の変数を初期化
a0, a1, a2, a3, a4, a5 = -1, -1, -1, -1, -1, -1

# 計算量が最も大きいものを 1 つだけコメントアウトする (先頭に # をつける)
a0 = f0(N)
a1 = f1(N, M)
a2 = f2(N)
a3 = f3(N)
# a4 = f4(N)
a5 = f5(N, M)

# 結果を出力
print(f"f0: {a0}")
print(f"f1: {a1}")
print(f"f2: {a2}")
print(f"f3: {a3}")
print(f"f4: {a4}")
print(f"f5: {a5}")