More than 1 year has passed since last update.

Houdinist が競プロerになってみた話

Last updated at 2023-09-17Posted at 2023-09-17

執筆にあたって

Houdiniという 3DCG ソフト と 競技プログラミング のどっちも好きなひと（好きになれるひと）って私は結構いると思うのですが、業界が違いすぎるのかそういった記事を一つも見つけられません。ゲーム会社がコンテストのスポンサーをやっていたりするので、少しずつ繋がっていくのかなぁとも思いつつ、ゲーム会社内部で広報や人事、あとはアーティストと開発も距離が近くある必要があったりするのかもしれません。

私は仕事柄日本全国の CG プロダクションを訪問して人事やアーティスト、エンジニアとも話をするのですが、その中で競プロの立ち位置を考えたときどう感じたのか、実際どうなっているのか、最低限競プロを頑張っていると言えるくらいになったのでいわゆる 色変記事 という文化に乗っかって色々書いてみることにします。

あとたまに聞かれることとして「仕事のためにやってるんですか？」というのがありますが、完全に趣味です。

Houdinist 向け「競プロってなに？」

競技プログラミングの略です。問題文とその入力があって、それに対する正しい答えを出力するプログラムを書く競技（というかゲームというか）です。専用のウェブサイトにプログラム（ソースコード）を提出すると自動で合否が判定されます。

以下の問題は、AtCoder 社 (競プロ界でとても有名な日本の会社) の「AtCoder Biginner Contest 137」の一問目です。

つまり最も簡単な問題の一つです。AtCoder では基本的に毎週土曜日の夜にコンテストが開催されているのですが、そこでの成績に応じてレートがつきます。そこそこまともに努力しないと到達できないレートになったので、今回こうして記事を書いています。（一種の文化みたいなもんです）

「競技プログラミングって敷居が高そう」という意見を時々もらいますが、実はそんなことはありません。実際、先ほどの問題は「ちょっとした計算をして、その中でどれが一番大きいのか」を答えればよいので理解するのは簡単です。もちろんプログラムが書けないといけませんが、例えば Houdini でも使える Python だと以下のように書けます。

ABC137A.py

A, B = map(int,input().split())
print(max(A * B, A + B, A - B))

たった二行書ければもうスタートには立てています。 コードに出てくる print, split 等を少し検索すれば、大体何がどうなっているか理解するのは難しくないでしょう。

正しい出力さえできていれば多少コードが違ったりしても問題ありません。また Python 以外でも C++, Java, Brainf**k など実に様々な言語が利用可能です。

たとえば C++ だと次のように書けば正解になります。

ABC137A.cpp

#include<iostream>
#include<algorithm>
int main(){
  int A, B;  std::cin >> A >> B;
  std::cout << std::max({A+B, A-B, A*B}) << std::endl;
}

Python より少し行が増えましたが、書き方が少し違うだけでなんとなく同じことをしていると直感的にも理解できるのではないでしょうか。

例えば Unreal Engine は C++ を使うので、いろんなことが息をするように書けると便利です。Unity ユーザーなら C# で競プロをしても良いかもしれません。（残念ながら VEX はありません）

「そこそこ努力しないと到達できない」ってどんなレベル？

比較的意味が分かりやすい問題だとこんな問題があります。

最初、1 という数字を持っています。普通の六面サイコロを振って、出た目をかけていきます。例えば 2, 3 と出たら持っている数字は 6 になります。
ゴールとして、適当な数字が与えられています。下手な出目だと、うっかりゴールの数字より大きくなってしまうこともあります。ピッタリ同じ数字になる確率はいくらですか？

競プロ未経験であれば、結構数学が得意でないと、何から始めてよいのかすらわからないかもしれません。仮に方針が定まったとして、そこそこプログラミングに慣れていないと、結構時間がかかるかもしれません。コンテストでそこそこな成績を出そうと思ったら、この前のあと四問含めて、100 分以内での実装が必要です。しかも偶然一回だけそれができてもまずこのレートになることはなく、安定的にそれができるかより早く達成できるかのどちらかが必要です。

競プロer 向け「Houdiniってなに？」

