Go to Qiita Advent Calendar Top
LoginSignup
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@kikutannnb

AIと自然言語処理を使ってAtcoderの問題のタグ付けをしました

Last updated at Posted at 2025-09-22

1. はじめに

こんにちはキクタンと申します。今回生成AIと自然言語処理を使って、Atcoderの問題(ABC175~420)と関連アルゴリズムのタグづけを行いました。

またその過程で問題urlと解説urlの結びつけを行い、まとめました。これらのデータは何かと使えると思うので、過去問全体の網羅的なタグ付け、URLの結びつけなど、必要に応じて自由に使ってみてください。リポジトリに置いておきます。

github：https://github.com/kikutak1182/problem_recommend

なおこのデータを使って問題レコメンドアプリ（解説記事）を個人開発で制作しました。こちらの記事が前編、今回が後編みたいな感じなので、気になったら見ていただけると幸いです。
レコメンドアプリURL：https://problem-recommend-150123537389.asia-northeast1.run.app/

2. 注意

  • この記事は過去のABCの問題のネタバレを含みます

  • 今回タグづけした範囲は、ABC175~420、difficulty400以上の問題です

  • タグ付け自体完全ではなく、問題によっては精度が低いことや、一部の問題でURLなど壊れている可能性などあります、ご了承ください

  • またタグ付けにあたりAtCoderやAtCoder Problemsのデータを参考にしています。感謝

3. 今回作成したデータ

  • 問題（ABC175~420）にタグ付けしたデータ
problems_data.json
{
  "abc175_e": {
    "title": "ABC175 E",
    "problem_url": "https://atcoder.jp/contests/abc175/tasks/abc175_e",
    "editorial_url": "https://atcoder.jp/contests/abc175/editorial/54",
    "tags": ["動的計画法", "ビット演算", "巡回セールスマン問題"],
    "tag_ids": ["DP", "BOP", "TSP"],
    "confidence_scores": [1.18, 1.04, 0.58],
    "detailed_scores": {
      "DP":  {"self_confidence": 0.90, "embedding_similarity": 0.36, "rule_based_score": 1},
      "BOP": {"self_confidence": 0.75, "embedding_similarity": 0.53, "rule_based_score": 1},
      "TSP": {"self_confidence": 0.60, "embedding_similarity": 0.16, "rule_based_score": 0}
    }
  }
}...
  • URL結びつけ
editorial_mappings.json
{
  "editorial_mappings": {
    "abc175_a": {
      "contest_id": "abc175",
      "problem_index": "A",
      "problem_url": "https://atcoder.jp/contests/abc175/tasks/abc175_a",
      "editorial_url": "https://atcoder.jp/contests/abc175/editorial/51",
      "editorial_id": 51
    },
    "abc175_b": {
      "contest_id": "abc175",
      "problem_index": "B",
      "problem_url": "https://atcoder.jp/contests/abc175/tasks/abc175_b",
      "editorial_url": "https://atcoder.jp/contests/abc175/editorial/50",
      "editorial_id": 50
    }, 
    ...
  }
}
  • タグ定義ファイル（108タグを用意）
tag_definitions.json
{
  "tags": [
    {
      "id": "DP",
      "name": "動的計画法",
      "aliases": ["DP", "動的計画", "Dynamic Programming", "メモ化", "dp"],
      "description": "大きな問題を部分問題に分割し、結果をテーブルに記録・再利用する最適化手法。「i番目までで状態jになる最適値/場合の数」を漸化式で求めるのが典型で、ナップサック問題などが代表例。計算量は(状態数)×(遷移)で決まり、bitDPや区間DPといった頻出パターンも存在する。"
    },
    {
      "id": "KDP", 
      "name": "桁DP",
      "aliases": ["桁DP", "桁dp", "digit DP", "digit dp"],
      "description": "数値の各桁を状態として持つ動的計画法の特殊形。N桁以下で特定条件を満たす数の個数を数える問題に使用される。桁数×桁×フラグ状態をDPテーブルとし、上からi桁目まで確定した状態を遷移。計算量はO(桁数×10×状態数)で、ABC形式では頻出パターン。"
    },
    ...
  ]
}

4. 背景

今回の主な成果物としては

  • 問題へのタグ付け
  • 問題-解説URL結びつけ

だと思っています。まずはこれらを作った背景・必要性について説明します。

4.1 Atcoderの問題タグ付けが無い

前の記事で説明した問題レコメンドアプリを作るには、特定のアルゴリズムから、そのアルゴリズムが使われている問題を検索（あるいは列挙）する必要があります。つまり問題とアルゴリズムのタグ付けデータが必要でした。しかし調べたところ過去問全体へのタグ付けは存在せず、そのためタグデータも自作する必要がありました。

4.2 生成AIを使ったタグ付け

このタグ付けを考えていたのは今年5月頃だったのですが、当時生成AIを使用した競プロでの不正により競プロ界隈が荒れていた記憶があります。これにインスピレーションを受け、「AIが問題を解けるならAIによるタグ付けなんて造作もないはず」と思い、さっそくOpenAIのAPI(o4-mini)に問題文を投げ、「この問題を解くのに必要なアルゴリズムを最大３つ選出して」とプロンプトを与えました。

