feature image

2023年8月25日 | ブログ記事

Copilotは競プロの夢を見るか?

はじめに

こんにちは,@masky5859 です。この記事は夏のブログリレー 2023 年 5 日目の記事です。

突然ですが,AI って凄いですよね。まとまった文章を生成するもの,美麗な絵を出力するもの,物体認識を行うものなど用途は様々で,その能力は爆発的に向上し続けています。

これはAIの良くない使い方です。

今回取り上げるのはGitHub Copilotという,コーディングを補助する AI です。僕自身も Copilot をよく使用していて,プログラミングの勉強をしていてわからない言葉や関数があった時などに具体的なコードをつけて説明をしてくれるので大変重宝しています。

これだけ便利なものがあれば当然みなさん,「Copilot だけで競プロの問題をどこまで解けるのだろうか?」と思いますよね?思ってください。異論は認めません。

...うんうん,やはりみなさんそう思っているようですね!そこで本記事では,先日のAtCoder Beginner Contest 314を題材に,Copilot 単体でどこまで競プロの問題を解くことができるのかということを実験していこうと思います。

この記事は AI を用いて競プロコンテストに参加することを推奨するものではありません。また,コンテストに参加する際には,各コンテストの主催者が定める規則を確認してから参加しましょう。

GitHub Copilotに限りませんが,AIの出力するコードが100%安全だとは限らない点には注意が必要です。

いざ尋常に勝負

問題のレベル感

今回題材にする ABC314 のレベルは,

という感じです。僕が自力で解けているのが D までなので,今回 Copilot に解いてもらうのは,最大で D までにしようと思います。C までは行けて,D は半々,というのが僕の事前予想ですが,はたしてどうなるでしょうか。

なお細かい問題文についてはリンク先を参照してください。

A 問題

A 問題は,円周率を少数第 N 位まで出力する問題です。

プロンプト

以下に問題文,入力形式,出力形式を示すので,正しい答えを出力し,2 秒以内に実行が終わる c++のコードを書いてください。

問題文 円周率の小数第 100 位までの値は 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679 です。1 以上 100 以下の整数 N が与えられます。円周率を小数第 N 位まで出力してください。より厳密には、円周率を小数第 N+1 位で切り捨て、末尾の 0 を取り除かずに出力してください。ただし,1 <= N <= 100 です。
入力 N
出力 円周率を小数第 N 位まで 1 行で出力せよ。

出力されたコード
#include <iostream>
#include <string>
using namespace std;

int main() {
    int n;
    string pi = "3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679";
    cin >> n;
    cout << pi.substr(0, n+2) << endl;
    return 0;
}

結果としては,問題なくAC(正答)を取れました。ただ「侮るなよ,奴は四天王の中で最弱だ」と言ったところでしょうか。
記念すべき初AC!やったね!

B 問題

B 問題は,ルーレットの出目と各参加者が賭けた目が与えられ,与えられた目を選んだ人のうち賭けた個数が最も少ない人を出力する問題です。

プロンプト

以下に問題文,入力形式,出力形式を示すので,正しい答えを出力し,2 秒以内に実行が終わる c++のコードを書いてください。

問題文 N 人の人がルーレットの賭けに参加しました。 このルーレットの出目は、0 から 36 までの 37 個の整数のうちいずれかです。 i=1,2,…,N について、人 i は 37 個の目のうち Ci 個の目 A{i,1}A{i,2} ,…,A{i,Ci}に賭けました。ルーレットが回され、出目は X でした。X に賭けた人たちのうち、賭けた目の数が最も少ない人たちの番号を昇順にすべて出力してください。
より形式的には、
1 以上 N 以下の整数 i であって、下記の 2 つの条件をともに満たすものを昇順にすべて出力してください。

条件 1.人 i は X に賭けている。
条件 2.任意の j=1,2,…,N について「人 j が X に賭けているならば、Ci≤Cj」が成り立つ。
ただし,出力すべき番号が 1 つもない場合もあります。そのような場合には 0 のみを出力してください。

入力形式
N
C1
A{1,1},A{1,2} ,…,A{1,C1}
C2
A{2,1},A{2,2} ,…,A{2,C2}
...
CN
A{N,1},A{N,2} ,…,A{N,C2}
X