たぶん公式サイトにあるカスタマーリールを見るのが一番わかりやすいです。
カナダのトロントに本社を置く SideFX 社が開発するハイエンドな 3DCG の制作ソフトです。有名なハリウッド映画から、PS5 や Switch のゲーム、建築や科学技術用途のビジュアライゼーションまで、誰もがほぼ確実にこのソフトで作られた CG を（CGとすら気づかないものも含めて）観ています。

あとで詳しく言及しますが、競プロer には一番向いている CG ソフトな気がします。大きなハリウッドのプロダクションは、巨大な爆発や大滝のために、（十中八九）Houdini 用に大規模な一体型流体ソルバを自社開発していたりもします。

この動画によると、60億ボクセルくらいの単一疎ボリュームの圧力場の解決が求められているようですが、競プロがどこかしら役立ちそうな数字ですね。

ちなみに私は Houdini を使ってハイエンドな CG を作ったり、アーティストやエンジニアそれぞれの要望や質問に答えるような仕事をしています。
例えばこれはちょっと前に私が作った CG の草とか花とかです。100% 手作業はしんどいので、うまいこといい感じなシステムを作って生成したりしてます。そんなことをしてる人です。

水色になれました🍥

競プロに詳しくない Houdinist 向けとして、色に対する実力の雰囲気は AtCoder の社長である chokudai さんのブログを読んでみると良いでしょう。詳しいことはわかりませんが、AtCoder のレートは相対評価なので、新規の増加や過去問の蓄積により年々少しずつ難化しているようです。上記のブログも最終更新が約一年前なので、人によっては少し違う感想をもつかもしれませんが、私の体感は大体あっている気がします。しいて私が思うことを挙げるとすれば、たぶん水色レベルでも競技プログラミング未経験者が戦うことは結構無理があるきがします。

参考までに、私は不登校学歴コンプ持ちです。ほぼ小卒です。アルゴリズムなんて大して勉強したことはありませんでした。なんとなく現在までの流れを振り返ってから、詳しい精進の記録を連ねることにします。

はじめたきっかけ

運が良いことに、私には Discord で通話したりリアルでも会ったりしている黄色コーダーの凄い知り合いがいます。あるとき私がバケツ塗の画像処理のコードで混乱していると、三分くらいで高速化してきたので、何をどう考えているのか聞いてみると 「判定するとこミスってたから $O(N^2)$ になって 4K とかだとだいぶ重くなるけど、$O(N)$ にしておいたからまぁ 8K でもいける」 くらいな返しをしてきました。今ならそれは茶色レベルの BFS 典型であることは言うまでもないのですが、当時は大変驚いて色々聞いた結果、いつの間にか競プロをやることになっていました。

最初はそこまでのめり込んだわけではありませんが、後述のようにいつの間にかかなりの本を短期間に読むことになります。

水色になるまでにやったこと

期間の割にちゃんと書き出すと以外にも量があるので、まずはやったことを整理して、その後で実際どのように進めたのかに触れます。

AtCoder の過去問

コンテスト参加回数は 28 回、ほとんど ABC です。仕事が忙しくて今年の前半は何もしていなかったりもしているので、何とも言えない回数です。初めてコンテストに出たのは二年くらい前ですが、二回目はその約一年後なので、精進期間は実質 $\frac{3}{4}$ 年くらいです。AtCoder Problems によると、Streak Sum は 267 日、Accepted は 1847問だそうです。

基本的に AtCoder Problems の Recommendation と ABC-E までの完答率を上げるために ABC-E までをやった結果です。灰茶が埋まってないのは常に現在の色未満はほぼ解いていないからです。Recommendation に出てくるものだけは試験管問題 (AtCoder 初期の古い問題) だろうと基本全部解くつもりでやってます。Median Solve Time が出ているので、それを基準に考えてもわからないなら解説を見ます。

解説を見てしまった、Median Solve Time を超えてしまった、自力で解けたけど解説の方針の方がずっと優れているなど、自分の中で納得のいかなかった場合は基本的にすべてノートに書いています。（どうでも良いですが紙派です）つい先日四冊目に入りました。ほとんどの場合一問１ページで書いているので、ざっくり 180 問程度そのような問題があったことになります。ちなみに今回入水したコンテストの C 問題は公式解説通りの解法をコンテスト中に実装しましたが、パッと思いつかなくて一旦 D に進んでしまった、evima さんの解説の発想がなかったなどの理由ですでにノートに書きこまれています。

