はじめに

こんにちは。ソフトウェアエンジニアの淵脇です。2020年から日本経済新聞社に入社しまして、日経IDの開発に携わっております。普段は趣味で競技プログラミングというものをやっており、また日経でも以前競技プログラミングのコンテストをいくつか開催しているということで、そのご紹介及び楽しさについて解説させていただきたいと思います。

競技プログラミングとは

競技プログラミングとは問題に対して正しい出力をするコードをいかに早く正確に書けるかを競い合うスポーツです。以前はプログラミングコンテスト(プロコン)といわれることも多かったのですが、最近は特にアルゴリズム系のコンテストを指して競技プログラミングといわれることが多いイメージです。

日本ではAtCoderが有名ですが、Codeforcesといった海外の大手サイトも含めほぼ毎週コンテストが開催されており、毎回数千人～1万人といった人数が参加しています。また、Google Code JamやFacebook Hacker Cupといった海外の大手IT企業が主催する優勝賞金数百万円クラスの大型イベントなどもあります。

筆者は競技プログラミングが大好きでして、AtCoder や Codeforces、TopCoder などでは「イエローコーダー」と呼ばれるレベルまで到達したことがあります。また、Facebook Hacker Cup では上位入賞者向けのノベルティであるTシャツを何度か頂きました。

日本経済新聞社でも全国統一プログラミング王決定戦、第二回全国統一プログラミング王決定戦といったコンテストを主催しており、大勢の方に参加いただきました。本日は全国統一プログラミング王決定戦のご紹介も兼ねて、競技プログラミングの楽しさをお伝えしたいと思います。

競技プログラミングが役に立つ場面

個人的には競技プログラミングそれ自体が楽しいからやっている部分が大きいのですが、もちろん業務においてもその知識が活用できるポイントがたくさんあります。例えば、

• 日常的にコードを書くことでプログラミングの心理的障壁が低くなる
• 計算量の概念に慣れ親しみ、データ量に対する処理時間の大まかな感覚が身につく
• 場面に応じた適切な最適化を選択できるようになる

などは競技プログラミングの大きな利点と言えるでしょう。私自身の具体的な事例として2点ほどご紹介すると、

• データ分析系の業務で工場のセンサーデータをインデックス化する基盤を開発していた時、競技プログラミングの知識を活かすことで計算量が改善ができるポイントを発見し、クエリ応答の時間を200分の1にすることに成功した。
• ブロックチェーン事業に携わっていた時、ブロックチェーン自体が何かと実体がわかりにくいと言われる技術であったため、要素技術であるハッシュチェーンに関して計算量解析を行うことで数字で顧客に訴求でき案件化につながった。

などがありました。

問題を見てみましょう

言葉だけではなかなか伝わりにくいと思いますので、全国統一プログラミング王決定戦で出題された問題を実際に見てみたいと思います。まずは一番やさしい問題であるA問題を見てみましょう。

（実際の問題はこちら)

AtCoderでは企業が主催するコンテストにおいて、最初のA問題に主催の企業に由来する問題文を出題することがよくあります。問題文は少し長文ですが、よく読むと典型的な数学の問題であることがわかり、最大値は$\min(A,B)$人、最小値は$\max(0, (A+B)-N)$人であることがわかります。

ちなみにこの問題を一番早く解いた人、つまりコンテストが始まってから「問題文を読む」「解答を考える」「プログラムを書く」「提出する」の一連の流れを最も早くこなした人は、「50秒」でその流れを完遂しています。このように比較的難易度の低い問題が出る序盤はスポーツのような感覚もあります。いかがでしょうか。少しだけゲーム感覚の楽しさが見えてきたのではないでしょうか。

難易度の高い問題を見てみましょう

では次に比較的難しい問題を見てみましょう。

（実際の問題はこちら)

競技プログラミングは一般に比較的簡単な問題をいかに早く解くかというだけでなく、このように難易度の高い問題を考え抜くというという側面もあります。この問題は全国統一プログラミング王決定戦予選において、本戦に出場できる上位200人に入れるかどうかの鍵になった問題でした。ちなみにAtCoderにおいてこのような700点や800点の問題がある程度通せる人は「イエローコーダー」といわれるレベルであり比較的ハイレベルな層になります。

こういった高難易度の問題は、すぐに「こうすれば解ける」という方針がわからないものが多いため次のような考察を実施します。

1. 問題文からすぐに分かることを整理してみる

   少しだけグラフ理論の知識が必要になりますが、それを前提とすると「重みが大きい辺以外は考える必要がなさそう」「最終的にいくつかの連結成分に分解して、各連結成分は元のグラフのサブグラフにすれば良さそう」といったことがすぐにわかります。

2. 紙の上で実験してみる

   例をいくつか考えノートにグラフを書き、手で辺を消したり追加したりして実験してみます。

3. ヒントとなるようなキーワードを抽出してみる

   「連結」「グラフ（Not 木）」といったキーワードから「Union Find」「Kruskal(実際には使いません)」あたりを想像します。また、「重み」といったキーワードから「ソート」したりするのかも、といった連想も働かせます。

4. メタ典型が当てはまらないか考えてみる

   競技プログラミングを少しやっていくと、「グラフの辺を削除云々というタイプの問題の場合、逆に辺を追加していくとうまくいくことが多い」といった典型的なメタ考察の引き出しが増えてきます。そのようなメタ典型を当てはめてみたりします。

このような考察をたどることで方針が立ったら実装をして提出をする、という流れになります。このようにパズル的な楽しさもあるのが競技プログラミングというものです。

終わりに

本記事では日本経済新聞社主催のプログラミングコンテストを題材に競技プログラミングのご紹介をさせていただきました。

テクノロジーメディアを目指す日本経済新聞社では、 日経電子版や日経IDなどの情報サービス・プラットフォームの開発に、このようなデータ構造やアルゴリズムの技術を活用しています。 メディアの未来を作る仕事に興味のある方は、ぜひお気軽にご連絡ください。

https://hack.nikkei.com/jobs