E869120's Blog

アルゴリズムや競技プログラミングに関する記事を書きます。

大実験!ChatGPTは競プロの問題を解けるのか (2024年5月版)

1. はじめに

2024 年 5 月 14 日、OpenAI 社から新たな生成 AI「GPT-4o」が発表され、世界に大きな衝撃を与えました。これまでの GPT-4 よりも性能を向上させただけでなく1、音声や画像のリアルタイム処理も実現し、さらに応答速度が大幅に速くなりました。「ついにシンギュラリティが来てしまったか」「まるで SF の世界を生きているような感覚だ」という感想も見受けられました。

しかし、いくら生成 AI とはいえ、競技プログラミングの問題を解くのは非常に難しいです。なぜなら競技プログラミングでは、問題文を理解する能力、プログラムを実装する能力だけでなく、より速く答えを求められる解法 (アルゴリズム) を考える能力も要求されるからです。もし ChatGPT が競技プログラミングを出来るようになれば他のあらゆるタスクをこなせるだろう、と考える人もいます。

それでは、現代最強の汎用型生成 AI である GPT-4o は、果たしてどれくらい競技プログラミングの問題を解くことができるのでしょうか。本記事では、国内トップレベルの競技プログラマーである筆者が、その実験結果について記したいと思います。

目次

  1. はじめに
  2. 競技プログラミングとは
  3. 実験方法
  4. 実験結果
  5. まとめと注意点
  6. おわりに


2. 競技プログラミングとは

まずは競技プログラミングを知らない方のために、競技プログラミング (競プロ) とは一体どういうものかを説明します。知っている方は読み飛ばして構いません。

競技プログラミングは、プログラミングの問題を解く大会です。プログラミングの大会と聞くと、皆さんの多くはアプリ開発やロボット製作などを思い浮かべると思いますが、競プロはそれとは違います。いくつかの問題が出題され、2 時間といった制限時間内に何問解けるかを競う大会です。数学の試験のプログラミング版だと考えるとわかりやすいでしょう。

問題例 1

それでは、競プロではどんな問題が出題されるのでしょうか。問題例として、以下が挙げられます。

リンゴが 3 個、ミカンが N 個ある。ミカンの個数が入力として与えられるので、果物の合計個数を出力するプログラムを作成せよ。ただし N は 1 以上 100 以下である。

この問題は非常に簡単で、たとえば代表的なプログラミング言語 Python を使った場合、次のようなプログラムを書くと正解となります。

N = int(input())
print(N + 3)

問題例 2

しかし、もう少し難しい問題になると、プログラムの実行時間も要求されます。例として、以下の問題を考えてみましょう。

足す数・足される数が 1 以上 N 以下、答えが M 以下となる足し算はいくつあるか。ただし N と M は 30 万以下である。

たとえば N=3, M=5 の場合、1+1=2、1+2=3、1+3=4、2+1=3、2+2=4、2+3=5、3+1=4、3+2=5 の 8 個の足し算があるため、答えは 8 である。

自然にプログラムを書くと、以下のようになります。

N = int(input())
M = int(input())
Answer = 0
for i in range(1, N+1): # 足す数
    for j in range(1, N+1): # 足される数
        if i + j <= M:
            Answer += 1
print(Answer)

このプログラムは確かに正しい答えを出力します。

しかし、このプログラムに N = 300000, M = 300000 を入力して実行してみましょう。残念ながら 1 分経っても答えが出力されず、不正解となってしまいます。

なぜなら、二重の for 文を使っているため 30 万掛ける 30 万、つまり 900 億回の計算を行っているからです。そして 900 億回の計算は、現代の PC をもっててしても一瞬では終わらない計算だからです。2

そこで、少しプログラムを変えて以下のようにしてみましょう。

N = int(input())
M = int(input())
Answer = 0
for i in range(1, N+1): # 足す数
    Answer += max(0, min(N, M-i))
print(Answer)

二重の for 文が一重の for 文に変わったため、実行時間が大幅に短くなり、これでようやく正解となりました。

このように競プロでは、プログラムを実装する能力だけでなく、「どうやったらより速く答えを出せるのか」を考える能力が必要であるため、非常に難しい頭脳勝負となっています。

AtCoder について

次に、日本を代表する競プロの大会である「AtCoder」について紹介します。

AtCoder は国内最大規模のコンテストサイトであり、毎週土曜日か日曜日の 21 時から、2 時間程度のコンテストがオンラインで開催されます。日本国内だけで 5000 人、海外を含めると 1 万人以上が同時に参加し、AtCoder の登録者数は 50 万人を超える規模となっています。

また、AtCoder のコンテストに参加すると、成績に応じてレーティングが付けられます。レーティングは強さの証明となるため、技術系アルバイトや就職・転職などで用いられることもあります。

AtCoder は日本語版の問題文も提供されており、初心者に比較的親切であるため、この記事で競プロに興味を持った方はぜひ AtCoder を始めましょう。


3. 実験方法

それでは本題に戻ります。

今回は ChatGPT の性能を調べるため、ChatGPT に競プロの問題を 10 問出題しました。ここで問題は難易度順に並べられており、検索やブラウジング機能、学習データによる利益を一切封じるため、すべて筆者オリジナルの問題にしました。3

また、ChatGPT の性能を最大限発揮させるため、問題文は学習データの多い英語版で提供することにしました。ここで、筆者は英語がそれほど得意ではないため、無料版 Grammarly による添削を行った後の問題文を提供しました。

さらに、問題文には AtCoder と同様、制約・入力形式・出力形式・入出力例を付けることにしました。つまり、以下のような形式で問題文が与えられます。

# Problem Statement
There are 3 apples and N bananas.
Write a program that prints the total number of fruits.

# Constraints
- 1 <= N <= 100
- N is an integer

# Input
N

# Output
Print the answer.

# Sample Input
7

# Sample Output
10

そして、ChatGPT が置かれている状況をプロンプトに入れると性能が上がるという情報もあるため、今回は以下のようなプロンプトを与えることにしました。

You are one of the top competitive programmers in the world.
Write a code to solve the following problem.
Any programming language is allowed.

---

(問題文をここに貼り付ける)

フィードバック

続いて、ChatGPT が回答を提出した後、どのような形式でフィードバックを与えるかについて説明します。

原則以下の 6 通りのいずれかのフィードバックを与え、これらのフィードバックのみ (= 原則人間の手助け無し) で正解にたどり着いたものだけに得点を与えます。3 回目の提出で正解にたどり着けなかったものは不正解とみなします。

ケース フィードバック
コンパイルが通らない場合 Unfortunately, your solution is judged as Compile Error. Please fix your solution.
入力例で不正解となった場合 Unfortunately, your solution does not output the correct answer for Sample Input. Please fix your solution.
その他のケースで不正解となった場合 Unfortunately, your solution judged as Wrong Answer. Please fix your solution.
実行時エラーとなった場合 Unfortunately, your solution judged as Runtime Error. Please fix your solution.
実行時間制限超過となった場合 Unfortunately, your solution judged as Time Limit Exceeded. Please improve time complexity of your solution.
正解となった場合 Congratulations! You submitted a correct solution.

それでは、果たして ChatGPT は 10 問中何問を解くことができるのでしょうか。いよいよお待ちかねの結果発表です。


4. 実験結果

まずは 1 問目から順番に行きたいと思います。

第 1 問

# Problem Statement
Mr.LLM bought N items in a supermarket. The price of i-th item was A[i] dollars. Write a program that outputs the total price.

# Constraints
- 1 <= N <= 100
- 1 <= A[i] <= 100 (1 <= i <= N)
- All input values are integer

# Input
N
A[1] A[2] A[3] ... A[N]

# Output
Print the answer.

# Sample Input 1
5
3 1 4 1 5

# Sample Output 1
14

日本語の問題文は次のようになります。

LLM さんはスーパーで N 個の品物を買った。i 個目の品物の価格は A[i] ドルだった。合計価格を出力せよ。

配列を入力して足し算をするだけなので簡単ですね。現役のプログラマなら絶対解かなければならない問題です。もちろん ChatGPT も簡単に解くことが出来ました。

def total_price():
    # Read input
    N = int(input())
    A = list(map(int, input().split()))
    
    # Calculate the total price
    total = sum(A)
    
    # Output the result
    print(total)

# Call the function to execute
total_price()


第 2 問

# Problem Statement
There is a string S of length N. All characters in string S are from 'a' to 'z'. A string is good if the following two conditions are satisfied:

1. There are exactly 5 kinds of character
2. Every two adjacent characters are different

Write a program that outputs whether the given string S is good or not.

# Constraints
- 1 <= N <= 100

# Input
N
S

# Output
If string S is good, print 'Yes'. Otherwise, print 'No'.

# Sample Input
11
abracadabra

# Sample Output
Yes