出力形式
出力するべき番号を昇順にすベて並べた列を、B1,B2,…,BK とする。1 行目には出力するべき番号の個数 K を,2 行目には B1,B2,…,BK を空白区切りで、それぞれ出力せよ。

以下に入力例と出力例を示すので,あなたのコードは必ずそれを満たすようにしてください。

入力例
4
3
7 19 20
4
4 19 24 0
2
26 10
3
19 31 24
19
出力例
2
1 4
この例について解説します。
ルーレットが回され、出目は 19 でした。19 に賭けた人は人 1 ,人 2 、人 4 の 3 人であり、それぞれが賭けた目の個数は 3,4,3 です。よって、19 に賭けた人のうち、賭けた目の個数が最も少ない人は人 1 と人 4 の 2 人です。

出力されたコード
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    vector<pair<int, int>> bets(N);
    for (int i = 0; i < N; i++) {
        int C;
        cin >> C;
        bets[i].second = i + 1;
        for (int j = 0; j < C; j++) {
            int A;
            cin >> A;
            if (A == X) {
                bets[i].first++;
            }
        }
    }

    sort(bets.begin(), bets.end());

    vector<int> winners;
    int min_bets = bets[0].first;
    for (auto& bet : bets) {
        if (bet.first == min_bets && bet.second != 0) {
            winners.push_back(bet.second);
        }
    }

    if (winners.empty()) {
        cout << "0\n";
    } else {
        cout << winners.size() << "\n";
        for (int winner : winners) {
            cout << winner << " ";
        }
        cout << "\n";
    }

    return 0;
}

しかしこのコードはWA(誤答)でした。まずもって,Xの値を受け取る前にXを用いてしまっています。最初にこのことを指摘してみました。すると,次のようにコードが修正されました。


出力されたコード2
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, x;
    cin >> n;
    vector<vector<int>> a(n);
    vector<int> c(n);
    for (int i = 0; i < n; i++) {
        cin >> c[i];
        for (int j = 0; j < c[i]; j++) {
            int ai;
            cin >> ai;
            a[i].push_back(ai);
        }
    }
    cin >> x;

    vector<int> bets(n);
    for (int i = 0; i < n; i++) {
        if (find(a[i].begin(), a[i].end(), x) != a[i].end()) {
            bets[i] = c[i];
        }
    }

    int min_bets = *min_element(bets.begin(), bets.end());
    vector<int> winners;
    for (int i = 0; i < n; i++) {
        if (bets[i] == min_bets && min_bets != 0) {
            winners.push_back(i + 1);
        }
    }

    if (winners.empty()) {
        cout << "0\n";
    } else {
        cout << winners.size() << "\n";
        for (int winner : winners) {
            cout << winner << " ";
        }
        cout << "\n";
    }

    return 0;
}

しかし,このコードもWAが出ます。ただ,先ほどのコードよりはいい感じですね。betsという配列を定義し,その要素を受け取るところまでは意図を読み取ることができます。ただし,これではmin_bets == 0の場合がうまくいきません。場合分けをしているように見えますが,意味をなしていません。そのことを指摘しました。しかし,単純に「min_bets == 0 の場合がうまくいきません。」と指摘しても,ほぼ同じコードが繰り返し出力されました。仕様がないので,細かく場合分けを教えることにしました。


細かく場合分けを教えるプロンプト

このコードも誤りです。もし min_bets が 0 の場合は,次の二つの場合を考える必要があります。
場合 1.配列 bets の中に 0 しかない場合があります。この場合,X にかけた人が存在しないと言うことなので,0 を出力すれば良いです。
場合 2.配列 bets の中に 0 と,0 以外の数が存在する場合があります。この場合,X にかけたひとが少なくとも一人存在します。だから,min_bets の値を 0 を除いて配列 bets の要素で最小の値に更新する必要があります。 以上のことを踏まえて,コードを修正してください。

