競プロAI(AtCoder Beginner Contestの解法を予測するWebアプリ)を作った

# はじめに
Webアプリを作って公開してQiitaに書く、ということがやりたくて、競プロAIが話題になっていたのでAtCoder Beginner Contestの解法を予測するWebアプリを作りました。精度はイマイチですし実用性もあまりないですが、試して遊んでいただけたら嬉しいです。

https://abc-predictor.herokuapp.com/

# 使い方
![スクリーンショット 2022-02-11 22.19.33.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1749271/20a46f53-d583-7176-d8af-c65fca39abef.png)
問題文をコピペ、配点を選択、変数の範囲を入力して、解法予測ボタンをクリックします。問題文の数式が崩れていても結果には影響しません。

![スクリーンショット 2022-02-11 22.26.18.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1749271/89268758-ac2d-85e6-ea54-4fa187f842af.png)
予測結果が棒グラフで表示されます。最も確率が高い解法のバーが赤く表示されます。

# 仕組み
配点、変数の範囲、300個程度の単語について問題文に含まれるか否か、を特徴量にしてLightGBMで多クラス分類をしています。学習データはABC126〜220の問題を用いています。解法のラベルは[ATCODER TAGS](https://atcoder-tags.herokuapp.com/)様に許可を頂いて、スクレイピングしました(ありがとうございました!)。

## 取得したデータを眺める
単純にプロット・抽出しただけですが、結構面白いです。

### 配点の分布
解法ごとの配点の分布です。
![スクリーンショット 2022-02-11 22.44.00.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1749271/d63e37ca-6c11-322e-6ece-b8ecb8bcd62f.png)
![スクリーンショット 2022-02-11 22.44.29.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1749271/43dfe533-ee30-24ae-0d82-5486c11b89e2.png)
![スクリーンショット 2022-02-11 22.44.45.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1749271/6d0bbfd6-7b29-caf2-6ba0-f8dbea33c581.png)

### 変数の最大値の分布
青の点が最小の変数の最大値、オレンジの点が最大の変数の最大値です。
![スクリーンショット 2022-02-11 22.48.35.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1749271/207b1cd6-9c64-8f18-abfe-16c94cdfadb0.png)
![スクリーンショット 2022-02-11 22.48.52.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1749271/34495baa-29ac-4c79-2323-16927204d3b1.png)
![スクリーンショット 2022-02-11 22.49.07.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1749271/8aee9371-f804-d8f4-72fe-c407e8bf18c1.png)

### 特徴的な単語
TF-IDFで各解法に特徴的な単語を抽出しました。

| Easy|基礎DP|bitDP|桁DP|Union-Find|BIT・セグ木|queue|Flow|Game |
| ---|---|---|---|---|---|---|---|--- |
| 出力|割っ|全て|数字|関係|クエリ|持っ|まだ|使っ |
| 以上|余り|条件|もの|友達|定義|捨てる|できる|始め |
| 高橋|ただし|もの|うち|選び|処理|取り出し|最大|交互 |
| 文字列|マス|満たす|ちょうど|最大|番目|操作|マス|勝つ |
| 判定|移動|以上|表記|存在|種類|報酬|表し|ゲーム |
| 最大|高橋|異なる|表し|重み|かつ|入っ|置く|行動 |
| 満たす|個数|種類|以上|平面|答え|選べ|置き|どちら |
| これら|大きく|並び|個数|でき|含む|働く|選択|最善 |
| いくつ|方法|最小|いくつ|結び|全て|ボール|作り|二人 |
| それぞれ|最小|替え|割っ|座標|整数列|あなた|二つ|最適 |
| 文字|でき|番号|特別|パス|計算|これら|達成|勝ち |
| でき|非常|できる|扱い|付け|長さ|高橋|情報|負け |

| 全探索|二分探索|bit全探索|BFS・DFS|最短経路|Ad-Hoc|貪欲|整数|文字列 |
| ---|---|---|---|---|---|---|---|--- |
| 満たす|うち|番号|でき|かかり|いくつ|最大|個数|文字列 |
| 存在|min|つい|上下|移動|条件|でき|満たす|文字 |
| もの|それぞれ|条件|移動|番号|それぞれ|最小|素数|小文字 |
| 条件|最小|存在|つない|また|最大|選ん|条件|長さ |
| いくつ|最も|一方|頂点|最小|でき|行う|以上|判定 |
| 最小|すなわち|以上|左右|途中|満たす|条件|うち|先頭 |
| 長さ|小さい|または|最短|場合|番目|以上|もの|出力 |
| 判定|選ん|行う|隣接|頂点|考え|満たす|gcd|アルファベット順 |
| 場合|番目|等しい|番号|グラフ|高橋|番目|ただし|大文字 |
| 文字列|最大|個数|つい|通っ|ただし|番号|いくつ|置き換え |
| うち|異なる|得る|たどり着け|つけ|あなた|できる|整数列|例えば |
| 番目|ペア|通り|双方向|時間|ひとつ|合計|長さ|部分 |

## モデルの精度
7:3に分割して検証しました。

|解法|検証データ数|Top-1 Acc.(%)|Top-3 Acc.(%)|
|---|---|---|---|
| Easy|57|91.2|98.2 |
| 文字列|11|18.2|36.4 |
| 全探索|11|18.2|45.5 |
| 整数|8|37.5|75.0 |
| 基礎DP|7|14.3|14.3 |
| 貪欲|6|0.0|83.3 |
| Ad-Hoc|6|0.0|16.7 |
| 二分探索|5|0.0|0.0 |
| 最短経路|4|0.0|25.0 |
| BIT・セグ木|3|0.0|0.0 |
| BFS・DFS|2|0.0|0.0 |
| queue|2|0.0|0.0 |
| bitDP|2|0.0|50.0 |
| bit全探索|1|0.0|0.0 |
| Union-Find|1|0.0|0.0 |
| 桁DP|1|0.0|0.0 |
| Flow|1|0.0|0.0 |
| その他|41|12.2|26.8 |

絶対に過学習しています。

# その他
- UIがクソダサいんですが、どうすればカッコよく作れますか？
- Herokuで公開したけど、AWSの100倍楽でした。