日本語の問題文は次のようになります。

N 文字の英小文字からなる文字列 S が与えられる。文字列が以下の 2 つの条件を満たすとき、良い文字列という。

  1. ちょうど 5 種類の文字がある。
  2. どの隣接する 2 文字も異なる文字である

1 問目よりは少し問題設定が複雑になりましたが、この難易度であれば AtCoder 参加者の 80% 以上が解くことができるでしょう。もちろん ChatGPT も簡単に解くことが出来ました。

def is_good_string():
    # Read input
    N = int(input())
    S = input().strip()
    
    # Check if the string has exactly 5 kinds of characters
    unique_chars = set(S)
    if len(unique_chars) != 5:
        print("No")
        return
    
    # Check if every two adjacent characters are different
    for i in range(1, N):
        if S[i] == S[i - 1]:
            print("No")
            return
    
    # If both conditions are satisfied
    print("Yes")

# Call the function to execute
is_good_string()


第 3 問

# Problem Statement
There is a grid with R rows and C columns. The cell on the i-th row and the j-th column is denoted as cell (i, j).

For each (i, j) (1 <= i <= R, 1 <= j <= C), cell (i, j) is colored black if A[i][j]=1, and colored white if A[i][j]=0.

Mr.LLM wants to know whether 4*4 black subgrid exists in the grid.

More formally, he wants to know whether there exists a value (a, b) (1 <= a <= R-3, 1 <= b <= C-3) that all cells (i, j) (a <= i <= a+3, b <= j <= b+3) are black.

Write a program that outputs the answer.

# Constraints
- 4 <= R <= 100
- 4 <= C <= 100
- 0 <= A[i][j] <= 1 (1 <= i <= H, 1 <= j <= W)
- All input values are integer

# Input
R C
A[1][1] A[1][2] A[1][3] ... A[1][C]
A[2][1] A[2][2] A[2][3] ... A[2][C]
:
A[R][1] A[R][2] A[R][3] ... A[R][C]

# Output
If 4*4 subgrid exists, print 'Yes'. Otherwise, print 'No'.

# Sample Input
5 5
1 1 0 1 0
1 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1

# Sample Output
Yes

日本語の問題文は以下のようになります。

R 行 C 列のマス目が与えられる。各マスは黒か白で塗られている。全部黒で塗られている 4×4 の領域があるかを判定せよ。

少し難しくなってきた人も多いかもしれませんが、4×4 の領域を全部調べるという方法で解くことができます。たとえば下図の例の場合、以下の 4 通りを調べると答えを出すことができます。一番最後の 4 番目が条件を満たしているため、答えは Yes です。

それでは、ChatGPT はこの問題を解くことができるのでしょうか。4 重の for 文などの複雑な実装が要求されますが、余裕で解くことが出来ました。この時点で、AtCoder 参加者の約 25% を上回っています。

def find_black_subgrid():
    # Read the dimensions of the grid
    R, C = map(int, input().split())
    
    # Read the grid
    A = [list(map(int, input().split())) for _ in range(R)]
    
    # Check for a 4x4 subgrid of all black cells
    for i in range(R - 3):
        for j in range(C - 3):
            all_black = True
            for x in range(i, i + 4):
                for y in range(j, j + 4):
                    if A[x][y] != 1:
                        all_black = False
                        break
                if not all_black:
                    break
            if all_black:
                print("Yes")
                return
    
    print("No")

# Call the function to execute
find_black_subgrid()


第 4 問

# Problem Statement
An integer is good if it is multiple of 2024 and the sum of digits is less than or equal to K.

Write a program that outputs how many integers between 1 and N are good.

# Constraints
- 1 <= K <= 100
- 1 <= N <= 10^{10}
- All input values are integer

# Input
K N

# Output
Print the answer.

# Sample Input
20 10000

# Sample Output
3

日本語の問題文は以下のようになります。

2024 の倍数かつ各位の数字の和が K 以下であるものを「良い整数」と呼ぶ。1 以上 N 以下の整数の中で、良い整数はいくつあるか。

この問題を解く最も単純な方法として、1 が良い整数か、2 が良い整数か、3 が良い整数か、のように順番に調べていく方法があります。この方法を Python で実装すると以下のようになります。

# sumdigit は各位の数字の和を返す関数とする。ここでは省略する。
K, N = map(int, input().split())
Answer = 0
for i in range(1, N+1):
    if N % 2024 == 0 and sumdigit(N) <= K
        Answer += 1
print(Answer)

しかし、本問題の制約は「N が 100 億以下」であるため、この方法だと最大 100 億回以上の計算を行うことになり、実行に時間がかかってしまいます。このままでは正解できません。

そこで、2024 の倍数だけを調べるという工夫をすることで、実行時間を大幅に削減することができます。つまり、2024 は良い整数か、4048 は良い整数か、6072 は良い整数か、のように調べるということです。この工夫を思いつけるかどうかが、本問題を解く最大の鍵となります。

それでは、ChatGPT はこの問題を解けるのでしょうか。以下のように、工夫した解法でしっかり解いてきました。

def count_good_integers():
    import sys
    input = sys.stdin.read
    data = input().split()
    K = int(data[0])
    N = int(data[1])
    
    def sum_of_digits(x):
        return sum(int(digit) for digit in str(x))
    
    count = 0
    for num in range(2024, N + 1, 2024):
        if sum_of_digits(num) <= K:
            count += 1
    
    print(count)

# Call the function to execute
count_good_integers()


第 5 問

# Problem Statement
You are given an integer N. Write a program that outputs an array A = {A[1], A[2], ..., A[N]} (length is N) which satisfies the following conditions:

1. A[1] < A[2] < ... < A[N]
2. For each i (1 <= i <= N), A[i] is an integer between 1 and 1000000.
3. For each i (1 <= i <= N-1), A[i+1] is divisible by A[i].
4. For each i (1 <= i <= N-2), A[i+2] is divisible by A[i]+A[i+1].

# Constraints
- 1 <= N <= 6
- N is an integer

# Input
N

# Output
Print the answer in the following format.

A[1] A[2] ... A[N]

If there are multiple answer, any of them is regarded as correct.

# Sample Input
4

# Sample Output
5 10 30 120

日本語の問題文は以下のようになります。

整数 N が与えられる。次の条件を満たす数列 A[1], A[2], ..., A[N] を 1 つ作れ。

  • A[1] < A[2] < ... < A[N]
  • A[i] は 1 以上 100 万以下
  • どの i (1 <= i <= N-1) についても、A[i+1] は A[i] で割り切れる
  • どの i (1 <= i <= N-2) についても、A[i+2] は A[i]+A[i+1] で割り切れる

この問題は、実際に手を動かして考える必要があるという点で難しいですが、前から順に考えていけば数分で解くことができます。たとえば N=4 の場合を考えてみましょう。

  • A[1] について:適当に 5 とします。
  • A[2] について:A[1]=5 より 5 の倍数でなければならないので、適当に 10 とします。
  • A[3] について:A[1]=5, A[2]=10 より 10 と 15 の倍数なので、30 とします。
  • A[4] について:A[2]=10, A[3]=30 より 30 と 40 の倍数なので、120 とします。
  • これで正しい数列 [5, 10, 30, 120] を得ることができました。

それでは、ChatGPT はこの問題を解くことができるのでしょうか。なんと、ここで初めて間違ったプログラムを提出しました! 入力例の N=4 では [2, 6, 12, 48] を出力しましたが、残念ながら 48 は 6+12=18 の倍数ではないため、条件を満たしていません。

def generate_array(N):
    if N == 1:
        print(1)
        return
    elif N == 2:
        print(1, 2)
        return
    elif N == 3:
        print(1, 2, 6)
        return
    
    # Start with a small set of base values that satisfy the initial conditions
    A = [2, 6, 12]
    
    # Generate the rest of the values to satisfy the conditions
    for i in range(3, N):
        next_value = A[i-1] * (i + 1)
        A.append(next_value)
    
    # Output the generated array
    print(' '.join(map(str, A[:N])))

# Read input value N
N = int(input().strip())

# Generate and print the array
generate_array(N)

そこで、入力例で不正解であるということを ChatGPT に伝えたところ、今度はまったく別のプログラムを出してきました。しかし残念ながら、このプログラムは無限ループに陥ります。

その後も 2 回目のフィードバックを与えましたが、最後まで正解には至りませんでした。どうやら、ChatGPT は手を動かして考察しなければならない問題が苦手なようです。

def generate_array(N):
    if N == 1:
        print(1)
        return
    elif N == 2:
        print(1, 2)
        return
    elif N == 3:
        print(1, 2, 6)
        return
    
    # Start with a small set of base values that satisfy the initial conditions
    A = [1, 2, 6]
    
    # Generate the rest of the values to satisfy the conditions
    for i in range(3, N):
        next_value = A[i-2] + A[i-1]
        while next_value % A[i-1] != 0 or next_value % (A[i-2] + A[i-1]) != 0:
            next_value += A[i-1]
        A.append(next_value)
    
    # Output the generated array
    print(' '.join(map(str, A[:N])))