しかし結果の精度はかなり悪く、非実用的でした。

理由（仮説ですが...）は主に２つあると思っていて、

  1. 単純に使用したモデルが弱い(o4-mini)
  2. chatGPTに問題文をコピペする時とは推論の仕方が異なる

です。
1に関しては当時API料金が今より高かったのでしょうがない気がします。
2に関しては「タグ付けして」という今回のプロンプトでは「解法候補を探索して上位を列挙」するだけなのに対し、gptに問題文を貼り付けて「これを解いて」という普段のやり方では「解法候補の探索→アルゴリズムの構築→実装、テスト」までやってくれる気がします。（ここは完全に推察でしかないですが）

もちろんお金をかけてより良いモデルを使う、プロンプトを校正するなど改善案はありましたが、それによりどのくらいタグ精度が上がるかは未知数でした。
そこでより直接的な方法として「解説からタグを抽出する」方法を選択しました。

4.3 Atcoderの解説URL

そこでまず問題URLと解説URLを結びつけるところから始める必要がありました。

ABC(Atcoder Beginners Contest)の問題URLは以下のように、非常に簡潔にまとまっています。

https://atcoder.jp/contests/abc424/tasks/abc424_a

一方でABC424のA~G問題の公式解説URLを列挙してみます。

A問題：https://atcoder.jp/contests/abc424/editorial/13920
B問題：https://atcoder.jp/contests/abc424/editorial/13931
C問題：https://atcoder.jp/contests/abc424/editorial/13899
D問題：https://atcoder.jp/contests/abc424/editorial/13932
E問題：https://atcoder.jp/contests/abc424/editorial/13858
F問題：https://atcoder.jp/contests/abc424/editorial/13900
G問題：https://atcoder.jp/contests/abc424/editorial/13936

このように、解説URLは末尾の謎の自然数で管理されています。単調増加すらしていません。これはABC424が特殊なのではなく、他のABC回もほぼ同様です。謎ですね。

このため問題文と解説文からタグ推定をするために、あらかじめURLをまとめておく必要があります。これは解説ページのソースをスクレイピングすると解説URLが入手できます。（下の解説がまとまっているページ）
image.png

なお、他にも細かい注意点があります。
まず、ABC316の欠番です。ABC316が存在しないことで、コンテスト番号と配列のインデックスが合わなかったりします。把握必須です。

また一部のABCには、Ex問題がありますが、実はEx問題のURLは少し特殊で、例えばABC233のEx問題を見ると、

https://atcoder.jp/contests/abc233/tasks/abc233_h

と、なぜか/abc233_exではなく/abc233_hとなっています。不思議ですね。

5. タグ推定・用いた技術

本題に入ります。今やりたいのは、「問題テキストと解説テキストから必要なアルゴリズムを抽出してタグ付け」です。大まかに以下のフローでタグ付けを行いました。

  1. 競プロでよく使われるアルゴリズムや典型知識を100個ほど考え、タグとして定義とする
  2. 問題ごとのタグ候補を考える（8個ほどに絞る）
    2.1. 問題・解説テキストに完全一致でその単語が存在するかどうか（ルールベース）
    2.2. 問題・解説テキストをエンべディングし、コサイン類似度を計算
  3. タグ候補と問題・解説テキストをOpenAIのAPIに投げ、各候補タグの妥当性を聞く
  4. 最後に、ルールベース＋コサイン類似度＋AI推定結果を用いて信頼度スコアを計算、上位3つをタグとして選出

5.1 タグ定義

tag_definition.json
{
      "id": "DP",
      "name": "動的計画法",
      "aliases": ["DP", "動的計画", "Dynamic Programming", "メモ化", "dp"],
      "description": "大きな問題を部分問題に分割し、結果をテーブルに記録・再利用する最適化手法。「i番目までで状態jになる最適値/場合の数」を漸化式で求めるのが典型で、ナップサック問題などが代表例。計算量は(状態数)×(遷移)で決まり、bitDPや区間DPといった頻出パターンも存在する。"
}

このような形式でタグを108個ほど定義しています。aliasesに含まれる単語が問題・解説に完全一致で存在すると、ルールベースのスコア（後述）を加算します。またdescriptionからタグのエンべディング（後述）を計算します。

なお橙・赤diffあたりの高度典型や、逆に「配列」「重実装」のような意味が広いタグは含まれない可能性が高いです。ご了承ください。

なおタグ定義には「典型手法、100個答えよ」みたいな記事をかなり参考にしました（今は無いようです）。

5.2 タグ・問題文のエンべディングとコサイン類似度計算

ここから問題文＋解説文を統合したものを単に「問題文」と呼ぶことにします。問題文に紐づけるタグを考える時、問題文とタグのdescriptionの類似度が高ければ適切なタグと言えます。そこで、各タグと各問題文をベクトル化して、コサイン類似度を計算し、embedding_similarity(0.0~1.0)とします。

実際はこれもOpenAIを使用しています。OpenAI Embeddingsのtext-embedding-3-smallというモデルで、タグdescription、問題文をそれぞれ1536次元にエンべディングしています。

