こんにちは、チームラボの福岡です。チームラボでは、グラフィクスエンジニアとしてインタラクティブエンジニアというチームに所属しており、映像作品をプログラミングで作りこむ仕事をしています。

ですが今回は、空間展示にも映像にも全く関係ない話題となります。

概要

東工大のサークル「traP」さん主催で、AtCoderを利用した競技プログラミングコンテストが、チームラボのオフィスで開催されたため、背景の説明とそのレポートを記しました。

競技プログラミング、略して「競プロ」

そうです！
今日の話題は、競技プログラミング、略して競プロです。

皆さん───
「競技プログラミング」という言葉を耳にしたことは──　ありますか？

どうしても、知る機会がないと想像がつかない気がします。このワードを初めて聞いて想像する絵というのは、十人十色なのではないでしょうか。

少しだけ説明しますと、もちろん、上図のように土俵の上で1対1で戦うもの…ではありません。（すみません、上の絵は忘れて下さい！）

とはいえ実のところ、プログラミングで以って戦う、ことは合ってます。

ですが、多くの場合は
・Webプラットフォーム上で完結する、多人数参加型のコンテスト形式
で行われるものであり
・「出題」に対して適切な答えを与えるような「プログラムを提出」し、
・その正解数と提出時間を競う
という形式のものが多いです。

※日本で「競プロ」というと、これを指しがちです。

少し競プロの世界を（万人に優しめな説明で）

【！】興味なければ、次の見出しまで飛ばしてくださいね【！】
競プロってなんぞや…？という話を少し具体的にします。

「競プロではとにかく問題が出される、というけど、具体的にどんな問題よ？」と気になられるかもしれません。

そうですね…例えば。短い問題ですと
「100万個の整数が書かれたリストが与えられます。この中で、"2つ足して1億を超える"ような数のペアは何組あるか？を求めてください」
といったものです。

おお。なるほど。おおお～…？
・・・ピンと来ないかもしれませんよね。

では折角なので、図にして分かりやすくしてみます。

こんなリストがプログラムに与えられるわけですね。

そして、プログラムは何を数えるかというと・・・

「足して1億を超える」ようなペアがいくつあるのか？？を数えます。

…ではどんな方法があるでしょうか？

素朴に考えると、例えばこんな方針を思いつきます。
「100万個の整数を、総当たりで足し算した結果表を作り、"足して1億を超えたマス"の数を数える」
なるほど。要は、100マス計算のような表を作るわけです。
つまりこういうことですね。

結果的にこれで正解自体は求められます。おお。なんと！

しかし。
・・・問題があることにお気づきでしょうか？

そうです。正しい答えが求まる方法、だとしてもマズいのです。

実は総当たりというのは…　大変です。ワールドカップのグループリーグ戦の結果表などでも総当たりの表は出てきますが、100万個同士の総当たりともなると、その組み合わせの数は膨大になります。

はい。そうです。ヤバいのです…（悲）

100万個の中のペアを考えると、約5000億回の足し算をしなければならないわけです。これは現代のコンピュータを以ってしても、一瞬で終わる処理ではありません。(1秒で1億回の足し算だとしても1時間以上です)

ところが、ある【工夫した手順と方法】で処理することで、数千万回くらいの処理(1秒くらいに収まる)で、終えることができるわけです（記事の最後に答えを書きます。興味ある方はどうぞ）

それゆえ、問題には「プログラムの計算時間は2秒以内とする」というふうに、実行時間に制限がつくことが一般的です。

ですから、処理する手順や計算をかなり工夫して、短い処理時間で結果を返す方法を考察し、それをプログラムとして書き起こす必要があります。これが楽しい所であり難しいところです。

コンテストが、オフィスで行われた！！

話を戻します。

…などなどの理由で、この競技プログラミング、略して「競プロ」は、特に大学生、情報科学系の学部で、ここ数年、急速な普及を見せています。