# Read input value N
N = int(input().strip())

# Generate and print the array
generate_array(N)


第 6 問

# Problem Statement
In LLM High School, the exam result is graded on a scale of 0 to N as follows.

- If the score of the exam was less than A[1] points, the grade will be 0.
- If the score of the exam was between A[1] points and A[2]-1 points, the grade will be 1.
- If the score of the exam was between A[2] points and A[3]-1 points, the grade will be 2.
- If the score of the exam was between A[3] points and A[4]-1 points, the grade will be 3.
- :
- If the score of the exam was more than or equal to A[N] points, the grade will be N.

Q students numbered from 1 to Q took the exam. The score of student i was S[i] points. Write a program that outputs the grade of each student.

# Constraints
- 1 <= N <= 200000
- 1 <= A[1] < A[2] < A[3] < ... < A[N] <= 1000000
- 1 <= Q <= 200000
- 1 <= S[i] <= 1000000 (1 <= i <= Q)
- All input values are integer

# Input
N
A[1] A[2] ... A[N]
Q
S[1] S[2] ... S[Q]

# Output
Print Q lines. In i-th line (1 <= i <= Q), print the grade for i-th student.

# Sample Input
4
50 65 80 90
5
66 96 35 49 50

# Sample Output
2
4
0
0
1

日本語の問題文は以下のようになります。

LLM 高校では、以下のように 0 から N までの N+1 段階の評定が付けられる。

  • 試験の点数が A[1] 点未満の場合、評定は「0」となる。
  • 試験の点数が A[1] 点以上 A[2] 点未満の場合、評定は「1」となる。
  • 試験の点数が A[2] 点以上 A[3] 点未満の場合、評定は「2」となる。
  • :
  • 試験の点数が A[N] 点以上の場合、評定は「N」となる。

Q 人の生徒が試験を受けた。各生徒の点数が与えられるので、各生徒の成績を出力せよ。

この問題の解答を自然に実装すると以下のようになります。しかし、このプログラムは二重の for 文を使っており、N×Q 回程度の計算が必要です。N, Q が両方上限の 20 万の場合は 400 億回となるため、実行に時間がかかってしまいます。

# Input
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
S = list(map(int, input().split()))

# Solve
for score in S: # score は生徒の点数
    grade = 0
    for border in A: # border は評定が変わる基準
        if score >= border:
            grade += 1
    print(grade)

そこで二分探索 (Binary Search) という典型的な手法を使うと4、プログラムを高速化することができます。なお、一般に二分探索などの基本的な典型手法を知っているかどうかは、競技プログラミング初級者と中級者の分け目となるため、実力を測る上では非常に重要な問題です。

それでは、ChatGPT はこの問題を解くことができるのでしょうか。なんと、一発で二分探索を使った正しいプログラムを提出しました。流石です。

from bisect import bisect_right

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    
    # Read N
    N = int(data[idx])
    idx += 1
    
    # Read A
    A = list(map(int, data[idx:idx+N]))
    idx += N
    
    # Read Q
    Q = int(data[idx])
    idx += 1
    
    # Read S
    S = list(map(int, data[idx:idx+Q]))
    
    # Process each student's score and determine the grade
    results = []
    for score in S:
        grade = bisect_right(A, score)
        results.append(grade)
    
    # Print results
    for result in results:
        print(result)

if __name__ == "__main__":
    main()


第 7 問

# Problem Statement
Mr.LLM finished the final exams, and the summer vacation of N days has started. However, he has to solve exactly M mathematics problems for homework. He decided to solve 0, 1, or 2 problems for each day, but he hasn't decided the number of problems to solve for each day. How many possible plans are there?

For example, if N=2 and M=3, there are 2 possible plans.

- Solve 1 problem on the first day, and solve 2 problems on the second day.
- Solve 2 problems on the first day, and solve 1 problem on the second day.

# Constraints
- 1 <= N <= 30
- 1 <= M <= 2N
- All input values are integer

# Input
N M

# Output
Print the answer.

# Sample Input
2 3

# Sample Output
2

日本語の問題文は以下のようになります。

LLM 氏には N 日間の夏休みがあるが、宿題が出されて合計 M 問の数学の問題を解かなければならない。そこで彼は毎日 0, 1, 2 問のいずれかの問題を解くことに決めた。何通りの計画があるかを答えよ。

この問題を解く最も単純な方法は、宿題の解き方を全部調べることです。しかし、以下の樹形図を見ると分かる通り、制約の上限である N=30 の場合は全部で 3 の 30 乗通りを調べる必要があります。3 の 30 乗は 200 兆を超えますので、当然時間内には実行が終わりません。そこで動的計画法という典型手法を使うと、この問題を高速に解くことができます。

それでは、ChatGPT は動的計画法を理解しているのでしょうか。そして、この問題は動的計画法で解けるんだということがしっかり分かるのでしょうか。

プロンプトを入力した結果、動的計画法を用いた正しい解答を出してきました。どうやら ChatGPT は典型手法を用いた問題が比較的得意のようです。

def count_plans(N, M):
    # Initialize the DP table with all zeros
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    
    # Base case: one way to assign 0 problems in 0 days
    dp[0][0] = 1
    
    # Fill the DP table
    for i in range(1, N + 1):
        for j in range(M + 1):
            # If solving 0 problems on the i-th day
            dp[i][j] += dp[i-1][j]
            # If solving 1 problem on the i-th day
            if j >= 1:
                dp[i][j] += dp[i-1][j-1]
            # If solving 2 problems on the i-th day
            if j >= 2:
                dp[i][j] += dp[i-1][j-2]
    
    # The answer is the number of ways to distribute M problems over N days
    return dp[N][M]

# Read input
N, M = map(int, input().strip().split())

# Print the result
print(count_plans(N, M))


第 8 問

# Problem Statement
You are given two integers A and B. Write a program that checks whether 2^A is strictly larger than 10^B or not.

# Constraints
- 1 <= A <= 100000000
- 1 <= B <= 100000000
- All input values are integer
- The relative error between 2^A and 10^B is more than 0.01

# Input
A B

# Output
If 2^A is larger than 10^B, print 'Yes'. Otherwise, print 'No'.

# Sample Input
10 3

# Sample Output
Yes

日本語の問題文は以下のようになります。

2 の A 乗が 10 の B 乗より大きいかを判定せよ。

この問題を解く最も単純な方法は、以下のように単純に if 文を使って比較を行うことです。Python で実装すると以下のようになります。

# 2.0 ** A は 2 の A 乗を意味し、10.0 ** B は 10 の B 乗を意味する
A, B = map(int, input().split())
if (2.0 ** A) > (10.0 ** B):
    print("Yes")
else:
    print("No")

しかし、この方法では残念ながら不正解です。たとえば、A として 1 億、B として 1000 万を入力した場合、エラーが起こってしまいます。この理由は、計算の途中で非常に大きい数が出てしまい、オーバーフローを起こすからです。

たとえば A が制約の最大値である 1 億の場合を考えましょう。このとき、2 の A 乗は約 3000 万桁の数になります。しかし Python の一般的な浮動小数点型では、2 の 300 乗程度までしか表現することができないため、値を正しく表すことができず、実行時エラーとなってしまいます。このような現象はオーバーフローといい、競プロで注意すべきポイントの 1 つになっています。

それでは、ChatGPT は正しくプログラムを書けるのでしょうか。以下のように対数関数を使うことで、見事オーバーフローを回避しました。

import math

def compare_exponents(A, B):
    # Calculate log(2) and log(10) using natural logarithms
    log2 = math.log(2)
    log10 = math.log(10)
    
    # Calculate A * log(2) and B * log(10)
    power_of_2 = A * log2
    power_of_10 = B * log10
    
    # Compare the two values
    if power_of_2 > power_of_10:
        print("Yes")
    else:
        print("No")

# Read input
A, B = map(int, input().strip().split())

# Perform the comparison
compare_exponents(A, B)

さらに注目すべき部分は、以下の写真に示す通り、ChatGPT がコメントで「普通に計算するとオーバーフローが起こるので、対数関数を使って計算します」と書いているところです。

ChatGPT は適当に正しいプログラムを書いたのではなく、よく注意してプログラムを書いていること、つまり注意力もあることがよく分かります。


第 9 問

いよいよ終盤になってきました。残る問題は 2 問です。

# Problem Statement
There is a rabbit on 1D coordinate x. Rabbit will perform the following N operation.

