競プロでPythonを使用している人はChatGPT(GPT-3.5)を使用して悩みのTLEを解決できるかもというお話

## はじめに
以前ChatGPTを使用してAtCoderの問題を解いてもらう記事が話題になったのはご存じでしょうか。

https://qiita.com/autotaker1984/items/2929937cd1fea6137d1f

その中の活用方法の一例として軽く触れられているものがありました。
>「このPythonコードをC++で書き直してください」

競プロについて、別の言語に置き換える意味は薄いように思われるかもしれませんが、Python使いは話が変わってきます。嗜む程度に競プロに参加しているPythonerは一度くらい、処理速度の問題で想定解でもTLEをして辛酸を嘗める経験をしていると思います。C++を使いなよと忠言されても **「おれには、これしかないんだ！ だから、これがいちばんいいんだ！！」** [^1] と言うしかない状況でした。[^2]


[^1]:パイロットハンター読んだことないですがこのセリフだけは知っています。心に響きます。
[^2]:この記事書いてて、C++使えばいいだけにも思えてきましたがきっと気のせいです。


yukicoderのコンテスト参加中、解法誤りによってTLEしてしまったコードをもしかするとRustに置き換えるとうまくいくかもしれないと思い、試しにChatGPTで変換すると、変換に成功してRustで提出することが出来ました。これはChatGPTが活用できるのではと実感しました。（もちろん解法誤りのためRustに置き換えても間に合わないのでTLEしました）

生成AIの使用が規制される機運も漂い始めてはいますが、これまでAtCoderで解法は恐らく合ってたもののギリギリTLEをしてしまったコードをChatGPTでRustに変換してAC出来るかということを調べてみました。
私の好きな言葉が「無料」、嫌いな言葉が「有料」なのでChatGPT Plusではなく無料で利用できるGPT-3.5による結果を記載していきます。

## 先に結論
 **DPとかの短くて簡単なコードならそこそこいける！**

## やり方

##### コードの変換を依頼
    以下のPythonによる競技プログラミングのコードをRustのコードに置き換えてください。
    原則として整数型は64bitとしてください。
    入力の受け付けには、`proconio`クレートを使用してください。
    ```
    ここに変換したいPythonのコード全部
    ```

##### エラーが出たとき
    以下のエラーが発生しました。解決してください。
    ```
    エラーべた貼り
    ```

##### 成功してACした時
    うまくいきました！　ありがとうございます！　天才！

お礼は忘れないように伝えましょう。

## 成功例：ABC278 E Grid Filling (Diff:996)

**問題**

https://atcoder.jp/contests/abc278/tasks/abc278_e

**TLEしたPythonの提出 (コード長 1304 Byte)**

https://atcoder.jp/contests/abc278/submissions/36624683

**変換したRustによる提出**

https://atcoder.jp/contests/abc278/submissions/43906452

**補足**
一発で変換成功です。
コンテスト本番は頑張ってRustに変換しようと1時間かけて失敗した苦い経験をしましたが、ChatGPTではものの1分かからずに変換できました。
比較的長いコードですが2次元累積和用の短い関数が含まれてるため、上手く変換できたのだと思われます。
元々のコードでは3次元配列のアクセスにより処理時間が掛かっており、その部分を定数倍高速化すればAC出来た問題です。
お礼を伝えると以下のような返答がきました。

![アンサー.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1227398/ed836c96-709d-fc2a-6224-114b6922f42b.png)

これさりげなくPython煽ってませんか？

## 成功例：ARC146 B Plus and AND (Diff:1335)

**問題**

https://atcoder.jp/contests/arc146/tasks/arc146_b

**TLEしたPythonの提出 (コード長 607 Byte)**

https://atcoder.jp/contests/arc146/submissions/34170873

**変換したRustによる提出**

https://atcoder.jp/contests/arc146/submissions/43906852

**補足**
一発で変換成功です。
元のPythonの提出について、実行時間制限:5000ms に対して5030msで終了しているような実行時間制限より少しだけ超過した時間で終了している場合は処理が打ち切られていないと判断できます。
Rustに置き換えることで処理時間が307msまで短くなるのはちょっと驚きですね。


## 一応成功例：ABC309 E Family and Insurance (Diff:957)

**問題**

https://atcoder.jp/contests/abc309/tasks/abc309_e

**TLEしたPythonの提出 (コード長 520 Byte)**

https://atcoder.jp/contests/abc309/submissions/43907678

※正しくはPypyによる提出で、Pythonによる提出なら間に合います

**変換した最終的なRustによる提出**

https://atcoder.jp/contests/abc309/submissions/43907984

**補足**
Pythonでハマりやすいdfsの問題です。
コードの変換が部分的に上手くいかず、手動で3行修正しています。
問題となったのは入力部分。
$p_2 \ldots p_N$の入力を$p_1 \ldots p_N$だと勘違いします。
こういったミスは指摘するより手動で直す方が楽そうです。

<details> 
<summary><font color="#ffa500">元の生成コード（折り畳みコード）</font></summary><div>