公式のウェブサイトの解説だけではなく動画がある場合はしっかりチェックしています。特に ABC は実装までしてくれるので大変ありがたいです。個人的に動画に見出している価値は以下の二つです。

ウェブサイトとは少し違う方針やアプローチが見られる
世界レベルのひとの考えが聞ける

一つ目は毎回ではありませんが、文字はどうしても厳密さ重視なので直感的にわかりにくいことが多々あります。一方で動画解説では最低限厳密さは確保しながら細かい点はウェブサイトにまかせることが多いので、イメージやお気持ちのような部分を聞けることが多いと感じます。
二つ目は単に世界レベルの人間の解説を聞けるという意味ではなく、個人的には 細かいちょっとした発言を集めています。 公式の解説放送は snuke さんが担当しています。彼は銀冠なので、chokudai さんの言葉を借りると「頭のおかしい人」です。「これは部分和っぽい構造を含んでいるので全探索ベースしかないと思う」「NIM和のような天才的発想は普通のゲーム系とは別」など、動画だからこそ出てきそうなちょっとした言葉は他の問題にも役に立つことがあります。

AtCoder での過去問精進は大体そんな感じです。むしろ本格的に過去問を埋め始めたのはつい数か月前なので、次の本の話がもっと重要かもしれません。

本

競プロ目的で読んでみた本の一覧です。ほとんど本は読んでこなかった人間なので、小さな本棚がほとんど競プロ関連の本で埋まりました。ありがたいことに、好きな本を読むペースに合わせて買うくらいのお給料はもらえているので、読みたいと思ったら割とすぐ買っています。

多いですが一つずつコメントを付けます。

問題解決力を鍛える!アルゴリズムとデータ構造

例の黄色コーダーに最初に勧められた本です。著者の大槻さん（通称けんちょん）自身も黄色コーダーです。今思えば競プロの言葉や慣習、問題などがかなり多く登場した気がします。一方でしっかりとランダウの$O$記法の定義、いくつかのソートアルゴリズムの計算量解析、最後には $P \neq NP$ 予想やそれに伴い充足可能性問題への帰着など、コンテスト中深く意識しないようなことも載っており、必ずしも競プロ入門のためだけではない本であることが読んでみるとよくわかります。
読みやすさと厳密さのバランスが私にとっては最初の一冊としてはかなり良かった気がします。

この本ははじめて競プロの勉強をしようと思って買った本なので、かなり長い時間かけて読んでいます。

はじめての情報理論

これは情報理論の本なので、競プロとは特に関係がありません。コンピュータに関わることは確かなので、知っておいて損はないと思いますが、競プロ目的なら無理に読むことはないと思います。$\Sigma$ とか $\log$ 確率とかは当然頻出なので、苦手だったら読んでおくと耐性はつくかもしれません。

問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本

競プロで最低限戦うためのアルゴリズムと数学が詰まっています。著者のE869120 さんは赤コーダーなので、当然といえば当然の話です。
AtCoder に演習問題のジャッジ（自動採点システム）が常設されています。 最後の未解決問題を除きすべて AC しました。ちょうど 100 問くらいですが、しっかり理解しながらこれだけ幅広くやれば、さすがにまったく伸びないということはない気がしてくる分量です。
これを完了したあたりから明らかに競プロ始めたてとは違う感触を感じ始めます。

パズルで鍛えるアルゴリズム力

競プロの本ではありませんが、単純に面白いです。勘で適当にやっていたようなことが少し一般化されて頭が整理された気がします。Computer Puzzling という言葉がある気がするのですが、そんな感じです。

余談ですが、頭が整理されたので、ルービックキューブを解析するツールを後で作りました。二回繰り返すともとに戻る手順です。初期状態からかなり遠く、見た目の動きが面白い手順というのがポイントです。

L2 F U' R2 F' R2 B2 L U B' D2 L' F' U' D' F2 U' L2 F2 D

ごまかしなくループするアニメーションが作りたくて解析しました。指数的に状態数が爆発するのが問題なので、少ない種類の操作で揃えられる状態を中間ポイントとして、半分全列挙的な考えで高速化するのがよくある手だそうです。