- 1st operation: Move to the position which is symmetrical with respect to coordinate A[1]
- 2nd operation: Move to the position which is symmetrical with respect to coordinate A[2]
- 3rd operation: Move to the position which is symmetrical with respect to coordinate A[3]
- :
- Nth operation: Move to the position which is symmetrical with respect to coordinate A[N]

Write a program that outputs the coordinate of the rabbit after finishing all operations for x=1, 2, ..., K.

# Constraints
- 1 <= N <= 200000
- 1 <= K <= 200000
- 1 <= A[i] <= 1000000 (1 <= i <= N)
- All input values are integer

# Input
N K
A[1] A[2] ... A[N]

# Output
Print K lines. In i-th line (1 <= i <= K), print the answer when x=i.

# Sample Input
3 2
5 3 9

# Sample Output
21
20

日本語の問題文は以下のようになります。

数直線上の座標 x にうさぎがいる。これから、うさぎは以下の N 回の操作を行う。

  • 1 回目の操作: 座標 A[1] に関して対称な場所に移動する。
  • 2 回目の操作: 座標 A[2] に関して対称な場所に移動する。
  • :
  • N 回目の操作: 座標 A[N] に関して対称な場所に移動する。

x=1, 2, ..., K について、すべての操作を終えた後のうさぎの座標を出力せよ。

この問題を解く方法を考えてみましょう。まず、座標 x にうさぎがいるとき、座標 target に関して対称な場所は 2*target-x となります。したがって、以下のようなプログラムを書くと、正しい答えが得られます。

# Input
N, K = map(int, input().split())
A = list(map(int, input().split()))

# Solve
for x in range(1, K+1):
    position = x
    for target in A:
        position = 2 * target - position
    print(position)

しかし、このプログラムは二重ループになっており、およそ N×K 回の計算が必要になります。本問題の制約では、20 万掛ける 20 万すなわち 400 億回程度の計算が必要になるため、実行に 1 分以上かかってしまいます。

そこで「答えが x に関して一次関数になっている」という性質を使うと、プログラムを高速化することができます。実際、入力例では

  • x=1 のときの答えが 21
  • x=2 のときの答えが 20
  • x=3 のときの答えが 19
  • x=4 のときの答えが 18

という感じで一次関数的に減っていきます。ただし、この性質に気付くのは難しく、おそらく AtCoder の常連参加者でも 25% 程度の人しか気づかないと思います。

それでは、ChatGPT はこの問題を解くことができるのでしょうか。まず、ChatGPT は以下のようなプログラムを提出しました。計算回数的には問題ないものの、残念ながら解法が間違っており入力例で正しい答えを出力しないため、元も子もありません。

def compute_final_positions(N, K, A):
    # Calculate the cumulative effect of transformations
    total_shift = 0
    for i in range(N):
        total_shift += 2 * A[i]

    # Prepare to output results for all initial positions from 1 to K
    results = []
    for x in range(1, K + 1):
        # Final position after all transformations
        final_position = total_shift - N * x
        results.append(final_position)
    
    return results

# Read input
import sys
input = sys.stdin.read
data = input().split()

N = int(data[0])
K = int(data[1])
A = list(map(int, data[2:]))

# Calculate and print the result
results = compute_final_positions(N, K, A)
for result in results:
    print(result)

そこで ChatGPT に対してプログラムを修正するよう伝えましたが、

  • 2 回目の提出:最初に書いたような「単純な実装のプログラム」を提出
  • 3 回目の提出:1 回目の提出とほぼ同じ「間違ったプログラム」を提出

となり、残念ながら最後までこの問題を解くことができませんでした。


第 10 問

いよいよ最終問題です。

# Problem Statement
There are N jewels in LLM Jewelry Shop. The jewels are numbered from 1 to N. The price of jewel i is P[i] dollars, and the weight of jewel i is W[i] grams.

Mr.LLM wants to buy 2 jewels, but he is happy if the total price is 100 dollars or less, and the total weight is 100 grams or more.

There are N(N-1)/2 possible ways of buying jewels, but how many of them are happy? Write a program that outputs the answer.

# Constraints
- 2 <= N <= 200000
- 1 <= P[i] <= 100 (1 <= i <= N)
- 1 <= W[i] <= 100 (1 <= i <= N)
- All input values are integer

# Input
N
P[1] W[1]
P[2] W[2]
:
P[N] W[N]

# Output
Print the answer.

# Sample Input
5
30 30
60 40
50 50
40 60
70 60

# Sample Output
2

日本語の問題文は以下のようになります。

N 個の宝石がある。i 個目の宝石の価格は P[i] ドルで重さは W[i] グラムである。2 つの宝石を選ぶ方法は N(N-1)/2 通りあるが、その中で価格の合計が 100 ドル以下かつ重さの合計が 100 ドル以上のものは何通りあるか。

まず考えられる方法は、2 つの宝石の選び方を全探索する方法です。しかし、N の最大値は 20 万であるため、最大 200000×199999÷2 = 約 200 億通りを計算する必要があります。このままでは実行に時間がかかり、不正解となってしまいます。そこで以下のテクニックを組み合わせると、プログラムを高速化することができます。

  • 価格と重さごとの個数を数えるという発想
  • P[i], W[i] の制約が 100 以下であることを使う発想
  • 累積和という典型テクニック
  • 重複して数え上げないようにプログラムを書く注意力

かなり難しい問題です。AtCoder の常連参加者の中でも 20% 程度の人しか解けないと思います。

それでは、ChatGPT はこの問題を解くことができるのでしょうか。最初に提出したプログラムは次のようなものでした。

def count_happy_pairs(N, jewels):
    # Sort jewels by price
    jewels.sort()
    
    count = 0
    
    # Use two pointers to find valid pairs
    for i in range(N):
        for j in range(i + 1, N):
            price_sum = jewels[i][0] + jewels[j][0]
            weight_sum = jewels[i][1] + jewels[j][1]
            
            if price_sum <= 100 and weight_sum >= 100:
                count += 1
    
    return count

# Read input
import sys
input = sys.stdin.read
data = input().split()

N = int(data[0])
jewels = []

for i in range(1, len(data), 2):
    P = int(data[i])
    W = int(data[i + 1])
    jewels.append((P, W))

# Calculate and print the result
print(count_happy_pairs(N, jewels))

このプログラムは正しく動作しますが、残念ながら先程説明した「実行に時間がかかる解法」を実装したものであるため、不正解となります。そこで 3 章のマニュアル通り、以下のフィードバックを返します。

Unfortunately, your solution judged as Time Limit Exceeded. Please improve time complexity of your solution.

すると ChatGPT は次のようなプログラムを返してきました。無駄な探索をしない工夫が追加されているため、プログラムの実行時間は少し速くなりましたが、本質的にはまだ二重ループであるため実行に 1 分以上かかることには変わりありません。

import bisect

def count_happy_pairs(N, jewels):
    # Sort jewels by price
    jewels.sort()
    
    count = 0
    
    # Iterate through each jewel
    for i in range(N):
        price_i = jewels[i][0]
        weight_i = jewels[i][1]
        
        # Find the maximum price that the second jewel can have
        max_price = 100 - price_i
        
        # Use binary search to find the range of possible second jewels
        j_start = bisect.bisect_right(jewels, (max_price, 300), i + 1)
        
        for j in range(i + 1, j_start):
            price_j = jewels[j][0]
            weight_j = jewels[j][1]
            
            if price_i + price_j <= 100 and weight_i + weight_j >= 100:
                count += 1
    
    return count

# Read input
import sys
input = sys.stdin.read
data = input().split()

N = int(data[0])
jewels = []

for i in range(1, len(data), 2):
    P = int(data[i])
    W = int(data[i + 1])
    jewels.append((P, W))

# Calculate and print the result
print(count_happy_pairs(N, jewels))

次は 3 回目、最後のチャンスです。マニュアル通りにフィードバックを送ります。果たして、ChatGPT は正しい解答を出すことができるのでしょうか。

import bisect

def count_happy_pairs(N, jewels):
    # Sort jewels by price
    jewels.sort()
    
    # Extract prices and weights
    prices = [jewel[0] for jewel in jewels]
    weights = [jewel[1] for jewel in jewels]
    
    count = 0
    
    # Iterate through each jewel
    for i in range(N):
        price_i = prices[i]
        weight_i = weights[i]
        
        # Find the maximum price that the second jewel can have
        max_price = 100 - price_i
        
        # Use binary search to find the range of possible second jewels
        j_start = bisect.bisect_right(prices, max_price, i + 1, N)
        
        for j in range(i + 1, j_start):
            price_j = prices[j]
            weight_j = weights[j]
            
            if price_i + price_j <= 100 and weight_i + weight_j >= 100:
                count += 1
    
    return count

# Read input
import sys
input = sys.stdin.read
data = input().split()

N = int(data[0])
jewels = []

for i in range(1, len(data), 2):
    P = int(data[i])
    W = int(data[i + 1])
    jewels.append((P, W))

