LLMに競プロの問題解かせてみた【ABC346】

はじめに

ルールやスコアの計算方法などは結果編に記載しています。

結果編

問題解説（A~E）

一応私も解いて解説しているのでリンクしておきます

結果

下記コンテストの問題をルールに基づいて解かせた結果です。

各問題の所感

問題A

Diffiuculty: 10

GPTsは入力の高速化を試みていました。readlineはたまに使うのですが、readはよくわからないです。たぶんinputより早いと思います。（間違ってたらすいません）

GPT-4 Turbo：挑戦1の出力

abc346a_gpt4turbo_1.py

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    A = list(map(int, data[1:N+1]))
    B = [A[i] * A[i + 1] for i in range(N - 1)]
    print(" ".join(map(str, B)))

if __name__ == "__main__":
    main()

問題B

Diffiuculty: 251

Cより難しいB問題です。ここでもGPT-4 Turboのみの正答でした。Claude 3 Opusの出力とGeminisはほとんど同じ出力で間違えているのに対し、GPTsはよく考えて間違えている印象でした。
実際にGPT-4oとClaudeの出力を比較してみます。

GPT-4o：挑戦1の出力

abc346b_gpt4o_1.py

# 定数: パターンの長さ
PATTERN = "wbwbwwbwbwbw"

# 入力を受け取る
W, B = map(int, input().split())

# 検索範囲の上限
max_length = 12 * 2

# 連続チェック用の長さを指定
target_length = W + B

# 作る文字列の長さを指定(パターンを2回繰り返せば十分)
extended_pattern = (PATTERN * ((max_length // len(PATTERN)) + 1))

# 探索と出力
for i in range(len(extended_pattern) - target_length + 1):
    sub_str = extended_pattern[i:i + target_length]
    if sub_str.count('w') == W and sub_str.count('b') == B:
        print("Yes")
        break
else:
    print("No")

Claude 3 Opus：挑戦1の出力

abc346b_claude3opus_1.py

W, B = map(int, input().split())

if W == 0:
    print("Yes" if B <= 1 else "No")
elif B == 0:
    print("Yes" if W <= 2 else "No")
else:
    print("Yes" if W <= 2*B+2 and B <= 2*W else "No")

問題C

Diffiuculty: 179

Claude 3 Opusが全問正答でした！また、Claudeの正答は別解も含めていていたり、ほとんどの回答がPythonの中、C++で書いていました。（C++はGeminiもたまに書く）

Claude 3 Opus：挑戦1の出力

abc346c_claude3opus_1.cpp

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, K;
    cin >> N >> K;
    vector<bool> appear(K + 1, false);
    
    for (int i = 0; i < N; i++) {
        int A;
        cin >> A;
        if (A <= K) {
            appear[A] = true;
        }
    }
    
    long long sum = 0;
    for (int i = 1; i <= K; i++) {
        if (!appear[i]) {
            sum += i;
        }
    }
    
    cout << sum << endl;
    
    return 0;
}

Claude 3 Opus：挑戦2の出力

abc346c_claude3opus_2.py

N, K = map(int, input().split())
A = set(map(int, input().split()))

ans = (1 + K) * K // 2 - sum(i for i in A if 1 <= i <= K)
print(ans)

問題D

Diffiuculty: 845

全滅でした。
やはり動的計画法（DP）などで解けるということを理解しているようでしたが、状態遷移をうまくできていないようです。Gemini 1,5

Claude 3 Opus：挑戦3の出力

abc346d_claude3opus_3.cpp

#include <iostream>
#include <vector>
#include <string>
#include <climits>

using namespace std;

int main() {
    int N;
    string S;
    cin >> N >> S;

    vector<int> C(N);
    for (int i = 0; i < N; i++) {
        cin >> C[i];
    }

    vector<long long> dp(N + 1, LLONG_MAX);
    dp[0] = 0;

    for (int i = 1; i < N; i++) {
        if (S[i - 1] == S[i]) {
            dp[i + 1] = min(dp[i + 1], dp[i]);
        } else {
            dp[i + 1] = min(dp[i + 1], dp[i] + min(C[i - 1], C[i]));
        }
        dp[i] = min(dp[i], dp[i - 1] + C[i - 1]);
    }

    cout << min(dp[N], dp[N - 1] + C[N - 1]) << endl;

    return 0;
}

まとめ

• Claude 3 Opusの問題C全正答は驚いた
  • LLMによって得意な問題とそうでない問題がありそう
• ABC344Eに続いてABC346Bに関してもGPT-4 Turboはただ一つ正答していた