自己紹介
初めまして。モノグサ株式会社のソフトウェアエンジニアのインターンに参加させていただいた堀毛晴輝です。
芝浦工業大学の学部2年で、グラフ理論に興味があります。
参加を決めた理由
AtCoderのコンテストでモノグサ株式会社のことを知り、競プロで問われるアルゴリズムやデータ構造を活用しながら課題の解決に取り組んでいるということで興味を持っていました。AtCoder Jobsでインターンの募集を見つけ、「参加できたら自分のスキルアップにつなげることができる！」と思い応募させていただきました。
取り組んだこと
記憶アプリMonoxerでは問題文とその解答を入力すると誤答を自動で生成し、選択問題形式で出題できる機能があります。
今回のインターンでは、数式の誤答生成の精度向上と"この中にはない"が正解となる問題のサポートを行いました。
既存の数式誤答生成アルゴリズム
解答の数式をMathMLの形式で受け取っているのでこれを利用します。MathMLは木構造となっていて、例えば$x^{2}+1$は、
のようにデータを持っています。この木に適切な変更/ノードの追加/削除といった操作を行うことで誤答を生成することが可能です。
また、問題の難易度を上げるために次のような手順で誤答を生成しています（以下、これを「クロス戦略」と呼びます）。
- 2つの操作A, B を選び、Aのみ適用したもの/Bのみ適用したもの/A, B両方適用したもの を誤答とする
これにより、消去法で正解を求めるのが困難になります。
精度向上
削除の操作について、既存のものでは元の数式に対してどの部分を消すかということを先に決定して操作時はその箇所を削除するような実装となっていました。しかし、追加の操作を行った後に削除をしようとすると消す箇所がズレてしまい、適切な削除が行えていない...ということがありました。
この問題について、まず各ノードに前後の兄弟のデータを持たせるようにしました。これにより内部で扱っている木構造の前後関係を壊さずにノード追加/削除が行えます（追加/削除するノードの前後のみを更新すれば良いです）。
次に、削除を行うタイミングでどの部分を消せば良いかを決定するようにしました。兄弟の前後関係が常に正しく保たれているため、消すべきノードの一番前に移動し、その項の末尾まで順に消していくような実装をしました。
"この中にはない"が正解となる問題のサポート
選択肢の中に"この中にはない"が含まれていると、選択肢から答えを推測することがより困難になります。
しかし、既存のアルゴリズムを用いて生成した選択肢に"この中にはない"を足すだけだと"この中にはない"が必ず不正解の選択肢となってしまうため、"この中にはない"が正解となる問題も生成できるようにする必要があります。
これは次のような手順で誤答を生成するようにしました。
- 3つの操作A, B, Cを選ぶ
- 正解にAを適用させる これをダミーの正解とする
- ダミーの正解に操作B, Cを使ってクロス戦略を行う
これにより、正解が"この中にはない"となるような問題が生成できるようになりました。
インターンの感想
今まで個人の開発しか経験がなく初めての複数人での開発ということで、Gitの使い方や読みやすいコードが書けるかどうかなど不安があったのですが、メンターの方と毎日1on1でコミュニケーションを取らせていただけたので実装の相談やわからない箇所の質問が気兼ねなくできました。また、コードレビューを通じてコードの改善だけではなく「どうしてこの書き方をすると良いのか」の理由を考えることができ、インターン前と比べ読みやすいコードが書けるようになったと思います。また、社員の方やインターンの方とボードゲームや毎週のおやつ会などを通じて交流することができて、とても楽しかったです。
貴重な経験をさせていただき、本当にありがとうございました！