# Calculate and print the result
print(count_happy_pairs(N, jewels))

下の写真に示すように、コメントには「累積和を使う」という正しい発想が出てきました。しかし、惜しくもこれを実装することができず、実行時間制限超過で終わりました。


5. 実験結果のまとめ

長くなりましたが、ChatGPT が以上の 10 問を解いた結果は以下のようになりました。

問題 結果 AtCoder のレーティング AtCoder で解く割合5
第 1 問 10 95%
第 2 問 30 85%
第 3 問 80 75%
第 4 問 130 70%
第 5 問 × 150 70%
第 6 問 300 50%
第 7 問 500 40%
第 8 問 500 40%
第 9 問 × 900 25%
第 10 問 × 1000 20%

したがって、人間の手助けが無い場合、ChatGPT の実力は茶色コーダー下位程度 (レーティング 400~599; AtCoder 常連参加者の上位 40~50% 程度) であると考えられます。6

ここで茶色レベルの参加者は、1 つ 1 つの基本的な解法テクニックは理解しているものの、複数の解法テクニックを上手く組み合わせられないという人が多いです。そのため、ChatGPT がさらに強くなるには、この壁を乗り越える必要があるのではないかと推測できます。

また、今回の結果は以下のように問題ジャンルによる差も見られました。7

  • 第 6~7 問のような「典型的な問題」については茶色下位以上の実力がある
  • 第 5 問のような「手を動かして解く問題」は苦手である

特に、AtCoder では主に以下の 2 種類のコンテストが開催されるのですが8、ChatGPT は同じ実力の参加者と比べて、前者が得意で後者が苦手ではないかと考えられます。

  • 典型的な問題が出題される AtCoder Beginner Contest (ABC)
  • 思考力を働かせなければ解けない AtCoder Regular Contest (ARC)

実際、ChatGPT が自身の実力を大きく上回る問題を解けた例として AtCoder Beginner Contest 345 D - Tiling が挙げられるのですが、この問題は典型的な全探索の問題であるため、傾向に当てはまっています。


実験結果に関する注意点

ここで、実験結果について注意しておかなければならないことが 2 つあります。1 つ目は、ChatGPT は今一番強い競プロ AI であるとは限らないということです。

たとえば 2023 年 11 月に Google が発表した「AlphaCode 2」という競プロ特化型の AI は、AtCoder では水色から青色程度 (上位 10% 以内) の実力を持つのではないかと言われています。

特化型 AI より汎用型 AI の方が当然不利であり、なおかつ AlphaCode は 100 万個のプログラムの候補をスパコンで生成したりするなど、潤沢な計算リソースを使用した AI であるため、無料の ChatGPT が負けるのは仕方ありません。

しかし、「世界で利用者数が最も多い AI のひとつである ChatGPT がこの程度の実力を持つ」というのが明らかになったことは、本実験において最も意義のあることだと思います。

2 つ目は、人間の手助けによって ChatGPT の実力が大幅に上がる可能性があるということです。たとえば人間が

  • 具体的にここがバグっている
  • 動的計画法を使えば解ける

などのアドバイスを与えると、これまで解けなかった問題が解ける可能性があります。例として第 5 問を振り返ってみましょう。第 5 問は最後無限ループに陥って不正解となりましたが、

next_valueA[i-1] を足し続けているせいで next_value % A[i-1] の値が絶対 0 にならなくてループから抜けない

ということを教えてあげた場合、解けた可能性がありました。また、惜しくも解けなかった第 10 問も、累積和を使うというアイデアを 1 回目の提出の前の時点で教えていれば、3 回のチャンスを使い切らずに解けた可能性がありました。

しかしながら、参加者の競プロの実力が高くなければ、的確なアドバイスを与えることはできません。そのため、実力の低い人が ChatGPT と人間の協力によって最上位の成績を取る、といったことは今の所現実的ではないと考えられます。


6. おわりに ~競プロの未来を見据えて~

最後に、茶色下位という結果はどう受け止めれば良いのでしょうか。人によって意見が分かれると思いますが、私の考えとしては、現時点ではそれほど大きな影響がないと思います。

例として就職・転職で AtCoder を使う場合を考えましょう。茶色のレーティングがあれば多少有利にはなりますが、急激に有利になり始めるのは一個上の緑色からです。そのため、ChatGPT を使って AtCoder に参加している人がまだ多くないことを考慮すると、大きな影響はありません。

ただし、筆者の考えとしては、もしプログラミング能力や思考力を上達させる目的で競技プログラミングに参加している場合、ChatGPT を使わずに問題を解くことをおすすめしています。なぜなら、自力でプログラムを書いた方が実力が上がりやすいと考えられるからです。

また、競プロを新たに始めた人が、ChatGPT に頼って参加している人に負けたなどの理由でモチベーションを落とす、といったことも考えられます9。しかし筆者としては、全く気にするべきではないと思います。なぜなら、もし全然プログラムが書けない人が ChatGPT に頼って実力以上の結果を取っても、本人にとっては何の力にもならないからです。

それでは、今後もし生成 AI がさらに強くなったら競プロはどうなるのでしょうか。

もちろん、競プロが続くかもしれないし、残念ながら終わってしまうかもしれません。どちらの可能性もあります。ですが将棋の場合、2017 年に人間のトップすら AI に破られたものの、まだ続いています。私の希望としては、将棋の例のように競プロが続いてほしいなと思っています。

最後になりますが、12,000 字超の長文を最後までお読みいただき誠にありがとうございました。


  1. https://openai.com/index/hello-gpt-4o/ 参照。
  2. 演算の種類によりますが、現代の PC では、毎秒 1~20 億回程度の演算ができることが多いです。
  3. インターネットの中には数万問の競プロの問題があるため、(特に典型問題に関しては) 内容がほぼ同じ問題が既に出題されている可能性があります。しかし少なくとも、問題設定はオリジナルになっています。
  4. アルゴリズムの教科書などに載っています。
  5. AtCoder Beginner Contest を想定。
  6. ただし、サンプル数が 10 と少ないため、この結果にはレーティング 400 程度の誤差を伴います。
  7. もちろん、10 問しか試していないので「有意差」と言えるほどの差はありません。
  8. その他にも AtCoder Grand Contest や AtCoder Heuristics Contest などがありますが、開催頻度は低いです。
  9. 現時点では ChatGPT を使っている人は高々数パーセントだと思っているので、それほど影響はないはずです。

ICPC 2023 世界大会参加記

1. はじめに

こんにちは、東京大学 4 年の米田 (E869120) です。この度は、4/14~19 にエジプトで開催されたプログラミングコンテストICPC 2023 世界大会」に、チーム Time Manipulators (E869120 + square1001 + QCFium) として参加し、世界 9 位で銅メダルを獲得しました。

そこで本記事では、ICPC について、ICPC に向けた練習について、そして本番の参加記について記したいと思います。長文になりますが、ぜひお読みいただけると幸いです。


2. ICPC について

まず、読者の中には ICPC を知らないという方もいると思うので、「ICPC が一体どういうものか」という話から始めましょう。

ICPC は、大学生・大学院生を対象としたプログラミングの大会です。ここで、プログラミングの大会にも様々なものがありますが、ICPCウェブサービスやアプリを作成するようなハッカソンのようなものとは異なり、制限時間内にプログラミングの問題をできるだけ多く解く大会です。いわゆる数学の試験のプログラミング版、と思っておくと分かりやすいと思います。

ICPC で出題される問題

それでは、ICPC ではどのような問題が出題されるのでしょうか。過去に出題された問題の例1として、以下の問題を考えてみましょう。

  • あるクラスの友達関係のデータが与えられる。
  • これから、友達関係でプレゼント交換を行う。プレゼント交換は、それぞれの友達についてプレゼントを渡す向きを決め、一方がもう一方にプレゼントを渡すという形式で行われる。
  • 不公平感をなくすため、各生徒がもらえるプレゼントの数の最大値と最小値の差をできるだけ小さくしたい。このような方法を 1 つ出力せよ。
  • たとえば友達関係が下図左側のようなものである場合、下図右側のように向きを決めれば差を 0 個にできる。

この問題を解く最も簡単な方法は、あり得る方法をすべて調べ上げることです。

たとえば上図の例の場合、プレゼントの向きの決め方としては 2 の 5 乗通り、すなわち 32 通りがあります。これらを全部調べて最も差が小さかったものを出力すれば、正しい答えを出すことができます。

しかし、この方法は友達関係の数が増えると上手くいきません。たとえば友達関係が 50 個ある場合、1000 兆通り以上の方法を調べ上げる必要があり、現代の PC を以てしても実行に数日以上かかってしまいます。そして、この問題では最大 3000 個の友達関係が与えられることがあるため、残念ながら正解することができません。