出力されたコード3
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, x;
    cin >> n;
    vector<vector<int>> a(n);
    vector<int> c(n);
    for (int i = 0; i < n; i++) {
        cin >> c[i];
        for (int j = 0; j < c[i]; j++) {
            int ai;
            cin >> ai;
            a[i].push_back(ai);
        }
    }
    cin >> x;

    vector<int> bets(n);
    for (int i = 0; i < n; i++) {
        if (find(a[i].begin(), a[i].end(), x) != a[i].end()) {
            bets[i] = c[i];
        }
    }

    int min_bets = *min_element(bets.begin(), bets.end());
    if (min_bets == 0) {
        if (count(bets.begin(), bets.end(), 0) == n) {
            cout << "0\n";
        } else {
            min_bets = *min_element(bets.begin(), bets.end(), [](int a, int b) {
                return a != 0 && (b == 0 || a < b);
            });
        }
    }

    vector<int> winners;
    for (int i = 0; i < n; i++) {
        if (bets[i] == min_bets) {
            winners.push_back(i + 1);
        }
    }

    cout << winners.size() << "\n";
    for (int winner : winners) {
        cout << winner << " ";
    }
    cout << "\n";

    return 0;
}

かなり良くなりました。ただしまだ不十分で,betsの要素が全て0の場合は,0と出力した時点で操作を終了すべきですね。このことを指摘しました。すると,正しくコードが修正され(return 0が追加された),無事ACが取れるコードが出力されました!やったー!今のところ自力で書いた方がはるかに楽そうですが...果たしてC問題はどうなることのでしょうか。先が思いやられます。
A問題の提出時間からの空きが苦戦を物語る。

C 問題

C 問題は,与えられた文字列を文字の色ごとにシフトする問題です。僕は本番でうっかり愚直な方法で書いてしまい,TLE(制限時間超過)を出してしまいましたが,果たして Copilot はうまく乗り切ることができるのでしょうか。

プロンプト

以下に問題文,入力形式,出力形式を示すので,正しい答えを出力し,2 秒以内に実行が終わる c++のコードを書いてください。

問題文
英小文字からなる長さ N の文字列 S が与えられます。S の各文字は色 1 、色 2 、… 、色 M の M 色のうちのいずれかで塗られており、i=1,2,…,N について、S の i 文字目は色 Ci で塗られています。各 i=1,2,…,M について、この順番に下記の操作を行います。
S の色 i で塗られた文字からなる部分を、右に 1 つ巡回シフトする。 すなわち、S の 色 i で塗られた文字の位置が先頭のものから順に p1,p2,p3,…,pk 文字目であるとき、S の p1,p2,p3,…,pk 文字目を、それぞれ、S の pk,p1,p2,…,p{k−1}文字目で同時に置き換える。
上記の操作をすべて行った後の、最終的な S を出力してください。
なお、M 色あるどの色についても、その色で塗られた S の文字が必ず 1 つ以上存在することが、制約として保証されます。
また,M,N は 2*10^5 以下の整数であり,M は N 以下だとする。

入力
入力は以下の形式で与えられる。
N M S
C1 C2 … CN

出力
適切に右シフトを行なったあとの文字列 S を出力せよ。

出力されたコード
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m;
    string s;
    cin >> n >> m >> s;
    vector<int> cnt(m);
    for (char c : s) cnt[c - '1']++;
    for (int i = 0; i < m; i++) {
        int shift = cnt[i] % n;
        rotate(s.begin(), s.begin() + n - shift, s.begin() + n);
    }
    cout << s << endl;
    return 0;
}

このコードはWAになります。そもそも,文字の色を示す入力を受け取れていないのでまずはそこを指摘します。すると,次のようなコードが出力されました。

出力されたコード2
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m;
    string s;
    cin >> n >> m >> s;
    vector<int> cnt(m);
    for (int i = 0; i < n; i++) {
        int c;
        cin >> c;
        cnt[c - 1]++;
    }
    for (int i = 0; i < m; i++) {
        int shift = cnt[i] % n;
        rotate(s.begin(), s.begin() + n - shift, s.begin() + n);
    }
    cout << s << endl;
    return 0;
}

確かに入力を受け取ることはできるようになりましたが,ACには至りませんでした。その後,なんとかACの取れるコードが出力されるように試行錯誤しましたが,一向にこのコードから大きく改善される様子が見られませんでした。そこで,最終手段として,自分が本番で用いた解法をプロンプトに含めてみることにしました。

プロンプト

あなたのコードは誤っています。文字列 s のそれぞれの文字に割り当てられた数字ごとに右シフトを行う必要があります。そのことに注意し,コードを修正してください。たとえば,deque を要素に持つ二次元配列を用いる方法が考えられます。

出力されたコード3
#include <iostream>
#include <vector>
#include <deque>
using namespace std;

