アルゴリズム実技検定で「エキスパート」ランクを取りました！
こんにちは、co-yarnです。
以前は経路探索エンジンの研究開発を担当していましたが、最近、地点検索システムの研究開発の担当部署に異動しました。
業務ではJava、Kotlin、Rust、Pythonを使っており、競技プログラミングではPythonを使っています。
私事ですが、AtCoder社が主催している第14回アルゴリズム実技検定（PAST）で、最高ランクの「エキスパート」ランクを取得しました！
社内ではエキスパート取得達成は3人目です。
せっかくの機会ですので、今回の note ではPASTの紹介と、「エキスパート」ランクを取ることの何がすごいのかという話をしたいと思います。
対象読者は「競技プログラミングは知っているけど、アルゴリズム実技検定ってなんなの？」という人を中心にします。
最後におまけ程度ですが、「競技プログラミング伸び悩んでいるんだけど」という人に向けての話を載せています。
PASTについて
ここでは「競技プログラミング」についての詳細な説明は省略します。
日本では「AtCoder」が一番有名な競技プログラミングのコンテストサイトです。毎週末にコンテストが開催されており、全世界から8,000人以上がしのぎを削っています。
PASTは、AtCoderが主催する「1からプログラムを作成する能力を問う、実践を想定した」検定です。
別の言い方をすると、「アルゴリズムを理解するだけに留まらず、読解力、思考力、コーディング能力を駆使して問題解決に至る能力」を測る検定です。
試験内容は、5時間の制限時間の中で全部で15問の問題を解いていくといったものです。問題に正解しているかどうかは試験中に確認ができ、不正解であっても試験時間中であれば何度でも出し直しすることが可能です。
得点によって5つのランクに分けられ、およそ3問解くごとに1つランクが上がるようになっています。一番上の「エキスパート」ランクは15問中14問以上正解する必要があります。
前半の問題は「小数第k位で表せられる2つの小数の和を正確に出力してください」（ https://atcoder.jp/contests/past202303-open/tasks/past202303_b ）のように、基礎的なプログラミング文法が分かれば解けるものになっています。
後半の問題はアルゴリズムを知っているだけでなく、それをどう工夫して適用させるのかを考える必要がでてきます。
例えば、上級の人であれば解けるはずの11問目の問題（https://atcoder.jp/contests/past202303-open/tasks/past202303_j ）です。
これからこの問題をどうやって解くことができるのか、解き方の一例をざっくりと説明したいと思います。
可能な限り噛み砕いて説明しますが、すべて理解する必要はありません。解く時のポイントをふんわりと感じ取っていただければと思います（これから問題を解きたい・ネタバレを避けたい方は飛ばしてください！）
ーーーーー解説ここからーーーーー
どのくらい列をシフトするのかを全通り試そうとすると、 1 回のパターンで答えがあっているかを判定するにはすべての文字を1回ずつ見ていく必要があるため、計算量が $${O(HW^2)}$$ となってしまいます。
この場合、例えば $${H = 10}$$, $${W = 4 × 10^4}$$ のようなケースだと、 最悪 $${HW^2 = 1.6 × 10^{10}}$$ 回程度の計算が必要となってしまい、制限時間の 2 秒に間に合わないです。（AtCoderの実行環境では、大抵の場合秒間 $${10^8}$$ 回程度計算されています）
制限時間内に解くためには、 Z-algorithm と呼ばれる「与えられた文字列(長さが $${N}$$ )について、$${k}$$が$${1～N}$$について、『その文字列自身』と『その文字列の $${k}$$ 文字目以降の文字列』が、先頭から何文字目まで一致するか（最長共通接頭辞）を、$${O(N)}$$ の計算量で計算する」というアルゴリズムを使います。（参考: https://snuke.hatenablog.com/entry/2014/12/03/214243 ）
一見、上記のようなアルゴリズムが、今回の問題を解く上でどう役に立つのかがわからないと思います。実は、「ある文字列 $${A}$$ がもう片方の文字列 $${B}$$ の連続部分文字列に含まれるかどうか」を判定するために使うことができます！
具体的には、 $${A + “$” + B}$$ ($${“$”}$$ は $${A}$$ にも $${B}$$ にも含まれない文字)のような文字列を作り、この文字列に対してZ-algorithmを使います。
それから、 $${B}$$ の先頭に当たるところからの最長共通接頭辞の長さを見ていき、 $${A}$$ の長さと一致するものがあれば含まれていると判定することができます。
しかし、今回の問題では列のシフトを行うと末尾の文字が先頭に戻ってきますが、そのようなケースで一致するかが判定できていません。そこで、列の文字列を 2 つ連ねた文字列を作ることで、元の文字列をシフトした文字列を、連続部分文字列として表すことができます。
まとめると、 $${A + “$” + B + B}$$ のような文字列を作ってZ-algorithmを適用することで、「何回シフトすれば目標の文字列と一致できるか」を $${3W + 1}$$ 回の判定で列挙することができます。
あとは、すべての行にでてくるシフトの回数を $${O(HW)}$$ かけて見つければ、この問題に正解することができます。
余談ですが、ローリングハッシュと呼ばれるアルゴリズムでも解けるようです。
ーーーーー解説ここまでーーーーー
このように問題を解く鍵になるアルゴリズムを知っているだけでなく、問題の性質を理解して工夫し、それを正しく実装する力が求められていることが、なんとなく伝わればと思います。
業務で役に立つこと
では、PASTで「エキスパート」ランクを取るほど競技プログラミングを突き詰めることで、一体どんなメリットがあるのでしょうか？
競技プログラミングが業務に役に立つことについては、以前執筆したPG BATTLEの参加記で触れています。
詳しくは記事を見ていただきたいですが、まとめると以下です。
一部のアルゴリズムについては、そのままでてくることがある（深さ優先探索、ダイクストラ法など）
一方で、高難易度の問題で要求されるような高度なアルゴリズムはでてくることはない
複雑な問題に対して、いかに解決するか考え抜く思考力・忍耐力が鍛えられる
計算量の観点が身につくことで、ボトルネックに未然に気がついたり、力の抜きどころがわかる
ちょっと違う観点で、個人的に役に立った（？）経験を少し紹介します。
冒頭で触れた通り、最近私は検索システムに携わる部署に異動になりました。検索システムについて私はほとんど知識がなかったので、業務で携わるに当たって検索システムについて 『検索システム ― 実務者のための開発改善ガイドブック』 という書籍で学習をしていました。
この書籍の中でポスティングリストを使ってどのようにスコアリングを行うかのアルゴリズムについて紹介されています。
書籍自体がわかりやすく書かれているのもありますが、アルゴリズムについて慣れている分、スムーズに理解することができたと思います。
また、コラムではありますが、suffix-arrayやトライ木(Trie)、kd木など、ところどころで競技プログラミングで聞いたことがあるアルゴリズムやデータ構造も紹介されることがありました（本来は逆なんですが）。
アルゴリズム自体を知っていてすぐに役に立ったというわけではありませんが、自分の知識と結びつく瞬間というのは面白いものでした。
PASTに挑戦してみようと思う方へ
「PASTに挑戦してみようかな」と思った方は、過去に開催された問題がAtCoderで公開されているので、ぜひ一度過去問を解いてみてください。なんとなく雰囲気を掴むことができるかなと思います。
本番の受験日ですが、PASTはオンラインでの受験となっており、各回ごとに約3ヶ月各個人の都合の良いタイミングで受験できるようになっています。ですので、これを読んだ直後にやってみるということも可能です。
逆に、しっかり準備してから挑戦するということも可能です（受験期間開始直後に受けると、特別な証明書になるという特典があります）。
詳しくは公式のページを確認してみてください！
伸び悩んでいる人へ
以下の文章は、競技プログラミングをそれなりにやっている人向けの文章です。私個人の体験談としているため、参考程度に読んでいただければと思います。
実は今回、PASTは第1回目から毎回受験しており、第3回目の時にはすでに「上級」ランクを取得していました。
ですので、「上級」ランク取得から約3年経った第14回でようやく「エキスパート」ランクが取得できたということです。正直、結構伸び悩んでいた時期が長かったと思います。
私なりに取り組んでいったことはありますが、「こうすれば伸びた！」というものはありませんでした。
「エキスパート」ランクを取得するために、「後半にかけられる時間をなるべく増やす」という戦略を取っていました。
具体的な時間配分としては「最初の9問で1時間、次の3問で1時間、最後の3問に1時間ずつ」というのを考えていました。そのためには、「前半の問題は素早く解けるようにする」「中盤の問題はつまらないようにする」「後半の問題は解ける可能性を増やす」ということが必要でした。
この戦略を実現するため、以下のことを実践していました。
コンテストには（ARC、AGC含めて）可能な限り出る
ABC終了後に解いた方法を共有し合う会に出る
青diffの問題を解いていく
PASTの過去問を解く
実践で学んでいくことが性に合っていたので、とにかくコンテストに出ていました。コンテストに出ることで、「簡単な問題を素早く解く」「知らないアルゴリズムを知る」と全体的に学びになることが多いです。
体当たりをしてうまく行かなかった部分は悔しさで記憶に定着しやすくなるということもありました。また、コンテスト後に他人と解法や考え方を共有することで、より学びになったり学習をつづけるモチベーションにつながるといった効果が得られました。
「中盤の問題をつまらないようにする」ところを補うため、青diffの問題を解いていきました。問題の抽出には 「AtCoder Problems」を利用させていただきました。
後半の問題にでてくるような高度なアルゴリズムについては、そもそも知っていないと解けないことが多いため、まず知っておくことが大事です。過去に出題されたものと似たようなものがでることもあるため、PASTの過去問をやることは重要だと思い取り組んでいました。
私は取り組めていませんが、最近では学習のためのコンテンツ（典型90や公式テキストなど）も増えているため、人によってはこちらを利用するのがいいかもしれません。
最後に
長くなりましたが、PASTがどのようなものかという話と、「エキスパート」ランクの何がすごいのかという話、おまけ程度ですが個人的な学習への取り組み方についてお話をさせていただきました。
改めて、アルゴリズムの知識だけでなく、問題を解くためにどう工夫をするのか・1から実際のプログラムとして書き上げることができる能力が必要になるんだなということが、なんとなく伝わってくれていれば嬉しく思います。
今回は少し深めの話をしたのですが、もちろん競技プログラミング始めて最初からここまで考えられるようになったわけではないです。楽しみながら、ついでとしてこういった力をつけていくことができるのかなと思います。
ですので、もしこの記事を読んで競技プログラミングやPASTに興味が出てきた方がいれば、ぜひ挑戦してみてください！