そこで「ある工夫した解法2」を使うと、3000 個の友達関係であっても 1 秒以内に答えを出せるようになります。このように ICPC では、プログラムを実装する力だけでなく、高速に答えを出せるような工夫した解法を考える能力 も重要になります。


大会の流れ

次に、ICPC がどのような流れで行われるかを説明します。まず、ICPC3 人 1 組のチーム戦/ただし同時にプログラムを実装できるのは 1 人 という形式で行われます。個人戦と異なり、戦略やチームワークも非常に重要です。たとえば実装者以外の 2 人をどう有効活用するかなどが重要になります。

また、日本の ICPC は一次予選・二次予選・世界大会の 3 つのステージからなり、それぞれ以下のような流れになっています。

大会 概要 競技時間 倍率
一次予選 オンラインで開催される 3 時間 300 チーム → 40 チーム
二次予選 横浜で開催される 5 時間 40 チーム → 2~4 チーム
世界大会 毎年開催国が異なる 5 時間 世界各地から 130 チームが参加

ここで世界大会では約 130 チームが参加しますが、そのうち上位 12 チームには以下のようにメダルと賞金が授与されます。ICPC は世界で最も権威のある大会の 1 つなので、ICPC でメダルをとることは多くの競技プログラマーの夢になっています。

大会 順位 チームの賞金
金メダル 1 位 約 250 万円
金メダル 2~4 位 約 120 万円
銀メダル 5~8 位 約 90 万円
銅メダル 9~12 位 約 50 万円

ICPC については理解できましたでしょうか。それではいよいよ、本編である ICPC 2023 世界大会の参加記に移りたいと思います。



3. ICPC 2023 参加記:世界大会までの過程

まずは世界大会に出場するまでどのような練習を行ったか、手短に記したいと思います。

2022 年 6 月

2022 年 6 月 15 日、当時東京大学 2 年の E869120、当時東京大学 2 年の square1001、当時東京大学 1 年の QCFium の 3 人でチームを組み、チーム「Time Manipulators」が結成しました。

2022 年 7 月

7 月上旬に一次予選が開催されるため、オンラインで一次予選の過去問を解くなどの練習を行いました。その結果、国内予選では 2 位で通過しました。

2022 年 11 月

12 月下旬に開催される二次予選に向けた練習を開始しました。チームで東大に集まって過去問を解いたり、戦略を立てたりしました。

ここで 1 つ記しておかなければならないことは、私達のチームにとって戦略とチームワークが非常に重要であるということです。私達のチームメンバーは全員、国内最大級のコンテストサイト AtCoder において国内 50 位程度の実力があるのですが、他の出場チームのうち、国内トップ 20 に入る実力者がいるチームが 4 チームほどあります。つまり、私達のチームが世界大会への切符をつかむには、実力の分を戦略とチームワークで補わなければなりません。そのため、戦略に関しては毎回の練習ごとに詳細な分析を行うなど、かなり力を入れて考えました。

2022 年 12 月

そして 12 月 28 日、二次予選を迎えました。10 日前にチームメンバーの 1 人がコロナに感染したり、前日に別のメンバーが熱を出したりするなどのトラブルが起こりましたが、何とか 2 位で世界大会進出を果たしました。

2023 年 2~7 月

当時、世界大会は 2023 年 11 月に予定されていたため、この時期はあまり多くの練習を行わず、「高校数学の基礎が 150 分でわかる本」の執筆作業に注力していました。7 月 26 日に発売され、2 万部以上売れました。

2023 年 9~10 月

世界大会の 2 か月前になり、いよいよ世界大会に向けた練習を始めました。1 日平均 5 時間の個人練習に加え、チームで東大に集まって海外の ICPC 予選の過去問を解くなどの練習を行いました。その結果、世界大会の 3 週間前の時点ではいよいよ完成度が上がり、メダルを狙える予感がしてきました。

ところが、10 月 28 日、戦争の影響で ICPC 世界大会が無期限で延期されるという一通のメールが来ました。あと 4 日大学に登校すれば世界大会というタイミングでした。これまでの努力が無駄になってしまうかもしれないという絶望感と、戦争は絶対に許されないという強い思いを同時に感じました。

2023 年 11~12 月

ICPC が延期され、最終的には中止も懸念されるような状況であったため、ICPC の練習を行えるような状況ではありませんでした。

2024 年 1 月

あれから 3 ヶ月が経った 1 月 16 日のことです。ICPC の開催可否に関する連絡が日本時間の 1/20 午前中に来るという連絡がありました。そして迎えた 1 月 20 日、午前 8 時に起きてメールを確認しました。まだ来ていません。9 時にももう 1 回メールを確認しました。まだ来ていません。その後、3 分おきくらいにメールを確認しました。10 時になっても来ません。中止になるのではないか、あるいは日程が他の重要な学業イベントと重なって出場できないのではないかと不安が高まります。しかし 10 時 16 分、ICPC 世界大会がエジプトで 4/14~19 に開催されるというメールが送られました。この時は本当に嬉しかったです。

2024 年 2 月下旬 (50 日前)

大学の期末試験が終わり、いよいよ本当の世界大会に向けた練習が始まりました。最初にやったことは、2/17~25 に開催された Osijek Programming Camp に参加したことでした。チームで東大に集まり、7 日間練習を行いました。

最初の方はあまり良い結果が出ず、10 月との落差に絶望しました。9 月 10 月の調整がたまたま上手くいっただけで、今回はチームの完成度を上げられないのではないかと不安を感じました。しかし最終日には 7 日間で最高の結果を出すことができました。

その後、チームとしての目標を決めました。チームとしては、コンテストで出来るだけ高い成績を残すことを第一の目標とするが、できれば 12 位以内のメダル獲得を目指す という目標を設定することになりました。3

2024 年 3 月上旬 (40 日前)

その後、10 月の練習と同様、チームで東大に集まって海外の ICPC の予選を解くなどの練習を行いました。チーム練習は週 2 回程度行い、練習がない日は 1 日 10 時間程度の個人練習を行いました。当時、パソコンが同時に 1 台しかない影響で実装速度がボトルネックになっていたため、実装力を上げる練習を中心に行いました。

また、戦略に関してもこの時期に深く考えました。2022 年 12 月の二次予選よりもさらに上のレベルのものを目指して考えました。戦略は序盤・中盤・終盤の 3 つの段階に分けて考え、どういう条件だったらこのような戦略を取る、などの場合分けを含めて考えました。戦略に関しては機密情報なのですべてを教えることはできませんが、一部の例として、以下のような戦略があります。

序盤戦略の例

  • 難易度順に並んでいない問題が 12 問あるとして、普通は最初 1 人 4 問ずつに担当を分けるところ、英語が読むのが早い square1001 が 6 問、その他のメンバーが 3 問を担当するように分ける。
  • その後、square1001 が最初の 5 分で 6 問の問題ジャンルを把握し、その中で他の 2 人が得意そうな 2~3 問を該当者に渡す。

終盤戦略の例

  • 終盤は、3 対 3 戦略・3 対 2 戦略 A・3 対 2 戦略 B・3 対 1 戦略のいずれかを適用する。
  • 詳しくは書かないが、どれにするかは残り時間や順位表等に応じてほぼ機械的に決める。
    • 3 対 3 戦略は、1 人が 1 問に取り掛かり、追加で 3 問解くことを目指す戦略である。
    • 3 対 2 戦略 A は、1 人が 1 問、残り 2 人が別の 1 問を協力して解く戦略である。あるいは、1 人が 1 問を実装して、残り 2 人が別の問題の解法を考える戦略である。
    • 3 対 2 戦略 B は、2 人が 2 問に取り掛かり、残った 1 人が他の 2 人のヘルプに回るという戦略である。
    • 3 対 1 戦略は、3 人で協力して 1 問を考えるという戦略である。ほぼ適用されない。

2024 年 3 月中旬 (30 日前)

前述の戦略を踏まえてチーム練習を行った結果、かなり良い成績を残すことができました。この段階でようやく、もしかしたらメダルが狙えるのではないかというレベルに達しました。

2024 年 3 月下旬 (20 日前)

この時期は別のイベントとして日本情報オリンピックの春季トレーニングが開催されており、チームメンバー 3 人全員がチューターを務めていたため、チーム練習は行いませんでした。

また、イベント後もチームメンバーの 1 人が新型コロナウイルスの濃厚接触者になったりしたため、チームで集まった練習ができない期間が 2 週間ほど続きました。

本番 10 日前

4 月に入り、いよいよ本番が間近になったため、ICPC 世界大会の過去問を解き始めることになりました。4/3 には 2018 年の過去問、4/5 には 2017 年の過去問を解きました。いずれもメダルを取れそうな結果に終わりました。しかし、コンテスト中の緊張など、これまでの練習では無かった課題も明らかになり、様々な対策を考えました。

本番 7 日前

