この記事は新歓ブログリレー2024の14日目です。

はじめまして、あるいは、こんにちは。アルゴリズム班のComaviusです。

さて、皆さんは唐突にいたずらをしたくなることはありませんか？ありますよね？少なくとも私にはあります。今回は私がtraPの部内SNSであるtraQ(「トラック」と読みます)でちょっとしたいたずらをした時の話をしようと思います。

本題

実はtraQにはtraQgazerというエゴサ支援ツールがあり、これはユーザーが事前に登録した文字列を含む投稿を通知してくれます。そして、やはり自分のユーザー名を登録している人が多いようなので、全ユーザーのユーザー名を部分文字列として持つ文字列を投稿してエゴサをしている陰険な人間(たとえば私など!)を呼び出してやろうと思います。しかし、ただ呼び出すだけでは美しくありません。

アルゴリズム

ここで、美しさために、可能な限り短い文字列でこれを実現することを考えます。これはShortest Superstring Problemという名前の問題で、現実的な時間で厳密解を得ることはできません^[1]。今回は焼きなまし法^[2][3]という近似アルゴリズムを使ってこれを解きたいと思います。

結果と評価

結果として、10分程度の実行で ユーザー名の総文字数=3242文字 から 2674文字 まで改善することができました。これがどれだけ優秀なのかは正直よくわかりませんが、PythonのライブラリであるSageMathのソルバーを十分な時間動かした時の解と同じスコアらしいため、優秀だということにしておきます。

呼び出されてしまった被害者の皆様

宣伝

この記事に興味を抱いた新入生の皆さん、朗報です。来る3/22から競技プログラミングサイトのAtCoderで新しくヒューリスティックコンテスト(AHC031)が開かれ、焼きなまし法をはじめとした近似解法を使って全世界1000人以上の参加者とスコアを競うことができます。ぜひ参加しましょう！

明日は@ikura-hamuさんと@beferiaさんの素晴らしい記事が投稿されます。お楽しみに！