こっちは一回で元に戻る手順です。何か手品とかに使えるかもしれませんね。

R' F2 D2 L B2 L' R D2 L' F2 U2 L

アルゴ×数学本でいかに鍛えられたかがわかる感じです。解析パートは C++で数日かかっていますが、ビジュアライズのリグは Houdini で、それに限っては高々数時間で完成させています。あとで競プロとCGテクニカルの関連を書くつもりなので、そっちでもう少し触れます。

ルービックキューブの状態遷移が生成するグラフはもっと複雑ですが、イメージはこの問題とかです。

情報工学アルゴリズム (東京大学工学教程)

知り合いもけんちょんも東大卒ということで、なんとなく読んでみることにしました。やはり授業で使う目的だからか一人では若干読みにくいところもある気がします。一部の文字列アルゴリズムとメタヒューリスティックの項以外はほとんど使っているので、読んでおいて損はないです。

アルゴリズム的思考力が身につく! プログラミングコンテストAtCoder入門

主にAtCoder の ABC の過去問をまとめた本です。難易度としては、とりあえず全部身に着けたら確実に緑にはなる雰囲気です。アルゴ×数学本をすべて終わらせてからだと、簡単な問題が多いかもしれません。

競技プログラミングの鉄則

言わずもがな競プロ専用の対策本です。専用なだけあってカバーされるレート帯と本の読みやすさが素晴らしいです。ただ本当に競プロに特化しているので、ついでに周辺の色々まで学びたい場合は先述の本をいくつか同時に進めても良い気がします。ちなみに著者はアルゴ×数学本と同じ E869120 さんです。
AtCoder に演習問題のジャッジ（自動採点システム）が常設されています。 一部の未解決問題等を除きすべて AC しました。

余談ですが、今回入水したコンテストの F 問題は設定が本書の問題集のこの問題に酷似しているのはわかっていました。似たような解法が適用できるかは別として、結果解けなくて悔しい思いをしているので、併せてもう一度よく考える予定です。
こんな風に、一通りやると結構な頻度で同じようなパターンに出会うことがある気がします。

アルゴリズムイントロダクション

世界的に有名な教科書です。ここに上げる本では一番詳しく、そして網羅的といえるのではないでしょうか。本題の最初では使用する実現技術のモデルについて言及されていたり、他の本で少し気になったポイントの多くが載っていました。実際、本書７ページには

本書はアルゴリズムの"百科事典"として使うことができる

とありますが、赤黒木の実装に際して文献を探していたところ、本書に 2色木として非常に詳しい説明がありました。（なぜ実装をしようとしたのかは後述）

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

AOJ (Aizu Online Judge) の問題に沿って競プロ目的でアルゴリズムとデータ構造の基本を学ぶ本です。AtCoder の ABC よりずっと基礎的典型的な事項が多く掲載されています。応用問題以外は問題のストーリーも特にないので、本当に純粋な典型的操作やアルゴリズムが競プロ目的で学べます。ACL (AtCoder Library, AtCoder のみで使える便利なライブラリ) は当然使えないので、最低限必要な実装力も身につくかもしれません。

プログラミングコンテストチャレンジブック

非常に網羅度が高い競プロ専用の本です。全部身に付いたら確実に青には届きそうなレベルですが、その分話も速く残念ながら競プロ未経験者で読み切れる人は少ない気がします。まだ三割くらいしかチェックできていませんが、ナップザック一つとっても高々数ページに様々なバリエーションが詰め込まれていたりします。

この問題 (ABC E - Wish List) は、「商品を最小費用で手に入れる」というかなり最適部分和的な雰囲気を含んでいますが、また同じ場所に置かれるほかの問題と比べてだいぶ難易度が高いですが、本書での経験のおかげか自力 AC しました。

その他よく見ている（た）資料等