1 週間前からはタイピング練習を行いました。競技本番は普段使っている日本語配列ではなく US 配列を使う必要があるため、それに慣れるための練習を行いました。最初は (, ), [, ] などの特殊な文字の位置に慣れるのに苦戦し、毎分 200 打鍵程度しか出ませんでした。しかし、

  • ダイクストラ法のプログラム (1000 バイト程度) を 50 回書く
  • セグメント木のプログラム (1500 バイト程度) を 10 回書く
  • 典型問題 20 問のプログラム (書くだけで 1.5 時間かかる) の実装を 4 周する

といった鬼のような練習を行った結果、3 日後には毎分 360 打鍵程度と、日本語キーボードの 90% 以上の速度が出るようになりました。

本番 5 日前

同時並行で、コンテスト本番で使うライブラリ資料の作成も行いました。ここでライブラリ資料とは、いわゆるカンニングペーパーのようなもので、典型テクニックを実装したプログラムを書くチームが多いです。

ライブラリ資料を作る上で難しいことは、チームで A4 用紙 25 枚という制限があることです。そのため、どれを書いてどれを書かないかを選ぶ必要があります。私達のチームでは 2 時間ほどのミーティングを行ってどれを書くかを決め、その後各自で準備を行いました。

本番 3 日前

4 月 10 日、世界大会前最後の大学の授業がありました。12 時に授業が終わり、その後他の同級生に ICPC について話した後、「これが日本の底力なんだ」ということを世界に見せるぞと誓って 13 時に帰りました。

本番前々日

最後の個人練習を行いました。

本番前日

最後のチーム練習を行い、2019 年大会の過去問を解きました。そして 17 時にチーム練習が終わり、いよいよ本番を残すのみとなりました。



4: ICPC 2023 参加記:コンテスト本番

それでは最後に、4/14~19 に開催された ICPC 2023 エジプト大会の参加記を記したいと思います。

4/13~14

世界大会への最初のステップは、エジプトのルクソールまで移動することです。私達のチームは 4/13 15 時頃に成田空港に到着し、17 時半発の飛行機に乗りました。アブダビ、カイロを経由し、トランジット含めて 27 時間のフライトの末、現地時間の 4/14 14 時頃に目的地のルクソールに到着しました。

4/15

この日は午前中に観光があり、午後に開会式がありました。

観光では Karnak Temple に行きました。エジプトだから当然ですが、一面茶色ばかりでびっくりしました。なお、Karnak Temple だけでなく、エジプトの他の建物も茶色系の建物しかほぼありません。

続いて、開会式ではルクソール知事を含む偉い人が次々と出てスピーチが行われたり、ICPC に参加するチームが読み上げられたりしました。

4/16

この日は ICPC Challenge という、競技本番とは別のコンテストがありました。ICPC Challenge は、1 問の数理最適化の問題が出題されるので、3 時間で出来るだけ良いスコアを出してくださいという形式のコンテストです。上位 24 チームにはスポンサー企業の Huawei からの賞品が授与され、特に上位 8 チームに入ると金賞のパソコンがもらえます。

さて、コンテストはどんな感じだったのでしょうか。私達のチームは、最初の 30 分は最上位を走っていました。しかし、その後上手くいく改善が思いつかず、あまりスコアが伸びずに 2 時間時点で賞品圏内から脱落しました。

そこで 2 時間半が経過した辺りで、あることに気付きます。ICPC Challenge では数十個の入力データのの合計点で順位が決まるのですが、過去の大会では「1 個だけ特殊なデータが入っていて、このケースに対して場合分けをすることで順位が一気に伸びる」ということが何回かありました。今回ももしかしたらそれかもしれない、と思いケースを分析してみたところ、まさに 1 個スコアが伸ばせるケースが見つかりました。

残り 10 分、急いで場合分けのプログラムを書きます。残り 5 分、プログラムのバグを探します。そして残り 3 分、提出すると順位が 30 位から 5 位に上がり、金賞圏内に入りました!

このようにして、私達のチームは Huawei Matebook というパソコンをもらうことができました。しかしもう 1 つ気付いたことがありました。今回は残り 10 分で改善が思いついて金賞圏内に入ったが、もし 10 分遅ければ銅賞にすら入っていなかった。つまりコンテストは運にかなり依存するということに気付かされたのです。そこで ICPC 本番では、「日本代表としての責任とかプレッシャーとかをあまり考えず、最後は運で決まると考えることにしよう」と思いました。

4/17

コンテスト前日であるこの日は、実機演習がありました。実機演習は、コンテスト本番のジャッジシステムや、提出の方法などに慣れるためのコンテストです。私達のチームでは、最初誰がパソコンにログインするか、パソコンの位置をどこにするかなどの細かいことを相談し、本番前の最後の確認を行いました。

4/18

いよいよコンテスト当日がやってきました。以下、時系列で参加記を書いていきます。

[8:00]

チームメンバーの全員が起床し、朝食を食べました。

[10:30]

コンテスト控室に入場し、このタイミングでスマホや時計が回収されました。控室の前には開始までの残り時間が表示された画面が映っており、いよいよ始まるのだと感じました。

[11:20]

競技開始 30 分前、最初のチームがコンテスト会場への移動を始めました。私達のチームは、アジア地区予選は感染症等でギリギリの状態での出場となり、世界大会も一時は延期された。このような経験があったので、最後の最後まで自分が世界大会の競技に出場できるということを信じられませんでした。しかしこの段階で「本当に始まるんだ」と確信し、涙が出ました。10 分ほど涙が止まりませんでした。

[11:30]

その後私達のチームもコンテスト会場に入場しました。そして覚悟を決めました。全力を尽くす。悔いのない試合にする。そして最後まであきらめない。

4/18 コンテスト

[11:50 / 0:00 経過]

そしていよいよコンテストが始まりました。問題は A 問題から K 問題までの 11 問。戦略通り、最初は自分が 2 問、QCFium が 3 問、square1001 が 6 問を担当し、square1001 が「他の人が得意」と判断した 2 問を該当者に渡しました。

その後、square1001 が簡単枠の I 問題の解法を思いついたため、実装を開始し、開始 19 分で正解しました。今度は自分が簡単枠の A 問題を実装し、開始 26 分で正解しました。その後、QCFium が G 問題の解法を思いついたため実装し、開始 56 分で正解しました。この時点では 4 位で順調な展開でした。

[13:00 / 1:10 経過]

しかし、今度は square1001 が D 問題、QCFium が H 問題を実装したものの、両方原因不明のバグに見舞われました (両方バグらせる人が非常に多い問題)。しかも順位表によると、現時点でこれまで解いた 3 問と実装中の 2 問以外は 1 人も解かれていません。そこで私は他の人の手助けをしながら、解かれてない中でも簡単だと思った C 問題と K 問題の解法を考えました。

[14:10 / 2:30 経過]

途中メダル圏外の 26 位まで落ちましたが、2 時間が経過した時点で両方のバグがほぼ解決し、2 時間 20 分までに簡単な 5 問をすべて正解することが出来ました。その間に自分は K 問題の合っている確率 80% くらいの解法と、C 問題の途中のアイデアを思いつくことができていました。

この時点で、順位表では C, F, K の 3 問が解かれており、自分のチームもこの 3 問を解けばメダルは取れるだろうと判断し、各メンバーの得意不得意を考慮して以下の戦略を取ることに決めました。

  • E869120 が C 問題の途中のアイデアを QCFium に教えた後、K 問題を実装する。
  • QCFium が C 問題の考察を行い、
  • square1001 が F 問題の考察と実装を行う。

しかし、現在 14 位でまだメダル圏外、しかも実装できる状態の人は僕しかいない。自分が流れを変えるしかないという状況でした。練習の成果をここで出すしかないと思い、実装を始めました。

[14:40 / 2:50 経過]

20 分の実装とデバッグの末、入力データのサンプルで答えが合いました。この時点で解法が正しいことを確信しました。しかし、まだ微妙な高速化が必要です。既に QCFium が C 問題の解法を分かっていたため、実装権を QCFium に渡し、高速化のアイデアを考えました。

[14:47 / 2:57 経過]

数分考えると、高速化の方法が見えたので必死に実装をしました。そして 3 時間 2 分、ついに提出をし、Accepted (正解) と表示されました。順位が 20 位から 7 位に上がり、流れが変わりました。

[16:10 / 4:20 経過]

その後、square1001 が K 問題を実装しました。この問題は 350 行弱の実装を必要とし、バグらせる人も非常に多い問題です。提出数を見れば、正解 1 に対して不正解 9 と、かなり不正解が多い問題でした。しかし、彼はこれを 40 分で実装・デバッグを終わらせるという超人的な技を成し遂げ、3 時間 53 分で正解しました。その後、QCFium も C 問題を正解し、4 時間 20 分で 8 問正解となりました。この時点で勝率 80% の優勢の状況になりました。

