AIを競技プログラミングで活用してみる

２回目の登場の中3のIです。
ここでは昨今進化が著しいAI、そのうちのChatGPT(GPT-3.5)というAIを使ってプログラミングをしてみよう！という内容で書いていきます。

そもそもChatGPTとは

ChatGPTは、OpenAIによって開発された自然言語処理技術の一種です。GPT（Generative Pre-trained Transformer）というモデルの一部であり、大量のテキストデータを学習して自然な文章や会話を生成することができるAIです。GPT-3.5アーキテクチャをベースにしており、さまざまなタスクに対する応答や文章生成が可能です。

この文章は「ChatGPTとはなんですか?」という質問に、ChatGPTが返してきたものです。こんな感じで色々質問に答えてくれるAIです。

競技プログラミングってなんぞや

競技プログラミングとは、プログラミングスキルとアルゴリズムの解決能力を競うコンピュータサイエンスの競技です。主にオンライン上で行われ、参加者は与えられた問題に対してプログラムを書き、そのプログラムが一定のテストケースを通過するかどうかを競います。
競技プログラミングの特徴は以下のとおりです：
1.アルゴリズムの応用: 参加者は様々な問題に対して最適なアルゴリズムを設計・実装する必要があります。これにより、問題解決力や論理思考力が鍛えられます。
2.制限時間とメモリ: 解答プログラムは一定の制限時間内に実行され、またメモリ制限もある場合があります。したがって、効率的なアルゴリズムを使わなければならず、最適化の余地があります。
3.多様な問題: 競技プログラミングの問題は、数学、グラフ理論、動的計画法、文字列処理、幾何学など、さまざまな分野にわたります。これにより、幅広い知識とアルゴリズムの理解が求められます。
4.競技環境: オンラインジャッジと呼ばれるシステムを通じてプログラムを提出し、自動的にテストケースに対する結果が判定されます。正しい解答だけでなく、効率性も評価されます。
5.国際的なコンテスト: 競技プログラミングは国際的な大会も開催され、世界中のプログラマーが競い合います。有名な大会にはICPC（国際大学対抗プログラミングコンテスト）やCodeforces、Topcoderなどがあります。(ChatGPTより引用)

最近では就職試験で競技プログラミングの問題を解く必要があったりもします。(Google社など)
物理部でも多くの部員がAtCoderという競技プログラミングのコンテストに参加しています。

AtCoderについて

今回は先程競技プログラミングの例として名前を挙げた、AtCoderの問題でAIを試してみます。
AtCoderには様々なコンテストが難易度別に分けられており、一番簡単なABC(AtCoder Beginner Contest)や中級者向けのARC(Atcoder Regular Contest)、天才以外お断りパズルコンテストの異名を持つAGC(AtCoder Grand Contest)、アルゴリズムの最適解を求めるAHC(AtCoder Heuristic Contest)などがあります。

ABCの例
問題例 {width=500px}

実際にAIを使ってみる

A問題