けんちょんの競プロ精進記録
- 初めて読んだ本の著者が彼なので、その影響もあってか読みやすいです。 そのうち会って本にサインをもらうのが小さな目標です。(けんちょんさん相互フォローだし実は共通の知り合いがいるのでよかったらごはんとか)
cppreference.com
- C++ で競プロをしているので、当然よく見ます。std::deque はランダムアクセス $O(1)$ とか小ネタを知っておくと、両側から入れて構築したいみたいな問題とかで実装が楽になったりします。一方で使い勝手だけみると std::vector の完全上位互換な気がしますが、std::deque は色々ポインタ管理をして実現したりしているので、一般に std::vector の方が（オーダーは同じでも）ランダムアクセスが速いとかいろいろ書いてあって面白いです。
C++ : The Cherno
- 全部見ました。元有名企業のゲームエンジンの開発者のようです。非常に深い話をしてくれるので、いわゆる業務プログラミングではやってはいけないけど競プロだとやるみたいなそれの理解に役立ったり、純粋に言語への理解が深まります。これを全部見ればコンパイルエラーやワーニングがわからないことはほぼなくなるのではないでしょうか。
Reducible
- とても分かりやすいアニメーションで有名なアルゴリズムが解説されています。全部見ました。少し更新が止まっているのが悲しいです。
アルゴ式 (Beta)
- 最近コンテンツが増えて、データベースやセキュリティなど競プロでは使わなそうなものも含みますが、競プロパートはすべて AC しました。「絶対にコピペはせずすべて書き直す」という自分ルールで取り組んでいたので、これが終わるころには BFS, DFS, 典型的 DP など何度も書かされるアルゴリズムは息をするように書けるようになりました。派生してダイクストラ等頻出なアルゴリズムも書けと言われれば息をするように書けるレベルになります。

これから見ようと思っている資料等

マスター・オブ・場合の数 : 栗田哲也 (著), 福田邦彦 (著), 坪田三千雄 (著)
- 場合の数やそれに伴う確率や期待値、数え上げが比較的弱いことを実感しています。高校、大学受験の勉強をまともにしたことがないせいかもしれません。
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 / プログラミングコンテストチャレンジブック
- 前述の通りすでに手元にあり、競プロ目的で次に読める日本語書籍はたぶん他に探してもあまりないはずです。

精進で気を付けていること

やっとここまでの精進の流れが追えたので、次は実際の精進中にポイントにしていることなど内容以外のことを少しまとめます。

1. どんな問題を解くべきか

色んな意見があることは知っています。「自分のレートと同じくらいのやつを解け」「一つ上の色も解け」「色やレートではなく目標にする色に必要なところ（たぶん水色なら E まで）を解け」大体どれもそれはそうと思ったので、Recommendation を基本にしつつ飽きたら ABC-E くらいまでを解いていました。ABC-E の対策は ABC-E の過去問が一番だろうと思ったのでそうしていただけで特別な理由はありません。（どうせそのうち全部やるくらいの気持ちでいます）

本に載っている演習問題は、大体先に前提知識の解説があるので、たまに応用問題で詰まるくらいで基本的には良いペースで進むので気持ち的には楽です。応用問題で詰まるときは、そもそも知らないことを知るために本を買っているつもりなので、ある程度考えたら積極的に答えを見ます。答えを見ずに AC してしまうと、解説を見なかったりしてしまうこともあると思いますが、それでは本を買った意味がないので本の解説は必ず読みたい派です。

2. 記録する問題、しない問題

ノートにまとめるかどうか、まとめるならどうまとめるかという話です。現状解いた問題数は、 AtCoder 上で 1800問ちょっと、アルゴ式や AOJ を含めると 3000 問に届かないくらいです。このうちノートに記録されているのは、主に AtCoder の問題で、約 180 問です。最近は、水,青の問題が多いですが、最初の方は場合分けを min,max で簡潔にするような A 問題や茶色レベルの典型的な dp や少し複雑になる実装なんかも載っています。基本中の基本なのにあまりに苦手だったり悩んだ AOJ の問題も数問あったりします。

最近は ABC-A,B を除きほとんどすべての問題の何かしらが記録されています。（ちょっとした実装のポイントだけとか）

実際のノート

仕事柄 Houdini という結構難しい部類のソフトを扱っているので、よく勉強法を聞かれることがあります。ついでといってはなんですが、競プロに限らず何かを学ぶときは大体同じような形式でノートをとります。

ここまでの流れだとだいぶ几帳面にきれいにまとめてそうな感じかもしれませんが、実際のノートの字は雑です。（誤解されると嫌なので、ちゃんとした書類はきれいな字を書きますというのだけは言っておきますが）個人的なノートを別にきれいな字や図で書こうというつもりもありません。主な理由は二つです。

