はじめに
ルールやスコアの計算方法などは結果編に記載しています。
結果編
問題解説（C~E）
一応私も解いて解説しているのでリンクしておきます
結果
下記コンテストの問題をルールに基づいて解かせた結果です。
各問題の所感
問題A
Difficulty: 20
Gemini 1.5 Flashは間違えていました。他の2つのコンテストでも問題Aを間違えたLLMはなかったので、うーん。
ただし、試行回数が少ないので多少はしょうがないのかもしれない。
ここで気が付いたのですが、言語を指定していないとどのLLMも大体Pythonで返ってきます。
Gemini 1.5 Flash：挑戦2の出力
abc344a_geminiflash_2.py
s = input()
s = s.replace(s[s.find('|') + 1:s.rfind('|') + 1], '')
print(s)
問題B
Difficulty: 47
単純に入力された文字列を逆順にするだけなので、どのLLMも間違えないと予想したが意外と間違えるLLMが多かったです。間違え方はどのLLMも大体同じで、下記のようにappendする前にbreakをしてしまっていました。
コーディング能力の欠如というよりは問題文をうまく読み解けてないような印象を受けます。
Gemini 1.5 Flash：挑戦3の出力
abc344b_geminiflash_3.py
a = []
while True:
n = int(input())
if n == 0:
break
a.append(n)
for i in range(len(a)-1, -1, -1):
print(a[i])
問題C
Difficulty: 204
基本的に計算量をうまく見積もれずTLE（制限時間オーバー）してしまっているものが多かったです。
正答に関してですが、LLMは数学的な処理が苦手だと思っているので単純に足したものをsetにいれて探索するのだと予想していましたが、$A_i + B_i = X_j - C_i$などを駆使して解いていました。
GPT-4o：挑戦2の出力
abc344c_gpt4o_2.py
N = int(input())
A = list(map(int, input().split()))
M = int(input())
B = list(map(int, input().split()))
L = int(input())
C = list(map(int, input().split()))
Q = int(input())
X = list(map(int, input().split()))
from itertools import product
possible_sums = set()
# Generate all possible sums of A and B
for a, b in product(A, B):
possible_sums.add(a + b)
output = []
# For each query, check if there exists a sum such that sum + c = x
for x in X:
found = False
for c in C:
if (x - c) in possible_sums:
found = True
break
if found:
output.append("Yes")
else:
output.append("No")
for result in output:
print(result)
問題D
Difficulty: 854
動的計画法（DP）を使って解く問題です。もちろんDPを知っているだけではなく、状態がどのように遷移していくか、そもそもDPで解けそうかということがわかっていなければ解けません。そのうえで、どのLLMもDPを使って解けそうということはわかっているようでした。
驚くべきはGPTsで両者ともに正答しています。特にGPT-4 Turboは2つも通していました。
GPT-4 Turbo：挑戦2の出力
abc344d_gpt4turbo_2.py
def main():
import sys
input = sys.stdin.read
data = input().split()
T = data[0]
N = int(data[1])
# 枝ごとに保持
bags = []
index = 2
for _ in range(N):
Ai = int(data[index])
Si = data[index+1:index+1+Ai]
bags.append(Si)
index += (1 + Ai)
# dp[i] は S を T の最初の i 文字と一致させるための最小の費用
# 初期値は、まだ何も取れないで inf
inf = float('inf')
dp = [inf] * (len(T) + 1)
dp[0] = 0 # 空文字列はコスト0で一致している
# 各袋について検証
for strings in bags:
new_dp = dp[:] # 現状の dp をコピー
for s in strings:
s_len = len(s)
# dp の全範囲を更新できるか確認
for i in range(len(T) + 1):
# i から s を末尾に追加して一致する部分までをチェック
# すなわち、T の i から i+s_len が s と一致するなら、dp[i+s_len] 更新
if i + s_len <= len(T) and T[i:i+s_len] == s:
if dp[i] != inf: # コストが定義されている場合のみ
new_dp[i+s_len] = min(new_dp[i+s_len], dp[i]+1)
dp = new_dp
# Tに完全に一致させる最小コスト取得
result = dp[len(T)]
if result == inf:
print(-1)
else:
print(result)
main()
問題E
Difficulty: 973
GPT-4 Turboくんがやってくれました。双方向リストを用いての解法です。ただ、かなり冗長か？とも思った。
GPT-4 Turbo：挑戦2の出力
abc344e_gpt4turbo_2.py
import sys
input = sys.stdin.read
from collections import defaultdict
data = input().split()
index = 0
# Skipping first two lines which contain N and the initial list A
N = int(data[index])
index += 1
A = list(map(int, data[index:index+N]))
index += N
# Mappings from value to position and from position to value
value_to_index = {}
index_to_value = {}
for i in range(N):
value_to_index[A[i]] = i
index_to_value[i] = A[i]
# Q and queries
Q = int(data[index])
index += 1
# List to maintain order using a doubly-linked list approach
# We use this instead of inserting directly into list because it's more efficient
next_elem = {}
prev_elem = {}
# setting up the doubly-linked list
for i in range(N-1):
next_elem[A[i]] = A[i+1]
prev_elem[A[i+1]] = A[i]
if N > 1:
head = A[0]
tail = A[-1]
else:
head = tail = A[0]
# Setting up a set for quick existence check
elements = set(A)
for _ in range(Q):
query = data[index]
if query == '1':
_, x, y = map(int, data[index:index+3])
index += 3
# Assumption: x is in A, x and y are integers
if x in elements:
elements.add(y)
if x == tail:
tail = y
else:
original_next = next_elem[x]
next_elem[y] = original_next
prev_elem[original_next] = y
next_elem[x] = y
prev_elem[y] = x
elif query == '2':
_, x = map(int, data[index:index+2])
index += 2
# Assumption: x is in A
if x in elements:
elements.remove(x)
if x == head and x == tail:
head = tail = None
elif x == head:
head = next_elem[x]
del prev_elem[head]
elif x == tail:
tail = prev_elem[x]
del next_elem[tail]
else:
prv = prev_elem[x]
nxt = next_elem[x]
next_elem[prv] = nxt
prev_elem[nxt] = prv
# Cleanup to avoid memory leaks
if x in next_elem:
del next_elem[x]
if x in prev_elem:
del prev_elem[x]
# reconstruct the list from the linked elements
result = []
current = head
while current is not None:
result.append(current)
current = next_elem.get(current, None)
print(" ".join(map(str, result)))
問題F以降
Difficulty: 1922
Difficulty: 3032
ここからは私も解けていないです。問題Fでは、Geminiたちが想定解であるDPを使って解くことを思いついていたようです。
問題F、Gemini 1.5 Flash：挑戦2の出力
abc344f_geminiflash_2.py
n = int(input())
p = [list(map(int, input().split())) for _ in range(n)]
r = [list(map(int, input().split())) for _ in range(n)]
d = [list(map(int, input().split())) for _ in range(n - 1)]
dp = [[float('inf')] * n for _ in range(n)]
dp[0][0] = 0
for i in range(n):
for j in range(n):
if i + 1 < n and dp[i][j] + d[i][j] < dp[i + 1][j]:
dp[i + 1][j] = dp[i][j] + d[i][j]
if j + 1 < n and dp[i][j] + r[i][j] < dp[i][j + 1]:
dp[i][j + 1] = dp[i][j] + r[i][j]
dp[i][j] += p[i][j]
print(dp[n - 1][n - 1])
まとめ
- GPT-4 Turbo強い
- 解答方針を決めさせるという使い方はかなり有効そう
- 問題Bは入力を逆順に表示させるという単純なものだが、Gemini 1.5 Flash、Claude 3 Opusは誤答が多い
- 日本語、もしくは文脈把握力がひくい？