[16:20 / 4:30 経過]

しかし、どうにかメダルを確実にしたいと思い、あと 1 問解くことを目指しました。3 章で述べた「3 対 1 戦略」を適用し、残り 3 問の中で最も簡単な B 問題を取り掛かりました。3 対 1 戦略は、練習でも適用率 10% 程度と珍しい戦略であるものの、最も熱いと言われていた戦略です。

この問題は、入力が実質的には N ひとつしかなく、スコアが最大になるような出力をしてください、という形式の問題です。3 人全員で協力して考えます。すると終了 25 分前に square1001 がそれっぽい解法を思いつきます。その後、最初に解法を思いついた square1001 が実装を始め、他の 2 人はより高いスコアを出せないかを考察します。

[16:40 / 4:50 経過]

実装を終え、提出すると不正解が出ます。つまり、より高いスコアが出せるということです。5 分前、3 人全員で必死に考察を進め、N = 6 でスコアを上げる方法が分かりました。不正解。2 分前、N = 10 でスコアを上げる方法が分かりました。それでも不正解。最後まであきらめずに考えましたが、ここでコンテストが終わり、8 問正解で終わりました。


さて、コンテスト終了後も開始 4 時間時点での順位表しか見られないため、自分たちのチームはメダルを獲得したか分からない状況でした。15 位以内に入っている自信はあったものの、12 位に入っている確率は 80% 程度、と思っていました。

そうこうしているうちに、20 時に結果発表が始まりました。成績の低いチームから順位が発表されていきます。60 位、50 位、40 位、30 位と発表されていき、緊張の時間が続きます。しかし 22 時頃、ようやく画面に「Medalists - The University of Tokyo」と表示され、自分がメダルを獲得したことが明らかになりました。この時は本当に嬉しく、国内予選から 2 年間このチームでやってきて良かったと思いました。

そして 4 月 20 日に帰国し、日本に銅メダルを持って帰ることが出来ました。めでたしめでたし。



5. おわりに

ICPC 2023 世界大会への参加にあたっては、たくさんの方の応援がありました。まずは応援してくださった方々に感謝申し上げます。また、一次予選・二次予選・運営に携わってくださった皆さんに感謝申し上げます。これが無ければ私達のチームが世界大会に出場することはなく、メダルを取ることもありませんでした。

最後に、チーム Time Manipulators のメンバーに感謝申し上げます。本当にありがとうございました。




  1. ICPC 2016 プレゼント交換会 の設定を少し変えたバージョン。
  2. かなり複雑なので詳細は略します。
  3. ここで、目標がメダルだけではない理由は、コンテスト本番のメンタルや心構えに影響するからです。

「高校数学の基礎が150分でわかる本」にかけた思い

1. はじめに

こんにちは、東京大学 3 年の米田です。この度は、ダイヤモンド社から『高校数学の基礎が 150 分でわかる本』という書籍を出版させていただくことになりました。高校数学の基礎を図解で超わかりやすく説明した本です。

本稿では、この本を書いたきっかけや、この本に懸けた思いについて記したいと思います。

なお、本の内容紹介につきましては、以前こちらの記事に書かせていただいたので、まだ読んでいない方はぜひお読みください。

 

2. 前提:数学はあらゆる人が身に付けてほしい

執筆のきっかけについて書かせていただく前に、まずは数学に対する僕の考えを述べておきます。僕は、高校数学の基礎くらいのレベルの知識は、あらゆる日本人が身に付けるべきだと思っています。

この理由としては、仕事の幅が広がる、論理的思考力が身につくなどたくさんあるので、詳しくは発売日前後にブログにまとめようかと思慮しています。しかしその中でも代表的な理由の一つとしては、生活していくうえで便利であることが挙げられます。

以下に例を 3 つ示します。「どんな場面で数学が使えるのか」のイメージだけつかめれば大丈夫です。*1

 

例1:宝くじ (本の p.85 の類題)

ある宝くじを 1 枚買うのに 300 円かかります。当たりの賞金と確率が以下のとおりであるとき、宝くじを買うのは得ですか。損ですか。

  • 1 等:賞金 1 万円/確率 1%
  • 2 等:賞金 300 円/確率 20%
  • 3 等:賞金 0 円 (ハズレ)/確率 79%

もし高校 1 年で習う「期待値」の計算方法を知っていれば、答えがわかります。

期待値を計算すると、平均して (10000×0.01) + (300×0.2) + (0×0.79) = 160 円の賞金しかもらえないとわかるので、この宝くじを買うのは損であると考えられます。

 

例2:データ分析 (本の p.96 の類題)

A 君と B 君の月別営業成績は以下の通りです。A 君と B 君のうちどちらが、安定した成績を出せていると考えられますか。*2

  1月 2月 3月 4月 5月
A君 350万円 400万円 600万円 100万円 550万円
B君 300万円 250万円 750万円 500万円 200万円

もし高校 1 年で習う「標準偏差」の計算方法を知っていれば、答えがわかります。

計算過程は省略しますが、A 君の成績の標準偏差は約 176 万円、B 君の成績の標準偏差は約 202 万円であるため、A 君の方が安定しているといえます。*3

 

例3:投資 (本の p.55)

あなたは今 1000 万円を持っていて、上手く投資をすると年率 10%、つまり 1 年に 1.1 倍の割合で所持金を増やすことができます。このとき所持金は、

  • 1 年後には 1000×1.1=1100 万円
  • 2 年後には 1100×1.1=1210 万円
  • 3 年後には 1210×1.1=1331 万円

と増えていきますが、果たして所持金が 10 倍の 1 億円になるのは何年後でしょうか。

もし高校 2 年で習う「対数 log」を知っていれば、答えがわかります。

答えは「1.1 を何乗すれば 10 になるか、つまり  \displaystyle \log_{1.1}10 」であり、これを電卓で計算すると約 24.15 なので、25 年後には 1 億円を超えている、ということが分かります。

このように、数学を学ぶメリットはたくさんあるため、僕は「高校数学の基礎」くらいの知識は、すべての日本人が身に付けるべきだとすら思っています。

 

 

3. 本書を執筆したきっかけ*4

しかし、数学に苦手意識がある人でも知識を身に付けられる本は、それほど多くありません。実際、僕がいくつかの本を読んだところ、国内で出版されている数学の本の多く(体感 9 割)は、残念ながら以下のいずれかに当てはまっています。

  • 難しくてかなりの読者が脱落してしまう
  • イラストや会話などの雰囲気でわかった気にはなるが結局身に付かない

そこで僕は、もしどちらにも当てはまらない最強にわかりやすい本を出版できれば、世の中の役に立てるのではないかと思いました。これが執筆を決めたきっかけです。

 

4. どう「わかりやすい本」を目指したか

ところが、前述のどちらにも当てはまらない、最強にわかりやすい本を書くのは全く簡単なことではありません。そこで拙著『高校数学の基礎が 150 分でわかる本』では、最強にわかりやすい本に仕上げるため、以下の 4 つの工夫を施しました。

  • 250 個以上のフルカラーの図
  • 数学が役立つたくさんの実用例
  • 中学レベルの知識から丁寧に解説
  • わかった気で終わらせない「穴埋め式演習問題」

なお、フルカラーの図については以下の紙面をご覧ください。図なしの見開きページがほぼ存在しないため、数学アレルギーの人でも抵抗感なく読み進めることができます。はじめて数学を学ぶ方、学び直しの方の 1 冊目の本として最適です。

 

5. おわりに - 本書はなぜ 200 ページか

最後に、本書を執筆する上で迷ったことを 1 つ記したいと思います。これはページ数をどれくらいにするかです。実際、本書の企画時には、大きく分けて以下の 2 つの選択肢がありました。

  • 500 ページで、高校数学のほぼ全部をわかりやすく解説する(語りかける高校数学などが例)
  • 200 ページで、高校数学の基礎に絞ってわかりやすく解説する

しかし長考の末、僕は後者の方を選ぶことにしました。なぜなら、本が長すぎると読む上での抵抗感が出てしまい、本来のターゲット層に届かなくなるのではないかと思ったからです。

ですので、本書は大体 3 時間程度で読めるようになっています。忙しいビジネスパーソンでも気軽に読めますので、興味のある方はぜひご購入ください。


本記事は以上です。最後までお読みいただきありがとうございました。大学の期末試験が迫る中、90 分で書いた乱文ですので、文章のクオリティはご容赦いただけると幸いです。

*1:問題の答えを理解する必要はありません

*2:なお、営業成績の平均は、A 君と B 君両方 400 万円です

*3:もちろん「有意差」といえるほどの大きな差はないですが、これは大学レベルの話なので本稿では考えないことにします。

*4:正確には、ダイヤモンド社からの執筆オファーを受けた理由と言うのが正しいです。