SentenceTransformersを使ってローカルでエンべディングする方法もあります（当初はこれを使っていた）が、OpenAIの方が最新モデルを使えること、計算が早いこと、またコストもそこまで高くない（1000問強で、おそらく数十円くらい）ことからこちらを選択しました。

5.3 キーワード完全一致

例えば解説の中に"二分探索","binary search"というワードが存在するなら、直感的に「二分探索」タグは相応しい気がします。

image.png

  • 例えばこの問題なら「動的計画法」「二分探索」がタグに含まれているべきです

各タグに対してエイリアス("aliases")を用意しておき、解説にエイリアスと完全一致する単語があるかどうかでrule_based_score(0.0 or 1.0)をつけます。

5.4 AIによるタグの妥当性

先述したとおり、AIが競プロの問題を解けるというバックグラウンドから、AIによるタグの妥当性の推定が効果的と考えます。

コサイン類似度、ルールベーススコアを元に、100個以上の定義タグから「候補タグ」を8個用意します。その後、OpenAIのAPI（モデルはo4-mini）を使って、候補タグがその問題文に相応しいか？というスコアをつけてもらい、self_confidence(0.0~1.0)とします。

候補タグを8個に減らすことでOpenAI APIに渡す入力トークン数を減らす狙いがあります。言語モデルに与える文脈が長くなるほどコストや処理時間が増大するため、候補タグの数を絞ることで効率よく判定できるようにしました。

5.5 推定結果

最終的なタグの信頼度confidence_scoreを、
confidence_score = 0.5 * self_confidence + 0.5 * embedding_similarity + rule_based_score
で計算します。この辺りの係数は割と雑につけたので改善の余地はあると思います。

confidence_scoreが高い順に上位３つを、問題のタグとしました。

先述しましたが、出力結果例です

{
  "abc175_e": {
    "title": "ABC175 E",
    "problem_url": "https://atcoder.jp/contests/abc175/tasks/abc175_e",
    "editorial_url": "https://atcoder.jp/contests/abc175/editorial/54",
    "tags": ["動的計画法", "ビット演算", "巡回セールスマン問題"],
    "tag_ids": ["DP", "BOP", "TSP"],
    "confidence_scores": [1.18, 1.04, 0.58],
    "detailed_scores": {
      "DP":  {"self_confidence": 0.90, "embedding_similarity": 0.36, "rule_based_score": 1},
      "BOP": {"self_confidence": 0.75, "embedding_similarity": 0.53, "rule_based_score": 1},
      "TSP": {"self_confidence": 0.60, "embedding_similarity": 0.16, "rule_based_score": 0}
    }
  }
}

6. おわりに

かかった金額

OpenAIのAPIはリクエストを送るのにお金がかかります。従量課金制で、例えばo4-miniモデルなら100万トークンで5ドルくらいです（正確には入力、出力で金額が違ったりします）。

今回バッチ処理やテキストキャッシュなどの工夫をしてかなりコストを下げた結果、abc175~420のdifficulty400以上の問題はおよそ1000問強ありましたが、かかった金額は5ドルに満たないと思います。もちろん実験や推定やり直しなどもあったのでもう少しかかりましたが、それでも合計15ドルくらいでできたと思います。

課題・可能性

  • Atcoderの問題タグ付け、やっぱり正解データが存在しないので、今回の手法がどのくらい良いものなのか検証しようが無いのが難しかったです。もしかしたら「Atcoder Tags」のデータを正解ラベルとして用いるのがよかったかもしれません。一般的なタグ付けタスクではどうしているのか、気になるところです。

  • 新しいコンテストが行われたときに、自動・半自動でタグ生成してデプロイみたいなCI/CDを意識した設計もやってみたいです。

  • 感覚的にタグの精度は70%くらいで、まだ改善の余地はあると思います。一番の問題点は自分でタグを定義してしまっているので、どの定義タグにも当てはまらない問題に対応できてないことです。解説や問題から直接的にタグを抽出するようなやり方で、精度がいい方法があれば取り組むべきだと思います。

  • 他にも、生成AIによるself_confidenceスコアに関して、Atcoderの問題・解説を使ってAIをファインチューニングすることで、「競プロっぽい表現・文脈」に対応させることができると思います。またこれにより、タグ定義なしで問題＋解説からいきなりタグを生成できると思うので、柔軟性＋精度を両立したタグづけができると思います。割と面白いタスクだと思うので、誰かぜひ挑戦してみて欲しいです。

感想

生成AIが発展して競プロの問題を解けるようになり、AIを使った不正などネガティブなニュースが増える一方で、逆に「生成AIが競プロに貢献できること」を考えられたのは良かったかなと思います。

また構想からデータ作成、アプリ開発、公開まで３ヶ月くらいはかかりましたが、いろんな技術を調べたり触ったりしてできるだけ質の良いものを作ろうと考えたのは良い経験だったなと思います。

なおタグ生成のコードもそのうち整理して公開できたらしたいと考えています。

何かの参考になれば幸いです。ここまで読んでいただきありがとうございました。

1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?