自分しか見ない
目的は「自分の考えを記録したり記憶を定着させること」であって「きれいなまとめノートを作ることではない」

一つ目はどうでもよいとして、二つ目が大事です。見ての通りすべてボールペンで書いていて、ミスしたら上から雑な修正をしています。これは 間違えたところを残したいから です。似たような間違いを何度もしていたり、あとから見返して勘違いしていたことが記録に残ります。個人的にはこれが一番大事です。この時字は自分が読めれば十分なので、できるだけ早く考えを出力するために最低限読める程度の品質です。

デジタルでとらないのは、単純に好みの問題です。紙なら軽くて電源不要です。今四冊目ですが、大体どこにどんな問題を書いたのかは覚えているので、ここまでに出てきた「あんな問題こんな問題がある」という言葉はノートに書かれていてすぐに思いついた問題たちです。

類題等の関連情報もしっかり記録しています。先日の ABC314 は E 問題は少し難しかったようですが、ノートに類題を記録していたおかげで、しっかり立式から式変形して通せました。

3. ライブラリの整備について

これは完全に「コンテストで勝つことより自分のものにすることが優先」という自分なりのルールに基づいているのですが、「とりあえず一回自前実装」 を大事にしています。modint にしても segtree にしても初めて使いたくなったら必ず一度頑張って実装します。

これは C++ の STL も同様です。STL は Standard Template Library なので仕方ありません。
まず std::vector (可変長配列) が使いたいので、new, delete と生配列を駆使してなんとか stk::vector を作りました。（stk は Satsuki の略）可変長配列はサイズが足りなくなるとより大きな領域を確保してコピーされますが「コピーが $O(N)$ なのになんで $O(1)$ ってことになってるんだろう？」みたいな疑問や「ABC 310 D の解説 1 の 47 行目の reserve がないと壊れるけどなるけどなんでだろう？」みたいな細かいことがとてもよくわかります。

そのうち std::set, std::map が使いたくなってきたので、これも仕様を調べて実装しました。内部的には赤黒木と呼ばれる強平衡二分探索木により、追加・削除・検索を対数時間で実現しているそうです。先ほど後で述べると書いた実装の理由はこれです。一応ハッシュセットに相当するものも作りましたが、AtCoder だと言語間の差を小さくしようと努力してくれているおかげで C++ だと log がついてもほとんど問題ないことからほぼ使っていません。

そんな調子で queue, stack, list などなど、競プロならほとんど std が stk にできるくらい実装しなおしました。

しっかり範囲for文にも対応させるため各データ構造は対応したイテレータも持っています。
これをやっておいたおかげで、set の lower_bound と vector の lower_bound で書き方が違うのにも納得がいきました。
詳しくは、random_access_iterator と bidirectional_iterator について調べてみるとよくわかります。

4. 一問からどれだけ得られるか

解けないとき、ただ解説をみて実装して理解して AC するのはさほど難しい話ではありませんが、ABC は典型を詰め込んだようなコンテストです。ほかの問題にも応用できるようにできるだけ大事な部分だけ切り分けて理解したいです。そんなとき何をしてますかという話です。

解説の writer 解に疑問を持つ

よくあるのは dp の初期値の INF や二分探索の範囲ですが、できるだけ強く範囲を見積もって、ギリギリのラインを狙って何度か提出したりしてます。コンテスト中そんな危険なことはしませんが、というか ABC では中々そういった意地悪はありませんが、たまにしっかり範囲を絞らないといけない問題があったりします。先日の D 問題は良い例だと思います。

例えばこの問題は writer 解が極端な -INF を設定していますが、これをもっと強く見積もってみたりします。コンテスト中にそれをする必要は特にありませんが、もうマイナスが逆転できないギリギリを狙って立式、式変形したり、そのラインを二分探索してみるとそれだけで色んな練習ができます。

テストケースを考える

半分ノートに書く都合なのですが、WA を出したときに何が悪かったのかはっきりノートに書きたくて、コーナーケースを考えることが多々あります。特に古い問題はテストケースが公開されていなかったりするので、自力でなんとかしています。
ARC, AGC の方が場合分けやコーナーケースが多い印象なので、最近は意図的にそっちの難易度低めの問題を解いたりもしています。

