はじめに
この記事は、「競技プログラミングを始めたばかりの人に伝えたいこと Advent Calendar 2021」12/16回です。
お題は、「競プロを始めたときにこんなことが知りたかった、と思うこと」ということで、ここでは特に、データサイエンティストが競プロを始めたらこんなイイコトあるかもよ、的なことを書いてみようと思います。
そもそもデータサイエンティストと競プロ
「データサイエンティスト」で思いつくデータサイエンティスト像は結構多岐にわたって、人によってイメージが違います。いわゆる昔ながらのデータ分析、データ解析の人、データアナリストと呼ばれるような人から、ビッグデータをぶん回しているデータエンジニアリングに近い人、また、機械学習こそがデータサイエンス！という人など、様々。また、分析するだけにとどまらず、その結果を用いた社会実装、例えば最適化計算などオペレーションズリサーチ系にもっていく人や、マーケティング、意思決定、組織論といったビジネスアプリケーション系にもっていく人など、使い方も様々です。
で、自分の周りを見回してみると、意外にデータサイエンティストと競プロerがかぶっていない印象を持っています。ていうか、データサイエンティストにおける競プロer率が非常に少なくみえる！
機械学習系、OR系はそこそこ親和性高くて、競プロerの上位陣（の社会人）にはそういった企業の皆さんが沢山いらっしゃる。一方で、ではデータサイエンティストがみんなそうかというと多分そうじゃなくて、一部のマニアックな人の趣味と思われているんではないかな、と。競プロからみるとデータサイエンティストとして有名企業で働いている人は沢山いて、そういう企業のデータサイエンティストは強者ばかりに見えますけれど、企業で働くデータサイエンティストを分母にするとそこそこレアなのでは？もちろん、そこに目を付けた企業さんは競プロ的スキルセットを持っている人を積極的に採用していると思いますが、一般的な認知はそこまでじゃないんじゃないか。
かくいう私も、データ分析で飯を食ってはや20年以上になりますが、競プロを始めたのは2年前、ちょうどコロナでずっとこもりっきりになったときにAtcoderを見つけて遊び始めました。ただ、OR系の仕事によく携わることがあったのと、出身が数学なので、入口のハードルはそんなに高くなかったろうと思います。
データサイエンスで競プロが活きる場所
データサイエンスで競プロ的スキルが活きた経験は、私個人としてはたくさんあります。整数計画の組み合わせ爆発をどうやって回避するか、ループが何十個もあるネットワークの中からどうやって旨い経路を見つけ出すか、何億行ある過去ログからどうやってアトリビューションパスを効率的に作るか、などなど。計算機を1週間回しっぱなしにしたり、数十台並列で回したりすることも多かったので、リアルを定式化すると競プロの問題になりそうなものがたくさんありました。いや、競プロと言うよりは、「アルゴリズム」と「計算パフォーマンス」の課題です。数千行のサンプルデータでは簡単に計算できるのに、それが数百万行になった途端にうんともすんとも言わなくなる。果たしてそれが30分かかるのか、一晩で返ってくるのか、それとも数万年かかるのか。それが「わからない」では結果が出ませんから、どうやって実現可能な時間で返ってくる問題に仕立て上げるかを考えなければなりません。ただ、それはそういう仕事、高度計算機利用的な業務を私が得意としていたからで、 普通のデータ分析はローカルコンピューターでExcelやRを使ってポンと出るものが多かったです。
しかし、時代が変わってきました。
次では、具体的にデータサイエンスにおいて競プロが活きる場面を拾ってみます。
データの前処理
昔ながらのデータ分析では、データはせいぜい数千～数万。旧Excelで扱える範囲がだいたい限界でした。（当然、当時からテラバイトぶん回していた猛者はいますが、当時はレアケース。）
しかし、2000年代になって急激にデータ量が増えてきました。ビッグデータという言葉が流行り始めたのは2003年頃です。それからはや20年、ほとんど全てのデータサイエンティストは、当たり前のようにビッグデータを取り扱わなければならない局面にいます。すると、こういう分析課題のためにこういうデータを作りたいというスクリプトが、数万行のサンプルでは一瞬で計算が終わるのに、数百万行のデータを入れた瞬間固まってしまう。私も何度もありました。
ここで、もしそれがアルゴリズムで解決できる課題であった場合、知っているか知らないかでは課題解決できる可能性が大きく変わってきます。もし知らなくても、経験値の高いデータサイエンティストなら別の方法（例えばなんらかの仮説を入れてデータを小さくしてしまうなど）で回避することもできると思いますが、アルゴリズムの見直しでも解決できるならば選択肢は多い方がいい。
データ分析課題は、それを解決できるデータが作れた時点で既に解決しています。逆に言えば、解決するだけの情報が無い、もしくは解決に足りる整理がされていないデータをいくらこねくり回しても、「garbage in, garbage out」です。データサイエンティストは課題を解決できる仮説づくり＝それを表現するデータ作りが勝負ですから、そのデータ作りが計算時間の壁によって阻まれているとき、どのように乗り越えるかが試されています。アルゴリズムで解決できることに気がつけば、仮説を完全な形で表現できるかもしれません。逆に知らなければ、不本意な仮説でお茶を濁さなければならなくなるかもしれません。
なお、近年はデータエンジニアが前処理業務を受け持ってくれることも増えてきましたので、「アルゴリズムと計算パフォーマンスに詳しいデータエンジニアがいる」という選択肢もあることを付け加えておきます。しかしそうだとしても、どういう仮説の下にどういうデータを作るかはデータサイエンティストとデータエンジニアが協力して当たらなければならないので、知らないよりは知っていた方が何倍も作業を効率化できます。
分析
データができてしまえば、分析の行為自体は既存のソフトウェアに任せることが多いです。昨今は本当にツールの進化が止まらないので、まっさらから書くことはほぼありません。レアなケースとして、分析手法自体がまだ研究段階だったり、アプリケーションが特殊すぎて自分たちで作るしかないという場合は、計算アルゴリズムから作ることもあると思います。
最適化、機械学習
分析をツールに任せるのと同じように、最適化もほとんどの場合はツールに頼ります。機械学習などの学習アルゴリズムも広い意味で最適化と思ってよいです。これらも最近は本当に優秀なツールが安価に手に入るようになってきたので、ありがたいことです。ただ、最適化はカスタマイズされた制約の影響が大きいので、たまに自分で書いたり、もしくはツールを組み合わせたりなどして、うまく使ってやる必要があったりします。そんなとき、アルゴリズムや計算パフォーマンスのことを知っておくと、自分が取れる選択肢が増えて、イイコトがたくさんあります。
最適化を自分で実装する場合。最適化ということは、なにか原型となるモデルなり数式なりがあって、それをもっともうまい具合に調整する作業になります。調整とはつまり、ある探索空間の中から一つ「最適」なポイントを探し出すことですから、探索アルゴリズムがその中心になります。競プロのビギナー問題あたりでは二分探索の問題が頻出しますが、それのオバケが最適化の問題になっています。
ニュートン法のようなベーシックな方法を使う場合から、極大極小が様々に入り乱れた非線形な場の中でいかにして最大値を見つけるか、パーティクルフィルタやカルマンフィルタなど、また、ベイジアンにしてMCMCを使うとか、どんな方法であってもその裏には必ずアルゴリズムの課題が隠れていて、それをフェーズによって使い分ける必要があります。全く何の知識も無いところにいきなり「○○法」を持ち込んでも、それを実装するのに時間が掛かっていては本末転倒ですから、最初は適当な全探索をぶつけてみたりもします。 さらには、その探索方法選択自体を機械学習によって自動的に使い分けるようなこともあるかもしれません。
それらすべて、どのように効率的なアルゴリズムを組むかにかかっているので、裏で考えているのは、問題をどのように定式化して、どのように実装すると、時間内に思うような探索ができるか、ということで、これはまったく競プロ、特にヒューリスティック系のコンテストで考えていることと同じです。但し、制限時間は競プロと比べてたっぷりあるので、多少のムダがあってもなんとかなります。
二つ目はツールを使う際です。ツールを使うのだからあとはお任せでいいじゃん、ではありません。ツールは最大公約数的な使い方を想定して作ってあることが多いので、それから外れる使い方をしようとしたときに思わぬ落とし穴に嵌まることがあります。そのとき、これはツールの問題なのか、データの問題なのか、計算パフォーマンスの問題なのか、それらの問題点を想像し、解決の糸口にたどり着くために、競プロの知識や経験が活きます。経験したことのないことは想像できませんから、競プロで毎回出題される問題に苦労して経験値を積み重ねておくことは、この想像可能性に大きく影響してきます。
実際、あるライブラリの挙動がめちゃめちゃ遅いとき、もしかしたら？と思ってデータの持たせ方変えてみたところ一瞬で計算が終わった、ということがありました。また、世界的に名のあるソルバーを使ってもどうしても現実的な時間で答えを出せないのに、別のあるローカルソルバーを使ったら一瞬で準最適解までたどり着いたということもありました。ツールには向き不向きがあって、一番よく想定されている問題に一番適した計算方法になっています。ツールの解説書だったり、ツールを構成する元論文だったり、場合によってはツールの挙動を様々なテストデータで試したりして、ツールがどのように動いているのかをイメージし、課題をそれにフィットするようにうまく合わせてあげたりすると爆速になったりしますが、その想像力の元ネタとして競プロでの経験値は非常に役立ちます。
最適化の課題設定と定式化に必要なスキルはデータサイエンスだけでなく、また一方でアルゴリズムや計算パフォーマンスだけでもありません。そのほかにも、ビジネス経験や、様々なデータを見たり扱ったりした経験も活きます。ある種の総合芸ですので、経験値があればあるほど効果的、効率的な最適化ができます。
競プロ以外にあったらいいスキル
さて、ここまではデータサイエンティストにとって、競プロ的なスキル、つまりアルゴリズムと計算パフォーマンスがどう活きるかを見てきたのですが、データサイエンスは総合芸ですから、競プロではあまり出てこないけれど重要なスキルがあります。それをご紹介します。
コンピューターの仕組み
これは競プロの延長線上にあると言ってもいいかもしれません。 必ずしも競プロで考慮することではないですが、上位陣はおそらく意識していると思いますし、情報オリンピックレベルの皆さんはおそらくコンピューターサイエンスの授業で習っていると思います。トランジスタ、IC/LSIがどうやって動いているかとか、CPUが周りのデバイスとどう通信しているか、命令のスケジューリング、など。
また、ソフトウェアの面からも、C++やPythonがメモリをどう使っているか、コンパイラの果たす役割、最適化のされ方など。たまに競プロでも、巨大なメモリをアサインする際に「どちら側でまわすか」が議論されていたりしますが、メモリとキャッシュをどう使うと効果的か、という話です。そこまでカリカリにチューニングしなくても、例えばメモリのスワップが入ると劇的に遅くなるとか、ツールがメモリをこうやって使っているからメモリが足りなくなるとか、コンピューターやOS、ソフトウェアがどのような仕組みで動いているかを知っていると、改善の選択肢が増えます。
あとは最近だと、GPUなどアーキテクチャの異なるプロセッサをどう使いこなすかという課題もここに入るかもしれません。
並列計算
計算パフォーマンス改善のもう一つの手段として、並列計算が挙げられます。アルゴリズムによる改善は場合によっては劇的ですが、並列計算の改善はせいぜい線形、悪ければもっとサチります。それでも、100日かかる計算を100台並列で動かして1日で終えたり、30分かかるクエリが1000並列3秒で返ってきたりと、並列計算はパフォーマンス改善の手段として、ある種の問題にとっては確実に計算時間を短縮し、現実的な時間に計算を終えるための選択肢です。
このとき重要なのは、その問題は並列計算可能か？ということを見極めること、もしくは、問題を変形して、並列計算ができるような形にすることです。並列計算の中でも最も単純な分散計算（計算どうしがデータのやりとりをせず、個別の小さい問題を組み合わせるだけで解決する、つまり協調計算でない）問題にできれば、CPU数に対してほぼ線形に計算時間を短縮することができます。つまり、10台使えば計算時間は1/10に、1000台使えば1/1000になります。MapReduceなどもそれ系ですね。
MCMCのように一つ前の計算結果を参照する定式化をしてしまうと、一つの系列をそれ以上分散させることができません。複数系列を同時計算することはできますが。一つの系列に長時間かかるようであれば、例えばモンテカルロのように完全分散化してしまった方がいい場合もあるかもしれません。もちろん、様々な方法が論文等でも提案されていますから、それらを理解するためにも、並列計算の知識はあった方がいいです。
競プロには並列計算の話はほぼ出てこないのですが、「問題をどう定式化すると現実的なリソースで解けるようになるか」を考えるところは思考方針として非常に似ています。
クラウド利用
上に書いた全てのことを、現代ではクラウド無しに実行することは非常に困難です。100台の並列計算をしたいと思ったとき、クラウドではボタンをいくつか押せば直ちに100台のマシンを調達することができ、それが動き始めますが、これをオンプレでやろうとすると半年はかかります。このデータを分析したい、それには100並列で1週間かかる計算が必要、となってから機器を購入して、データセンターを予約して、納入されたマシンを接続して、OSをインストールして・・・気が遠くなります。
データも、いまはローカルにダウンロードすることすら困難な量のものがクラウドならけっこう簡単にやりとりできます。 HDDにダウンロードするのに一日、運搬に一日、コンピューターに入れるのに一日、なんてことは（うまくデータの流れを作れば）ほぼありません。
データベースは2012年に Google の Big Query が世界を変えました。少なくともデータサイエンス、データエンジニアリングにとっては、もはやそれ以前には戻れない画期的なサービスです。もちろんそれまでも、限られた人たちだけが使えるすごいサービスはあったかもしれませんが、一般向けに、誰でも使える巨大なデータベースサービスが、驚きの価格で提供されたことが革命的でした。
これからのデータサイエンスは、クラウドをどう使っていくかということと切り離せなくなってきています。
どのようなスキルセットを持つか
と、データサイエンティストはあれもこれも全部必要！という話になってしまいましたが、実はこれらすべて、ほどほどでいいです。
全てに精通している人は・・・もちろんいないわけではないですが、めちゃめちゃレアです。そしてデータサイエンスは属人的なワークなので、そのレアな人が全ての仕事をかっさらっていくことは不可能です。いきおい、できる人が、できることに、できる範囲で取り組むことになります。
仕事は中ボス攻略
ドラクエを想像するとわかりやすいと思います。中ボスを倒すのがミッションで、そこに至る過程に様々な障壁があります。あるときは魔法で、あるときは剣で、あるときはアイテムで攻略しなければなりません。そこで自分のステイタスを見てみると、沢山のアビリティが並んでいるのですが、その中に「競プロの部屋」でトレーニングできる「アルゴリズム」と「計算パフォーマンス」があります。もちろん、「数学」や「統計学」もありますし、「ビジネス」（はもっと細分化されていますが）や「システムエンジニアリング」、「クラウド」などもあります。
データサイエンスは総合芸ですから、それら全てのスキルをどのような配分で持っているか、と、あたる中ボスの特性とを見比べて、どうやって攻めるか、もしくは他の人に託すかを考えます。そしてその中ボスは、沢山います。世の中に様々なビジネス課題があって、それらがデータを抱えて待っているので、仕事は今のところなくなる気配はありません。しかし、自分がどういうスキルセットをもっているか、この先どのようにそれを伸ばしていくかということと、将来攻略する中ボスとは相関します。簡単に倒せる中ボスは早晩枯渇しますし、人数の多いスキルセットで倒しやすい中ボスも競争が激しくなるでしょう。
単品勝負の人はけっこう多いです。多くのアビリティの中で一つだけSやSSを持っている人が結構いるのは、大学教育がそうなっているからです。一つ一つのアビリティではSSの人は少ないのですが、アビリティがたくさんあるので「一つだけSS」の人が多くなります。他方、攻略する相手、ほとんどの中ボス攻略には複数のスキルが必要です。一つのアビリティだけで攻略できる中ボスはほとんどいません。ではどうするかというと、一人で複数のアビリティが強い人が攻略するか、チームで攻略するかになります。
自分の特色の作り方
さて、ここで面白いのは、攻略する中ボスにどのスキルセットが必要なのかが、事前には分かりにくいことです。SS単品の人が仮に当たってみても、攻略の糸口は見つかりません。SS周辺はわかるのですが、他のアビリティが低ければ、相手の強さを見積もれないからです。ではSSを沢山集めたチームを作ろう、と言っても、相手の攻略方法を見つけるPOCの段階でドリームチームを動かすのはコスト的にも時間的にも非常に難しい。
ですから、総合芸であるデータサイエンスの「現場」では、SSを一つも持っていなくとも、多くのアビリティでA持ちとか、複数個Sを持っていて残りはBなどという人の方が仕事を回しやすい。そういう人が中ボスの攻略方法にあたりをつけて、自分ひとりでできればちゃっちゃと片付けますし、自分のスキルや時間が足りないなぁと思えばSSの人を連れてくればいい。中ボス攻略のプロジェクトマネジメントができます。
データサイエンティストの方ならばおそらく、数学や統計学のアビリティはA以上だと思います。また、既に現場で活躍していらっしゃる方なら、その分野のビジネスにはかなり精通していらっしゃるので、それもA以上だと思います。そこにもうひとつ、アルゴリズムと計算パフォーマンスでAを持てば、攻略できる中ボスの範囲がぐっと広がります。私の体感として、データサイエンスで必要とされるアルゴリズムおよび計算パフォーマンスのAはAtcoderの緑～水色、Sは青くらいだと思います。実際、私が水色の真ん中くらいを行ったり来たりしているのですが、データ分析の実務で使うにはそのくらいあれば大抵のことができます。
そして冒頭にも申しましたが、データサイエンティストを分母として見回したとき、「アルゴリズム」と「計算パフォーマンス」でA以上の人はかなり少ない印象です。コンピューターサイエンスからデータサイエンスに入ってきた人たちはもともとSやSSを持ってくるのであまり見えないかもしれませんが、何度も言うように総合芸ですから、いろんな入口の人がいて、様々な仕事をしていて、その中でこの二つのアビリティが強い人はなかなかに少ない。そして、ビッグデータとクラウドの時代になって急激に重要性が増している。ということは、「アルゴリズム」と「計算パフォーマンス」のアビリティを「競プロの部屋」で修行して、AやSレベルに上げられれば、できる仕事の幅が広がり、アウトプットの質も高まり、世の中から必要とされるデータサイエンティストにまた一歩近づけるということになります。
おわりに
ということで、データサイエンティストが競プロ始めるとこんなにいいことがたくさんあるよ、ということを書きました。
実際に私が2年前から始めてみて、その経験値が具体的な仕事の課題解決に結びついたことが何度もあります。それまでもある程度の知識はあったので、やればそれなりにできると思っていましたが、皮算用のフェーズと具体的に自分がやってみたフェーズとでは想像できる広さとスピードが全く違いました。
いきなりコンテストは・・・と躊躇するなら競プロの典型例題を集めた「典型90」にチャレンジするのもいいですし、それはハードルが高いと思う人は、「アルゴ式」という入門編サイトも最近立ち上がりました。統計における統計検定がフリーで開催されていると思えば良いです。（そうか、統計でもそういうサイトを作ったら面白いかも・・・）あとは、自分が門を開くかどうかだけです。具体的な入門方法は他の方が本カレンダーで沢山解説頂いているので、そちらにお任せします。
最後に。実はこの話を書いている途中で、「あれ？もしかしてこれを書いてしまうと、自分の競合相手を育ててしまうことになるのでは？」と、ちょっと思いました（笑）。自分が統計×数学×計算の領域で飯を食っているので、同じスキルセットの人が増えてしまうと競争相手が増えてしまう・・・。でも、いやまてと。新しい人の流入が無くなってしまったジャンルは早晩潰れます。データサイエンスの世界が常に勢いがあって、スリリングで、活気に溢れるコミュニティである方がいい。その中で、自分が後進に脅かされはぁはぁ息を切らして追い抜かされる方が絶対に面白い。競プロの世界で、自分の子供と同じかそれより若い人たちにまったく敵わない、瞬間過ぎて背中も見えないくらいぶち抜かれて真っ白になるのを毎週経験していたら、未来はもっと面白いなって思えますよね。