先ほど紹介したAtCoderの、執筆時点で最新のABC315のA問題「tcdr」を解かせていきます。
(https://atcoder.jp/contests/abc315/tasks/abc315_a)
ちなみにA問題はプログラミングの基礎であるif文、for文さえ書ければできると言われるほど簡単です。

とりあえず問題文だけ与えてみます

「英小文字からなる文字列Sが与えられます。Sからa,e,i,o,uをすべて取り除いて得られる文字列を出力してください。なお、Sはa,e,i,o,u以外の文字を一つ以上含みます。
この問題をC++で解いてください」

ChatGPTくん↓

「以下は、与えられた文字列からa,e,i,o,uを取り除いて得られる文字列を出力するC++プログラムの例です。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <string>

int main() {
    std::string S;
    std::cin >> S;

    std::string result;
    for (char c : S) {
        if (c != 'a' && c != 'e' && c != 'i' && c != 'o' && c != 'u') {
            result += c;
        }
    }

    std::cout << result << std::endl;

    return 0;
}

このコードは、与えられた文字列を1文字ずつ走査し、母音文字でない場合は新たな文字列resultに追加していく方法で処理しています。最終的にresult文字列を出力します。」

ちゃんとしたコードが出てきました　提出してみるともちろん正解になりました。

B問題

A問題より少し難しいB問題も解かせてみます。
同じくABC315の「The Middle Day」です。
(https://atcoder.jp/contests/abc315/tasks/abc315_b)

これも問題文だけ与えてみます

「AtCoder 国の暦では、一年は\(1, 2, \dots ,M\)番目の月の\(M\)か月からなり、そのうち\(i\)番目の月は\(1, 2, \dots, D_i\)番目の日の\(D_i\)日からなります。
さらに、 AtCoder 国の一年の日数は奇数、即ち\(D_1 + D_2 + \dots + D_M\)は奇数です。
一年の真ん中の日は何番目の月の何番目の日か求めてください。
言い換えると、\(1\)番目の月の\(1\)番目の日を\(1\)日目としたときの
\((D_1 + D_2 + \dots + D_M + 1) / 2\)日目が何番目の月の何番目の日かを求めてください。
この問題をC++で解いてください」

ChatGPTくん↓

「以下は、与えられた条件に基づいて、C++で問題を解くためのサンプルコードです。このコードは、AtCoder国の暦に従って、真ん中の日が何番目の月の何番目の日かを計算します。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int M; // 月の数
    cin >> M;

    vector<int> D(M); // 各月の日数
    for (int i = 0; i < M; ++i) {
        cin >> D[i];
    }

    int totalDays = 0;
    for (int i = 0; i < M; ++i) {
        totalDays += D[i];
    }

    // 真ん中の日の位置を計算
    int middleDay = (totalDays + 1) / 2;

    int monthIdx = 0;
    while (middleDay > D[monthIdx]) {
        middleDay -= D[monthIdx];
        ++monthIdx;
    }

    cout << monthIdx + 1 << " " << middleDay << endl;
    // 1-based indexを表示

    return 0;
}

このコードは、入力として月の数と各月の日数を受け取り、AtCoder国の暦に従って真ん中の日の位置を計算し、それが何番目の月の何番目の日かを表示します。コード内のコメントも参考にしてください。」

今度もちゃんとしたコードが出てきました。提出してみるともちろん正解です。

C問題

今度はC問題を解かせてみます。C問題は、問題文の流れでなんとなく解けるA,B問題よりも急に難しくなります。
問題文の流れで解こうとすると制限時間を超過してしまい、正解にならないからです。
正解にするには、効率よく情報をさばくコードが必要になります。
AIにできるのでしょうか

とりあえず問題文だけ

「\(N\)カップのアイスクリームがあります。\(i\)カップ目の味は\(F_i\)、美味しさは\(S_i\)(\(S-i\)は偶数)です。
あなたは、\(N\)個のカップの中から\(2\)つを選んで食べることにしました。
このときの満足度は次のように定義されます。
食べたアイスクリームの美味しさを\(s,t\)( 但し、\(s≥t\)) とする。
\(2\)つのカップの味が異なるなら、満足度は\(s+t\)である。そうでないなら、満足度は\(s + t/2\)である。
満足度として達成可能な最大値を求めてください。
この問題をC++で解いてください」

ChatGPTくん↓

「以下は、与えられた条件に基づいて、C++で問題を解くためのサンプルコードです。このコードは、N個のアイスクリームの組み合わせから最大の満足度を求めます。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N; // アイスクリームの数
    cin >> N;

    vector<int> F(N); // 味
    vector<int> S(N); // 美味しさ

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

    long long maxSatisfaction = 0;

    // すべての組み合わせを試す
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (i == j) continue; // 同じアイスクリームを2つ選ぶことはできない

            long long satisfaction;
            if (F[i] != F[j]) {
                satisfaction = static_cast<long long>(S[i]) +
                　　　　　　　　　static_cast<long long>(S[j]);
            } else {
                satisfaction = static_cast<long long>(S[i]) +
                　　　　　　　　　static_cast<long long>(S[j]) / 2;
            }

            maxSatisfaction = max(maxSatisfaction, satisfaction);
        }
    }

    cout << maxSatisfaction << endl;

    return 0;
}

このコードは、アイスクリームの組み合わせを全て試し、与えられた条件に従って満足度を計算し、その中から最大の満足度を求めます。コード内のコメントも参考にしてください。」　　

時間切れになりそうな二重for文を使うコードを出してきました…　とりあえず提出してみると、案の定時間切れになってしまいました。

実際に私がコンテストで提出したコードの手順で伝えてみます(最適解なわけではない)。

それぞれの味で一番美味しいもの、二番目に美味しいものをまとめる
それぞれの味で一番美味しいものだけの組み合わせを作る
それぞれの味で一番美味しいもの、0.5倍した二番目に美味しいもので組み合わせを作る
組み合わせの中で一番美味しいものを選ぶ
この手順で実行するコードを書いてください

ChatGPTくん↓

理解しやすい手順で問題を解くために、提案された手順に従ってアプローチを取ります。以下に、与えられた手順に基づいて問題を解くC++コードを示します。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    vector<int> flavors(N), tastiness(N);
    vector<int> maxTastiness(N, 0); // それぞれの味で一番美味しいもの
    vector<int> secondMaxTastiness(N, 0); // それぞれの味で二番目に美味しいもの

    for (int i = 0; i < N; ++i) {
        cin >> flavors[i] >> tastiness[i];

        if (tastiness[i] >= maxTastiness[flavors[i]]) {
            secondMaxTastiness[flavors[i]] = maxTastiness[flavors[i]];
            maxTastiness[flavors[i]] = tastiness[i];
        } else if (tastiness[i] > secondMaxTastiness[flavors[i]]) {
            secondMaxTastiness[flavors[i]] = tastiness[i];
        }
    }

    int maxSatisfaction = 0;

    for (int i = 0; i < N; ++i) {
        int s = maxTastiness[flavors[i]];
        int t = secondMaxTastiness[flavors[i]];

        int satisfaction;

        if (flavors[i] != flavors[j]) {
            satisfaction = s + t;
        } else {
            satisfaction = s + t / 2;
        }

        maxSatisfaction = max(maxSatisfaction, satisfaction);
    }

    cout << maxSatisfaction << endl;

    return 0;
}