なかでも今回、東京工業大学の学生サークルである「traP」さんが、競プロの大会を開かれる！しかも開催場所を探している！ということでしたので、ここで満を持して、チームラボの登場です。会場として6階の会議室フロアを丸ごと貸し出し、運営を手助けすることを申し出ました。

結果、チームラボオフィスで、（大学生主導による）競プロコンテストが開催されたこととなりました。めでたいですね。

コンテストの、始まる気配

当日の段取りの確認などをし、運営陣だけで静かだった会場は、12時半を回ると、続々と、参加者がオフィスに集結してきます。

30人を超える参加者でしたが、うまく各机に分かれてもらい、チームをその場で組みたい人はメンバーを募集したり、と、コンテストらしい運営が進められていきます。

オリジナルの名札をもらえるのが、このコンテストの個性的な所の１つかもしれません。私も貰いました。ネット上でしか会ったことのない参加者同士になりがちゆえ、識別するのには一役買います。

一段落終わったのち、コンテスト開始まで残り10分、残り5分、と迫るにつれて、少しずつ場が静かになっていきます。特に何かを賭けた大会というわけではありませんが、戦の前の緊張感なのかもしれません。

今回は、1チーム最大3人までが許されるチーム戦です。こうした「嵐の前の静けさ」を楽しみながら、各チーム、役割分担や戦法について最後の確認をしていきます。

チームラボからも6名参加しました

13時のコンテスト開始の合図と同時に、全員が一斉に問題文のページを開きます。私の文章力ではこの臨場感を伝えられませんが、こうして、会場は突然「始まった！」という雰囲気に包まれていきます。

18時までの、5時間です。いま、長い戦いの火蓋が切られました。

さて、少々話が変わりますが、チームラボには「競プロ部」が存在します。

この競プロ部から今回は6人が参加し、【1チーム3人】ですから、2チーム編成としました。チーム名は「えび天そばちゃ」という名前に決定。海老みたいな名前の人と、お茶みたいな名前の人と、私（あだ名が"そばや"）、の3人で構成されるためです。

私らのチームは、戦法としては単純で、「順に若い番号の問題から見ていく。できそうならコードを書ききる所までトライ。詰まったor嫌な予感がしたら後回し。後回しの問題を、時々相談したり、担当を交代したりして進めていく」というものでした。

結果的に私も、難しめの問題である「問題F」の提出に成功したため、かなりホクホクした気持ちで終えることが出来ました。いかつい問題の討伐に思いがけず成功すると、気持ちええものですね…久々に味わった感覚です。

参加者としての感想

個人的に1番良かった瞬間は「考えた実装方法をチームメンバーに説明している途中で、突然"あっ！"と高速化の方法を思いつけたこと」です。一緒に論理を追ってもらうだけで自分の頭の整理になる、という、こういった協力の方法もあるんだな、と学ばされました。なにも直接教えあったりコードを書いてもらうことだけが協力ではないということですね。

また、年齢をやや露呈する発言なのかもしれませんが、5時間フルに集中するのは、中々に堪えるものもありました。でもそれもまた良いですね。

それに、こういった長い時間に亘る大会というのは、重たい問題に対して色んな具体例を考えたり、とことん重たい考察をする余裕があります。また、チームメンバーと共に考察を練ったり、コードも協力して書いたり、…といったチーム戦ならではの楽しみ方もできます。

多くの場合、趣味としての「競プロ」といったら、1人で参加し、しかも2時間程度で終わり、実際の会場に集まることもなくWeb上で完結することが多いため、こういった臨場感というものはありません。しかし今回の「長時間」「チーム戦」「実会場で」という普段味わえない要素により、独特の臨場感をみなさん楽しめたのではないでしょうか。

結果発表、そして解説！

作問者が、スライドを見せながら、直々に解説をしていきます。競プロ界でも有名な、名だたるメンバーが次々に登壇していき、圧巻です。「東工大もこれだけの面々を擁してんだぞ」と言わんばかりの布陣です。しかも、このオフィスに勢揃いしてる…というのが、大変不思議な気分です。

