はじめに

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

使い方

問題文をコピペ、配点を選択、変数の範囲を入力して、解法予測ボタンをクリックします。問題文の数式が崩れていても結果には影響しません。

予測結果が棒グラフで表示されます。最も確率が高い解法のバーが赤く表示されます。

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

単純にプロット・抽出しただけですが、結構面白いです。

解法ごとの配点の分布です。

青の点が最小の変数の最大値、オレンジの点が最大の変数の最大値です。

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

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