より簡潔な書き方を考える

やはり長いコードになるとバグらせがちです。bit 演算を駆使して補集合の部分集合列挙とかいろんなパターンを for 文が一行で書けるような小ネタをコツコツ集めてたりします。そういった小ネタは一ページとる必要がないので、ノートを逆のページから使っています。

一方で短くなればなんでも良いわけでもないです。個人の感覚なので正直どうでもよいとも思いますが、短くなることによって否定の否定とかやたらテクニカルになるとそれこそ良くないので、コンテスト中はわかりやすさ重視です。
SSRS さんは間違いなく世界レベルのコーダーですが、テクニカルな書き方がほとんどなく異常に読みやすいのでよく拝見させていただいています。

結局競プロって業プロの役に立つの？

業務プログラミングといっても色んな業務があるのでまずはコンテキストをはっきりさせておくと、ハイエンドな 3DCG コンテンツを裏から支える、エフェクト・テクニカルアーティスト の視点の話です。

競プロer 向けの話

こと Houdini で使うちょっとしたプログラミングについては、基本的にほぼ AtCoder 灰色レベルです。たまに茶色くらいのが出てきます。手作業で一点ものをつくるタイプのアーティストが詰まるのは大体灰色後半から茶色前半くらいな気がします。
単純なプログラミングのスキルとは別ですが、chokudai さんのブログのスライドにもある「未経験分野の習得速度」という観点でいうとかなりアドバンテージがある気がします。3DCG の世界はとにかくすごい速さで新機能や新技術が追加されてきますが、きちんと整理して、もとになっている技術を調べて理解する力はアルゴリズムの応用力で必要以上に鍛えられるきがするからです。
AtCoder でもゲームフリークさんがスポンサーをしていたりしますが（というか色んなゲーム会社のそういう人たちと話をしていますが）かなり需要はあるはずです。

例えば以下は、とあるゲーム会社の実際の質問を競プロ風にしたものです。実際はもっと細かい例外とか面倒なことが色々あります。（色々怒られそうなので具体的なことはすべて伏せます）

$N$ 個のファイルがあり、$i$ 個目のファイルは $m_i$ 種類のファイルの参照方法を持っています。また、$i$ 個目のファイルの $j$ 個目のファイルの参照方法では、$k_{i,j}$個のファイル $a_{i,1}, a_{i,2}, \ldots,a_{i,k_{i,j}}$ を参照しています。また、単にほかのファイルへの参照情報だけを持っている場合もあれば、独自に形状データとそれに付随する情報等を集めたデータのまとまり $x_i$ を持っている場合もあります。同じ形状データに関する同じ情報が別のファイル間で二種類以上確認された場合は、ファイルごとに設定された優先度 $p_i$ をもとに最終的にシーンとして表示する情報を決定します。
すべての参照方法を試し、その結果一つ一つをを個別のファイルとして保存してください。

現状機能しているファイルの参照は DAG とみてよさそうなので、切り替えを全探索して dp 的なことをしたて情報をかき集めたらなんとかなりました。
私がもらったテスト用のデータは制約を気にするほどのサイズではありませんでしたが、実際のところは当然手作業ではどうにもならなかったり、ゲームエンジン側への様々なメタデータの生成が常日頃から行われています。
実際のところファイル形式や会社独自の内部事情や管理都合があるので、アルゴリズム部分だけ協力して、後でエンジニアから「なんとかなりました」と報告を受けた感じです。

ABC だとちょっと面倒な全探索は水色下位になるイメージなので、そこに情報のかき集めみたいな処理がプラスされるともう少し diff が上がりそうですね。

つまり私の体感では「半数以上のIT企業において、アルゴリズム能力についてはカンスト」という言葉は結構信ぴょう性がありそうです。カンストまでしなくても、そういった人材が数えるほどしかいなければどこかの部署で人が足りなくなるので、実際は 7,8 割近い会社で十分すぎる水準な可能性すらある気がします。

Houdinist 向けの話

Houdini で頻出なちょっとした Wrangle とか Python などは、ほとんど AtCoder の初心者向けコンテストの最初の二問ができれば瞬殺するレベルです。なんなら三問目までできると、Connectivity とか Graph Color とか便利ノードがたくさんありますが、そういったノードの（アルゴリズム部分だけなら）10 分 20 分で書けるレベルです。