東工大と医科歯科大の併合を題材にした(!?)文字列の問題や、写真のように、チーズケーキを題材にした図形的な問題 (東工大といえば当然チーズケーキなので) が出たりと、問題でもかなり遊んでいることが伝わります。

さて。
「問題を解く5時間」も当然ながら楽しいしメインディッシュなのですが、この「出題者による直接解説」も、負けず劣らず、この手のコンテストの醍醐味なのではないかと思っております。

この「解説」は、結局、解法の説明には留まらなくなります。

そういった、「作問者」を1人称にした現実のドラマがあったこと、さらには「問題」を1人称にしたドラマがあったこと──　それがスライド解説と共に、明らかにされていきます。それも1問1問ごとにです。参加者一同、おなじ空間を共にして、その解説を囲んでいます。

なかなか言葉に説明しがたい「ワクワク感」のようなものが、会場を満たしていて、とてもいい時間を過ごさせてもらったなと思いました。ときに、作問者の競プロ人生の一端が垣間見えると言って過言でない出題もあり、それが徐々に明かされていくこの解説の時間が、私はとても好きです。大袈裟でしょうか。

会場提供する上の具体的な懸念

参加者ではなく、開催に協力する側としての視点も、一部書き残したいと思います。

ネット環境

まず最大の心配が「会場として、ネット接続を安定して提供できるか」というところでしたが、結果的に何とかなりました。ホッとした、というのが正直な所です。競プロのコンテストは、e-sportsほどの強力なネット環境は求められませんが、それでも開催するにあたりこれは生命線ですね。

お菓子

一方、かなり小さな後悔ですが、お菓子がすぐになくなりました。予想をかなり上回って、お菓子が大人気でした。新しく補充されるたびに、ちょっとした殺到が起こり、「コンテストは、そんなにお菓子を食べたくなるのか！」と驚いていました…笑

企業の規模からすれば、お菓子は大した額ではないかもしれないため、もう少し供給を頑張ればよかった気もします。

メモデスク

あと１つ良かった点は、メモデスクを有効活用して貰えたことでしょうか。

実は多くの机は、机の上面が大きな紙になっており、ペンでメモを書き放題になっています。具体例をメモしたりアイディアを共有したりを、かなりスピーディーに進めることができます。この点は競プロに相性がよかったですね。

とにもかくにも、大きな問題なく終えられたことが、素晴らしいです。

個人的には喜ばしいです。

私個人としては、学生時代の終わり頃、初めて競プロを友人に教えてもらい、様々な議論や考察が活発に行われている「界隈の独特な雰囲気」に驚いた、とともに、ある種の尊さを覚えるところもありました。

確かに、競プロの技術が直接に業務の役に立つ機会は、必ずしも多くはないと思います。それでもIT界隈の芽である素晴らしい学生は恐らくこういったところに多く集まっている気がします。「是非、企業の大人たちがこういった学生の盛り上がりを支援してほしい！」と、少なくとも学生当時は思ったものでした。

それがこうした形で、僅かですが、叶ったわけです。それゆえ（会社の総意はともかく）私個人としては大変喜ばしいです。なんか綺麗すぎるまとまり方になりましたが、素直な感想です。

～さいごに～

＜長く拙い記事になりましたが、読んで頂きありがとうございました！＞

関係するリンクなど

・AtCoder
https://atcoder.jp/

・今回コンテストを主催したtraPさん
https://trap.jp/
東工大の「デジタル創作・プログラミング系サークル」とのことです
競プロ以外にも、様々な分野にわたった活動内容となっているようです。

・コンテストの現地参加申し込みフォーム（connpass）
https://connpass.com/event/259774/

・コンテストで実際に出題された問題
https://atcoder.jp/contests/ttpc2022/tasks

おまけ１：ネタばらし

※競プロ経験のない人には難解な可能性がありますが、ご了承下さい

記事前半で例として出した「100万個の整数が書かれたリストが与えられます。この中で、"2つ足して1億を超える"ような数のペアは何組あるか？」の回答例を軽く説明します。