このコードは、与えられた手順に従って最大の満足度を計算します。まず、各味に対して一番美味しいアイスクリームと二番目に美味しいアイスクリームを保持します。次に、それぞれのアイスクリームの味に対して最大の満足度を計算し、その中から最大の満足度を選択します。

なんか定義していない変数jを使ってますね。一個前に出力されたコードに引っ張られている感じ？
その辺の処理はいらないので無くします。
そして、配列maxTastiness、secondMaxtastinessの要素数が足りていません。このコードではN個の要素がありますが、途中でN+1番目の要素にアクセスする処理が行われる可能性があり、範囲外参照をしてしまいます。手順２、４もできていないので、修正してみます。

まず、maxTastiness、secondMaxtastinessの要素数が足りていなく範囲外参照をしてしまう可能性があります。要素数をN+1にしてください。
また、各味に対して一番美味しいアイスクリームと二番目に美味しいアイスクリームで組み合わせを作る処理の中で、違う味かどうかを判定する無駄な処理が発生しています。
それぞれの味のsatisfactionの値を出し、maxSatisfactionを更新してください。
そして、全ての味の中での、美味しさが最大になる組み合わせを作ることはできていません。
現状の２回目のfor文の処理の後で、maxTastinessを降順にソートして、最大と二番目に大きい美味しさの値の和を出し、maxSatisfactionと比較し、値が大きい方を出力してください。

ChatGPTくん↓

理解しました。提供されたコードの問題点を修正し、新しい手順に従ってコードを書き換えたいと思います。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    vector<int> flavors(N), tastiness(N);

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

    vector<int> maxTastiness(N+1, 0); // それぞれの味で一番美味しいもの
    vector<int> secondMaxTastiness(N+1, 0); // それぞれの味で二番目に美味しいもの

    for (int i = 0; i < N; ++i) {
        int flavor = flavors[i];
        int t = tastiness[i];

        if (t >= maxTastiness[flavor]) {
            secondMaxTastiness[flavor] = maxTastiness[flavor];
            maxTastiness[flavor] = t;
        } else if (t > secondMaxTastiness[flavor]) {
            secondMaxTastiness[flavor] = t;
        }
    }

    int maxSatisfaction = 0;

    for (int i = 0; i < N; ++i) {
        int s = maxTastiness[flavors[i]];
        int t = secondMaxTastiness[flavors[i]];

        int satisfaction = s + t / 2;

        maxSatisfaction = max(maxSatisfaction, satisfaction);
    }

    sort(maxTastiness.rbegin(), maxTastiness.rend()); // maxTastinessを降順にソート
    int combinationMaxSatisfaction = maxTastiness[0] + maxTastiness[1];

    maxSatisfaction = max(maxSatisfaction, combinationMaxSatisfaction);

    cout << maxSatisfaction << endl;

    return 0;
}

この修正されたコードでは、最初に各味の美味しさを保持し、一番美味しいと二番目に美味しいアイスクリームを計算します。その後、各アイスクリームの組み合わせの満足度を計算し、最大の満足度を求めるために、maxTastinessを降順にソートして最大と二番目に美味しいアイスクリームの和を取得し、それを元の最大満足度と比較して最終的な結果を出力しています。

ちゃんと修正されたコードが出てきました。提出してみると正解になりました。

D問題

D問題以降は残念ながら僕が完全に理解してできているわけではないので、先送りということにしておきます。

まとめ

ChatGPTくんはAtCoderのA,B問題は問題文だけ渡しても解けるが、C問題はアルゴリズムを自分で考え伝えないと解けない。

参考文献

競技プログラミングとChatGPTを含むAIについて 2022-12-07 chokudai https://chokudai.hatenablog.com/entry/2022/12/07/161959

あとがたり(駄文)

以前Twitter(Xではない)でAIにエンジニアの仕事が奪われる！！、と言っている人を見かけたことがあります。しかし、それは違うのではないかと思っているのです。
確かにこの記事で分かるように、AIはコードを書くことはできますが、しかし１から生み出すということは難しいです。
エンジニアに求められている能力は顧客の本当に欲しい物を出すことだ、という内容のことをQiitaで言っている人がいました。
AIにそんな能力があるでしょうか？顧客の本当に欲しい物を作り出すためには、その顧客が抱えている様々な背景などを考慮する必要があるでしょう。それは社会経験を積み色々なデータが備わっている人間にしかできないことだと私は思っています。

昔からAI(≒機械)が人間の能力を上回り、人間に反逆するという内容の作品はあります。その一例としてマトリックスがありますが、人類が機械を大量破壊、追放した結果反逆が発生した、という設定があるらしいです。
AIに意思・感情を持たせてしまうとAIに仕事を奪われそうと騒いでいる人間との軋轢が発生してしまい、実際にマトリックスのような世界になってしまうかもしれません
そんなことを防ぐために、AIについての理解を深めるということは重要なのではないかということを思っています
(要約：AIが発展してるから、ちゃんとどんな感じのもので何ができるのかは理解しておこうね！)