冒頭述べた始めたきっかけにバケツ塗のアルゴリズムの話がでてきましたが、これを一般の無向グラフに拡張して少し持つべき情報を工夫すると Connectivity とまったく同じことが実現できます。よりレートが上がると、5 分もあれば正解コードが書けるレベルです。
例えばバケツ塗の類題として、以下のような問題があります。二つ目は D 問題なので四問目ですが、三問目としても十分あり得る難易度です。

アーティストであれば最初の三問ができたらかなりカンストレベルな気がします。TA でもまぁまぁ十分な案件も多いかもしれません。というのも、三問目からは問題文通りに愚直に実装すると基本的に TLE (Time Limit Exceeded, 実行時間制限超過)になるので、なんらか高速化する力が求められます。 「SOP Solverでこれを事前計算しておけば良いのでは？」とかそんなことが少しできるはずなので、かなり強いアーティストです。
AtCoder 社長の chokudai さんは「情報系の学生が茶色であれば、ちゃんと勉強してるなって印象になる」と自信のブログで述べていますが、映像系の専門学校生だとかなり優秀な人材なのではないでしょうか。
もし TLE にならないパターンの三問目でも、今度は実装がそこそこ複雑になるので、ちょっとした Wrangle で困る人はまずいないと思います。

両者向けの話

突然ですが、こんなアニメーションを作りました。ルービックキューブは適当に回したあとそれを逆再生すれば元に戻るのは当たり前ですが、それでは動きとして面白くないので、そうではなくループするようにしました。具体的には、2 回繰り返すと元に戻る 20 手の動きを求めました。実は数学的にはどんな手順も有限回繰り返すうちに元に戻るのですが、2 * 20 手が見た目にも面白く解析もしやすそうだったのでこうなりました。

解析パートは C++、CG パートは Houdini です。解析パートで競プロ的あれこれが役に立つのはもちろんとして、CG パートも結構競プロでした。具体的には

回転を表す文字列 $S$ があたえられます。それを一つずつの回転に分解して、どこをどのように回すべきか決定してください。
アーティスト的な視点では、後からアニメーションのタイミングを簡単に調整したいので、できるだけ高速で調整しやすいいい感じな方法を考えてください。
形状データは後からでも変更できるようにしたいです。
再帰的に配置したいので、座標もうまいこと計算してください。

みたいな感じです。競プロer にとっては前半と後半は比較的簡単な話で、Houdinist にとっては中盤が比較的簡単な話かもしれません。実際私も、最初に作ったリグでは回転部分の決定についてかなりハードコードしていました。それから数日して、3*3 以上に一般化したくなってきたこともありそこだけすべて書き直すことになりました。難易度的には緑中盤くらいのイメージです。どちらかというと回転記号を整合性を保ちながら拡張する方が面倒かもしれません。

ここまで競プロerにはたぶんぬるい話なので、解析パートにちょっとだけ言及すると Two-Phase-Algorithm と呼ばれるものが有名です。4*4 以上はたぶん最短に近い操作を求めるアルゴリズムはない気がするのですが、詳しい人がみていたらぜひ教えてください。

さいごに話のまとめ

よくネット上では「AtCoder の色は業務では無意味？」とか「競プロってどうなの？」みたいな小さい論争をみたりみなかったりします。人それぞれ意見はあるとして、実際私のようなろくにアルゴリズムをしらなかったヤツがある程度競プロを通して学んでから全国の CG プロダクションのエンジニアや人事と話してきた感想としては 「普通に、というか結構役に立ちます」
単純なアルゴリズムや計算量への勘もそうですが、しっかり問題を論理的に考える力とかも鍛えられた気がします。

こと Houdinist や CG 業界を目指す学生さんには、やっておいて絶対に損はないと言ってよいと思います。
逆に競プロer のみなさん、CG 業界では大いにその能力、需要があります。TA はアーティスト側をそこそこ知っておきたいですが、パイプラインエンジニアとか AtCoder のコンテストページではあまりみない職種もあります。

以上だいぶ長い記事になりましたが、最近の私の趣味競プロの話でした。じゃあの～。

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up