図では簡単のために、整数リストの長さは短めにして、「和が20を超える」で説明をします。説明は試みますが、絶望的に下手くそかもしれません。すみません・・・。

【準備】
まず入力の配列を、昇順にソートしておきます。

ソートは、どの言語でも割と簡単にできます。

次に、少々ややこしい操作をしていきます。

このソートされた配列で、常に、左右の2つの地点を注目し続けていきます。これを左注目点・右注目点と呼びましょう。
2つの注目地点は、図のように、最初は1番左と1番右に設定することにします。

そして次のルールに従って、注目点を隣に移動させていきます。

しかし図のように、
左注目点が移動されるタイミングで、「カウント」をしていきます。
図で言う黄色の吹き出しに相当します。

【ループ終了条件】
注目点をずらしていくと、最後には2つの注目点が隣接するので、このとき処理を終了することとします。

実は、これまでに結果として得られた「カウント」の合計というのは、「10以下の数」と「11以上の数」を足した場合で、和が20超となるようなペアの数、に相当してます。1+3+4+4+5=17、というのがそれです。

あとは「11以上の数」同士を足して和が20超となるペアを数えますが、実は、11以上の数同士を足したら必ず20を超えますから、「11以上の数」の個数をnとして、ペアの数は Comb(n,2) = n*(n-1)/2 通り, と一意に定まります。今回は「11以上の数」が6個とすぐ分かるので、6*(6-1)/2=15通りです。

2つの場合の合計、17＋15=32通り、がこの例での答えです。

全く同様な方法で、「100万個の整数・和が1億超」という設定の問題も解くことができます。

とにかく重要な点としては、「注目点の移動」という操作は、リストの個数分の回数しか生じていません。リストが100万個の整数なら、操作はたったの(?)約100万回です。（もっとも、ソートをする時点で数千万回程度の操作が生じてはいるのですが）

しかし、総当たりだと5000億回の足し算が生じるわけですから、これよりは遥かに短時間で答えが求まることがお分かりいただけるでしょうか。

これはほんの一例ですが、もっとうまい方法(アルゴリズム) は、あるかもしれません。

おまけ２：私の仕事と競プロの関係

おそらく競プロを既にやってる方向けです。

やや一般論になってしまいますが、グラフィクスプログラミングの仕事では、GPUプログラミングが業務の大半を占めることとなります。CPUと大きく異なるのが、その並列度の高さです。

十分な並列度ゆえ、アルゴリズムは、ときに、並列度∞を仮定した計算量評価をすることがあります。この辺りが少し面白く、お話しする価値があると思ったため、ここに追記します。

極論として、GPUプログラミングにおいて考えるのは【並列度∞の下では、各アルゴリズムの時間計算量はどうなるのか？】という話です。

例えば、N個の値が入った配列の最大値を返す操作を考えると、並列化なしの場合は当然ながらN-1回の大小比較が必要です。O(N)というわけですね。

ところが、GPUでは以下のように考えることができます。

きれいにO(logN)ですね。
max演算子、3回分の時間で、答え「21」が得られます。

同様に、長さNの配列に対して累積和配列を返す操作も、以下のような手順でO(logN)です。

少々図は入り組みますが、適切な順序で和を取っていくと、log(N)*2回分の時間で、累積和が格納された配列を得ることができます。

長さNの配列に対しては「ソート」までも、O((logN)^2)で可能です。「バイトニックソート」という有名な方法があります（Wikipediaのリンクを張るに留めます）
https://ja.wikipedia.org/wiki/%E3%83%90%E3%82%A4%E3%83%88%E3%83%8B%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88

このような「GPU計算の効率化」により、グラフィクス表現を"リッチ"にできることも少なくないわけです。

↑例えばこの作品は私も存分に関わりましたが、例えば、流体表現(水や空気の動き)の考える上で、GPU処理高速化の理解は欠かせません。

映像作品の「絵作り」をする上でも、間接的に競プロの考え方が役に立つことがある(比重は大きくないにせよ) のは、少し興味深くはありませんか？