int main() {
    int n, m;
    string s;
    cin >> n >> m >> s;
    vector<deque<char>> colors(m);
    for (int i = 0; i < n; i++) {
        int c;
        cin >> c;
        colors[c - 1].push_back(s[i]);
    }
    for (int i = 0; i < m; i++) {
        int shift = colors[i].size() % n;
        for (int j = 0; j < shift; j++) {
            char c = colors[i].back();
            colors[i].pop_back();
            colors[i].push_front(c);
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << colors[j][i];
        }
    }
    cout << endl;
    return 0;
}

しかしこのコードもうまくいきません。仕方がないので,細かく間違っているところを手取り足取り教えていこうかと思って新しいプロンプトを考え始めました。そこで僕は,大変な真実に気がつきました。

これ,自分で解くのと一緒じゃん

そうです。僕は「問題文だけ投げれば,Copilot くんがいい感じのコードを勝手に提示してくれて,あわよくばそのまま AC が取れる」ことを目標にやっていたはずなのに,いつの間にか「苦心しながら Copilot くんに手取り足取り言葉で教えてコードを書かせる」ことをしていたのです。これでは本末転倒だと気づき,Copilot で ABC314 の C 問題以降の AC を取ることを諦めました。

結論

GitHub Copilot 単体で競プロはできない

Copilot 単体で競プロを乗り切ることは難しい,というのが今の僕の結論です。問題文が単純な A 問題ならまだしも,B,C のように少し複雑になっただけでも,途端に正しく問題文を読み取ることができなくなったり,入力を受け取ることができなくなったりするのでは,それ単体ではどうしようもないと言っても良いでしょう。今回はABCの基本問題を題材としましたが,より考察力の求められる上位のコンテスト・高難易度の問題ではなおさらです。

もちろん,僕のプロンプトが悪かった可能性は十分にあります。巷には,A,B 問題を AI に丸投げして AC を取っているという猛者がいるという噂もあります。すごい。

Copilot と鋏は使いよう

では,Copilot が使い物にならないかと言えば全くそんなことはありません。Copilot はうまく使うと非常に優秀です。以下に,競プロでどのように Copilot を活かしていけるかということについて,自分の考えを書きます。

例えば,upsolve をしている際などに自分のコードが何かしらの理由で AC が取れないとします。ただ,何度見直しても間違いに気がつくことができない。そのようなときに Copilot を用いると,配列外参照などの単純なミスであれば,コードのどこが誤っているかを指摘してくれます。

また,コーディングの際に,単純な入力を受け取るための 2 重ループ,基本的な dfs や dp などであれば,Copilot が先んじて候補を示してくれるので,コーダーはそれをそのまま受け入れるか,あるいは軽微な修正を施すだけで普通に使えるコードを書くことができます。このように,まず人間がコードを書き,それを Copilot が補助するという形を取れば,コーディング速度は大幅に上がります。

正しく使うと楽できる部分も多い。

まとめ

Copilotのみで競プロをするという試みは歯切れの悪い感じで終わってしまいましたが,これを通してCopilotについての理解が深まりました。これからもCopilotをいい感じに使っていく方法を模索していきたいです。そしてそれ以上にそもそもの競プロ力を高めていきたいです。

明日は@mehm8128 さんの記事です。お楽しみに!

おまけ

Copilot のアイコンってちょっとカエルに見えませんか?

masky5859 icon
この記事を書いた人
masky5859

23B。アルゴリズム班/SysAd班。 犬が好きだにゃん。

この記事をシェア

このエントリーをはてなブックマークに追加
共有

関連する記事

2024年9月17日
1か月でゲームを作った #BlueLINE
Komichi icon Komichi
2024年8月21日
【最新版 / 入門】JUCEを使ってVSTプラグインを作ろう!!!!【WebView UI】
kashiwade icon kashiwade
2021年8月12日
CPCTFを支えたWebshell
mazrean icon mazrean
2022年9月26日
競プロしかシラン人間が web アプリ QK Judge を作った話
tqk icon tqk
2022年9月16日
5日でゲームを作った #tararira
Komichi icon Komichi
2024年8月29日
クロスコンパイルRust
H1rono_K icon H1rono_K
記事一覧 タグ一覧 Google アナリティクスについて 特定商取引法に基づく表記