```rust
use proconio::input;

fn main() {
    input! {
        n: usize,
        m: usize,
        p: [usize; n],
        xy: [(usize, usize); m],
    }

    let mut y = vec![0; n + 1];
    for (x, y_i) in xy {
        y[x] = y[x].max(y_i + 1);
    }

    let mut l = vec![Vec::new(); n + 1];
    for (i, &p_i) in p.iter().enumerate().skip(1) {
        l[p_i].push(i + 1);
    }

    let mut ans = 0;

    fn dfs(i: usize, cnt: usize, l: &Vec<Vec<usize>>, y: &Vec<usize>, ans: &mut usize) {
        let cnt = cnt.max(y[i]);
        if cnt > 0 {
            *ans += 1;
        }
        for &l_i in &l[i] {
            dfs(l_i, cnt.saturating_sub(1), l, y, ans); // マイナスになっても問題ない
        }
    }

    dfs(1, 0, &l, &y, &mut ans);
    println!("{}", ans);
}

```
</div></details>


## 一応成功例：ABC175 E Picking Goods (Diff:1554)

**問題**

https://atcoder.jp/contests/abc175/tasks/abc175_e

**TLEしたPythonの提出 (コード長 828 Byte)**

https://atcoder.jp/contests/abc175/submissions/18991906

**変換したRustによる提出**

https://atcoder.jp/contests/abc175/submissions/43908761

**補足**
何度か変換を試し成功確率20%くらいでした。
元のPythonのコードで`max`を使用してListの最大値を代入しているのですが、この部分の変換が難解だったようです。
```python
        if i!=R-1:
            DP[i+1][j][0] = max(DP[i][j])
```
自分で誤りを見つけてもいいですし、何度かトライするのもありなのかなと思います。


## ぎり失敗例：競プロ典型 90 問 043 - Maze Challenge with Lack of Sleep（★4）

**問題**

https://atcoder.jp/contests/typical90/tasks/typical90_aq

**TLEしたPythonの提出 (コード長 729 Byte)**

https://atcoder.jp/contests/typical90/submissions/24614568

**変換したRustによる提出**

https://atcoder.jp/contests/typical90/submissions/43907009

**補足**
01-BFSの問題です。変換自体は成功します。ただし変換しても間に合わず。
置き換えたものの実行時間内におさまらないこともあります。こういうパターンもあります。
理由としては元々のコードがあまりよろしくないせいなのかなと。
変換したことにより高速化は一応出来ているはずで類題となる[ABC246 E Bishop 2](https://atcoder.jp/contests/abc246/tasks/abc246_e)では[Pythonで5662msのコード](https://atcoder.jp/contests/abc246/submissions/30684714)が[Rustで1439msのコード](https://atcoder.jp/contests/abc246/submissions/43907331)に変換出来ています。



## ゴリゴリの失敗例
変換に失敗したPythonの提出コードのURLを記載します。
使用アルゴリズムとしては、Mo's、ダイクストラ、めぐる式2分探索、優先度付きキュー、Decimalです。
変換しにくかったり、長かったりするコードは上手く変換できません。
無料版なので仕方ない気もします。~~この辺りはPay to Winですね。~~

https://atcoder.jp/contests/abc174/submissions/40367407

https://atcoder.jp/contests/zone2021/submissions/22251557

https://atcoder.jp/contests/abc298/submissions/40779807

https://atcoder.jp/contests/abc307/submissions/42930103

https://atcoder.jp/contests/abc308/submissions/43147622

## 最後の補足
- 試しに「Bing AI」や「Lamma2」を使用してみましたが、これらはコンパイルが通るコードを生成してくれませんでした。
- ChatGPTの性能は一定ではないという話があります。また、この記事の内容はコンテスト外で過去問を解いただけで本番で使用したわけではありません。混み合えば処理が完了しないこともあります。ご留意ください。
- あくまで、定数倍高速化によりACする方法です。ABCのB問題などでTLEした場合は定数倍高速化で間に合うようなギリギリを求められる問題は出てこないです。その場合は解法を見直したりChatGPTに解法を聞いたりする方が得策です。
- Rustについての勉強になってそうと思うかもしれませんが、エラーの解決を全任せにするスタンスでは何も覚えられていないです。勉強にはそれなりの学ぶ態度が必要そうです。
- 複雑な処理は少々コードが長くなっても簡単なアルゴリズム書いた方が成功率があがりそうです。また大文字小文字の差だけの変数名があるとバグが発生しやすそうに思えたので区別しやすい変数名に変換しておくとよいかもしれないです。
- ライブラリ系のコードは事前に準備しておかないとエラーになりがちで辛そうです。逆に準備しておくと活用できる可能性はグッと上がりそうです。
- 整数のオーバーフローを考えたくない場合に多言語からPythonに変換するといった方法も利用できそうです。例として[ABC185 C Duodecim Ferra](https://atcoder.jp/contests/abc185/tasks/abc185_c)のような問題で使うことが出来そうです。
- 頑張ればヒューリステッィクの変換にも使えると思います。
- お金のある人はChatGPT Plusで試してくれると嬉しいです。