目次
1．はじめに
2．作ったもの
3．ASPRの仕組み
4．拡張機能を作ってみて
1. はじめに
筆者のプロフィール
- 大学3年
- AtCoder 緑色
- 最近Webアプリの勉強もしています
2. 作ったもの
AtCoder Similar Problem Recommender(ASPR)
タイトル通り、問題ページに行くと類似問題タブが表示され、そこから類似問題のページに飛べるようになっています。
クリックするとABCの問題の中から一番類似度が高い問題TOP3のリンクが表示されます。
ちなみにですが、特にTewtterなどに宣伝もしいなかったのにAtCoder Clansで紹介されていました。（なんでだろう？）
このスクリプトの目的
1. 色（難易度）に囚われずに問題に挑戦するきっかけを作る
AtCoder Problemsというサイトでは、問題別に難易度を表す色がつけられていて色別にどのくらいの問題を解いたことがあるかなどを確認することができます。
しかし、難易度は目安にすぎず、茶であっても解ける緑diffの問題もありますし、上のレベルを解説ACすることで得られる知識もあります。自分のレート以下の難易度の問題を解いて得られる力（早解き力など）もありますが、そのようなことばかりしていると、解けなかったときにモチベの低下につながってしまうこともあります。
「茶ですら解けないのに緑の問題が解けるはずがない…」といった風に考えてしまうことによって上のレベルの問題に挑戦する機会を失っている人に対し、このスクリプトは「似ている問題だし解けるかも！」と思わせることで様々な問題に挑戦する機会を与えることができます。
2. 似ている問題文だが、解法が違う問題文を見つけることができる
きっかけは、ABC206-D KAIBUNsyoでした。簡単な回文の問題はいくつか解いたことはありましたが、まさかこのように解けるとは思わず解けた後に感動したことを覚えています（ネタバレ回避のため解法についての言及は避けます）。
このように普通の回文の問題から、問題文は似ているが解法は違う問題に挑戦することができれば、考察力の向上にも繋がります。
リンク
Tampermonkey
ASPR
3. ASPRの仕組み
バックエンドにはFlaskを使用していて、スクリプトから送られてきたJSONデータからあらかじめ計算されている類似問題のランキングTOP３を返すようにしています。
どのようにして問題文の類似度を計算しているか
(1) 問題文で Bag Of Words(BoW) を作る
Bag Of Wordsとは、その文章が含んでいる単語の個数をベクトルで表現したものです。
例えば、
- 私はたこやきが好きです。
- 私はお好み焼きが好きです。
- 私はDPが嫌いです。
という３つの文章を考えると、文章で出現する単語は、「私」、「は」、「たこやき」、「お好み焼き」、「DP」、「が」、「好き」、「嫌い」、「です」、の９個になります。
次に、それぞれの単語を次元として、文章の中に含まれている個数を要素としたベクトルを作成します。
（例：「私はたこやきが好きです。」）
(1, 1, 1, 0, 0, 1, 1, 0, 1)
このようにしてABCの問題文をベクトル化します。
(2)コサイン類似度を計算する
（１）でベクトル化した問題文同士の類似度をコサイン類似度を用いて計算していきます。
コサイン類似度は以下の式で求めることができます。
\cos(\vec{a}, \vec{b}) =
\dfrac{ \vec{a} \cdot \vec{b}\ }{ \|\vec{a}\| \|\vec{b}\| }
イメージ的には下図の通りで、比較するベクトル同士の方向が似ているほどコサイン類似度が高くなります。
図を見てみるとaはcよりもbとの距離が近いですが、性質上bとcの方が類似度が高いと判断されます。
前処理で行ったこと
(1) 固有名詞の除去
ABCの問題文には「高橋くん」、「青木くん」、「AtCodeerくん」、「すぬけくん」といった人物が登場します。
「高橋くん」が登場しているかどうかによって問題文の類似度を計算してほしくないため、このような固有名詞は取り除きます。
(2) 記号の除去
AtCoderの問題文にはよく「A,B,C」のような記号が書かれています。そのような文字が問題文に登場するかどうかで問題文の類似度を計算してほしくないので、固有名詞と同様にこのような記号も取り除きます。
ASPRの改善点
(1) ベクトル化の手法
今回のスクリプトではベクトル化の手法にBagOfWordsを使用しましたが、このほかにも「word2vec」、「doc2vec」、などさまざまなベクトル化の手法があります。
BagOfWordsは一番単純な手法になるため、正確性に関してはまだまだです。
(2) 記号の除去について
記号を除去してしまうと都合が悪い問題もあります。例えば、
のように単純な問題は記号が使われている数式が問題を読み解く上で重要になります。そのため記号を取り除いてしまうと問題としての類似度が測りにくくなってしまいます。（実際の類似問題を見てみると、文章の長さが似ているものが推薦されている？）
4. 拡張機能を作ってみて
1.開発楽しい！
まず、自分で動くものを作って誰かに使ってもらうという体験ができるのは本当に楽しいことです。
AtCoderなどの競技プログラミングやPandasなどを使ったデータ分析などは今までやってきたことがあったのですが、開発をしてアウトプットをする機会はありませんでした。そのため、自分が作ったものを発表して意見をもらうという機会は貴重なものでした。
2.「プログラミング」を知ることができた
上でも書きましたが、今までなんとなくPythonだけを使ってきただけで別の言語を触る機会がありませんでした。そのため、JavaScriptなどの まだ使ったことのない言語に触れることができたので良い経験になりました。
また、HTTP通信やWebAPIなど今まで聞いたことがないような単語が出てきて、インターネットで起こっていることについて何もわかっていなかったことを痛感しました。
それがきかっけでそこから応用情報技術者試験の勉強をしたり、実際にAWSなどを使ってWebサーバーを立ててみたりと色々なことに挑戦するようになりました。
今後の目標
1.自然言語処理をしっかり勉強する
今回作ったASPRには様々な問題点があります。自然言語処理の知識もまだまだありません。
B４になると研究室に配属され、順調にいけば研究で自然言語処理を使うことになるので、これから自然言語処理についてしっかり勉強していこうと思っています。
2.新たなWebアプリケーションを作ってみる
AtCoderに関する新しいWebアプリケーションの案が一つあるので、それを形にしたいと考えています。