競プロで作問するときに考えていること

誰かの参考になるかもしれない、と思い。

自分はこれまで比較的多く作問に関わってきました。2010-2014年までの大学生/大学院生時代は topcoder (当時は世界で見て一番活気のあるコンテストでした) で50問以上 writer をやり、以降は ICPC 日本の国内予選と地区予選で、ほぼどの年も少なくとも1問は原案担当をやっていました。自分の思いついたアイデアが色んな人たちに真剣に手にとって考えてもらえる体験は、他ではできないほどの唯一無二の感慨深さがあります。

長く作問に関わっているものの何を考えながらやっているのかあまりダンプしたことがなかったので、少し言葉にしてみたい次第です。

作問は薄い狭間にある輝きを探す試行錯誤

問題づくりは盆栽のようなものだなぁと思っています。何かいいものが天から突然降ってくるというより、アイデアを育てるという感覚が近いように感じます。これについてまず書きます。

競プロの問題としてありうる存在空間のようなものを考えてみたとき、おそらくほとんどは「つまらない」問題になってしまうはずです。つまらないというのは概ね以下のような意味です。

  • 既存のよく知られたアイデア (教科書に載っている手法や典型テク) と同じか、僅かな延長である
  • 単純な方法 (指数時間の全探索など) から計算量オーダーを落とせず、工夫の余地がほとんどない

前者は問題が単純すぎたり基礎的なものを扱っている場合に起きがちで、後者は問題を個性的なものにするための条件設定が複雑すぎたり制約同士の噛み合わせが悪いときに起きがちだと見ています。

しかし面白い問題、独創的な何かのアイデアを必要とするような問題は存在します。かなり大雑把になりますが、空間の一方の側には「よく知られたアイデアの問題」の領域があり、もう一方の側に「工夫の余地がない問題」の領域があり、その間のわずかな隙間に創意工夫の余地のある問題があるようなイメージです。

作問はこの微妙で繊細な領域にある問題を探しに行く旅だと自分は捉えています。

プロセスとしては多くの場合、以下のような道をたどるのではないでしょうか。まずはモチーフを決めます。モチーフというのは、考える対象のことです。グラフや順列を考えたいのか、なにがしかの最適化をしたいのかといった大まかな枠です。モチーフに沿ってとりあえず問題を定式化します。初期の案は、出来がよくないかもしれません。まずは出来が良いのか悪いのかを判断するために問題を注意深く見ることが必要になります。もし改善が必要なら、モチーフは維持しつつも問題設定を変えて何かが変わらないかを繰り返します。これで誰かに見せてもいいと自信を持てるものができたら原案はそこで完成です。

もちろん、モチーフそのものがそれほど良くなく、納得のいくものができないこともあります。その場合は少し時間を置いて再度見直すか、あるいは諦めて他のことを考えるかという択を取ることになります。

自分が問題空間における探索としての作問について持っているイメージは、ライフゲームのようなセル・オートマトンにおけるルール設計が近いです。ライフゲームでは周囲8近傍のセルの状態に応じて次の時刻の状態が決まります。周囲の生きているセルが2とか3なら次も生存して、それ以外なら死滅する、といったものです。ライフゲームは単純なルールから非常に奥深い世界を展開してくれます。一方でこのゲームには変種もありえます。たとえば周囲の生きているセルが4とか5でも生存してもいいことにしても、ルールとしては成立します。しかし、残念ながらそのような変種のほとんどはつまらないと言われています。すぐに盤面が収束してしまったり、でたらめで構造を持たないような動きをするというのです。作問でやりたいことをライフゲームに喩えるなら以下のようになるでしょうか：

2次元のセル・オートマトンというモチーフから、「周囲の生存セル数が2,3なら次も生存」という奇跡的なバランスを持ったルールを見つけ出すこと。

長く興味を持てるモチーフを見つける

上に書いた事情から、作問というタスクは長く対象に向き合わなければ成果が出ないことがしばしばあります。目の前にあるものが実際に解ける保証はありません。解けるかわからないものに自分の時間を費やすことはいくらかのプレッシャーや葛藤もあります。このため、作問では長い間考え続けたくなるようなモチーフを探すのが大事になると思っています。

モチーフを見つける方法は色々あります。自分が取っているのは例えば以下のようなものです。

1. アルゴリズムの有名問題から何かを派生させる

入力を特殊なものに制限することで、通常よりも遥かに効率よく問題を解けるようになることがあります。

  • 部分列マッチを超長い数列に対して行う: ICPC APAC 2024 Bit Counting Sequence
  • 二部グラフ判定を膨張させたグラフで行う: ICPC 2022 国内予選 芸術家の苦悩
  • 凸包を特殊な点集合に対して取る: ICPC APAC 2026 L onion

2. 数学やアルゴリズム論にある何かの概念を中心に据える

wikipedia に載っているような枯れたもので構わないので、何かしらの概念を中心に置いてそれを発展させることで何かが生まれることがあります。自分はどうもこのパターンが一番多いようです。意外にも、真新しいことはよく知られていることの割と近くに色々転がっているような気がします。

  • 継子立ての変種: ICPC Yokohama 2023 Fortune Telling
  • 有限体上の行列ランク: ICPC Yokohama 2018 Ranks
  • ミンコフスキー和: ICPC 国内予選 2023 紋章の形の別荘
  • 風変わりな文脈自由文法: ICPC APAC 2026 Deformed Balance
  • 文法から謎のものを生成: ICPC Yokohama 2024 Tree Generators

3. オブジェクトの操作を考える

プログラミングコンテストではある定まった対象を操作して何かを最適化したり、最終形としてあり得る場合の数を考える問題が度々出ますが、これを自分の興味の出る範囲でやってみると何かが生まれることがあります。

入力は数列、グリッド、グラフ、多項式… 何か興味の持てる物が良いです。

  • 文脈自由文法で定義される式に対する操作: ICPC 国内予選 2022 じわじわ削れ
  • 数列の uniqueness, 行列, 要素の変更操作: ICPC APAC 2025 Duplicates

4. 現実のものや課題から着想を得る

有名な方法です。ただ、自分は試みてあまりうまくいかず、原案まで昇華できなかったことが多いです。

  • だんじり祭りが周囲の建物を破壊しながら進むことに着想を受けたもの: ICPC Tsukuba 2015 Routing a Marathon Race
  • JAG 合宿での宿泊: JAG 2013 Tokyo Olympics Center
  • ハードウェアの本を読んでいたときに思いついたもの: ICPC 国内予選 2018 浮動小数点数

5. インタラクティブ問題をどうにか作る

インタラクティブ問題は最初からそれを作る気持ちで挑まないとできないようです。バッチ形式をインタラクティブにするのは、普通はほとんどできないように見えます。何か秘密のオブジェクトを推測する類の問題では、必要となる情報量から質問回数の下限を見積もっておくと、それを達成するにはどうすればいいのか？という方向で進めやすい気がします。

逆に自分がほぼやったことがないのは、課題設定や概念ではなく解法からスタートするアプローチです。解法からスタートすると考えの幅が狭くなりがちで思いがけないアイデアと出会いにくい気がします。問題づくりが進んで、面白いアイデアがある程度見えてきたらそれに沿うように問題設定を微調整する、程度のことはあります。

作問する上で便利な道具

作問は解けるかわからないものと向き合うことになるので以下があると便利に進むことがあります。

  • レーティング: 単純に、分析力が高ければ問題が解けるかどうかを見分けたり、別解の可能性に思いを馳せやすくなってよいです。とはいえレーティングはそんなにすぐ伸びるものでもないのと、特定の問題を解くだけなら関連しない分野に対する知見は活きてこないので、なにか作りたいものがあったらそれに向き合い続けるのも大事だと感じます。世界にある知見は限りなくありそれを限られた時間で追いかけるのは難しいことです

  • 解けない問題たち: NP困難, #P-Hard (数え上げにおけるNP困難みたいな概念) である有名問題は一通り抑えておくと、自分が不可能なものに突っ走っていることがわかり便利です。計算理論の知識としては問題の還元くらいを抑えておけば十分に思います

出題先のコンテストについて知る

ここまでは単一の問題を作ることを念頭に置いていましたが、最終的には作った問題は誰かに手にとって向かい合ってもらうことで花開く存在となります。作問に手を付けるときに、どんなところで披露できるか考えておくことは作問の意欲を高めるものになると見ています。

小規模にやるなら例えば学内サークルなどの身内でコンテストをやるというのがあるでしょう。今の世の中で新規なものを作り出すのは容易ではありませんが、受け手側が新規性をそれほど気にしないなら心理的なハードルも低いはずです。

オンラインの不特定多数が参加するものでも国内なら yukicoder のような脈々と継がれているコミュニティがあり、そこに入るのも良いことだと見ています。自分は yukicoder で作問したことがないのであまり定かでないのですが、テスターから意見をもらえたりするのは刺激になりそうです。大学コンテストはもし学内に有志が揃っていたらチームで何かを運営する経験になるように見えます。JAG で模擬コンテストを開くのも同様です。

高みを目指すなら AtCoder や Codeforces のような数千人が参加する規模のオンラインコンテストが対象になるのでしょう。採用されれば喜びは大きいと思います。

締め

なんだか書いてみると具体的な方法論よりもメンタルモデルっぽい話が中心になりました。実際のところ「これをやればいい」というものはあまり無いように感じます。問題空間は広大で、そこをどう歩くかは作問者の感性や欲求次第であり、万人に共通するものはそう多くはないのではないでしょうか。赤ん坊が本能的な欲求で息をして身体を動かしたがるのと同じように、自分の感性を信じて問題空間をぶらぶらと歩いてみるのが良いのではないでしょうか。

ズートピア2 感想

他の考察とか全く見てないので結構めちゃくちゃなこと言っているかもしれない

世界

  • ズートピア自体は島で、いくつかのでかい壁で隔てられてできていることが判明した
    • 思っていたよりだいぶ人工の世界だった
    • これは異なる存在たちが対等となりえる世界を築くには手作りの不断の努力が欠かせないということの暗喩だろうか？
  • 成立から100年くらいしか歴史がないことも分かった
  • 降雪機や高温装置をぶん回してツンドラや熱帯を維持している
    • とんでもなくエネルギーが掛かりそうだがどこから得ているのだろう？
    • どこかで原子炉だか核融合炉だかをぶん回してるのか、あるいは再エネで頑張っているのか… いずれにしても膨大な発電施設が必須に見えるが作中では描写がなかった気がするので、妄想の余地がある
  • 島の広さ自体はよくわからないが、作中での登場人物たちの移動などを見るとそんなに広くなさそうな気がする
    • あんまり広かったら人工の自然環境とか作れない気がするし
    • 車で1日掛ければ1周できるくらいの規模感だろうか？
    • あまり広くないのだとすると人口もそこまで多くないことは察せられる

刑務所

  • ビーバーに数分で脱獄されていた
    • ズートピア住民の相互理解が欠けてそうな感じがする
    • あのビーバーが有能すぎだった可能性もある
    • 刑務所に限らず、個体が多様すぎて設備の標準化が追いついていないところが色々ありそう
  • 囚人全解放ボタンがすごい押しやすそうな場所にあった
    • どういう目的？
    • 刑務所で火事とかがあったときのための緊急脱出装置として用意されていた？のだとするとだいぶ慈悲深いが、それはいいのか…
  • 200人しか収容されていなかった
    • ズートピア全体の囚人があれだけだとすると衝撃的な平和さに思える
    • さすがに刑務所があれだけしかないというわけではないのかもしれない。げっ歯類とかどう見ても収容できないし

社会

  • 全体的に、なんで大型動物の警察官しかいないのだろう？
    • 殺傷力のある銃が普通に存在してるっぽいのを見るに、腕力よりも小回りの効くタイプがいた方が成果を上げやすいのではないだろうか。一枚岩的な集団では多様な市民に対応できない感じがする
    • 実際、警察官たちは一般人に近いニックをかなり逃しまくっていたわけで
    • 警察が大型種族にとっての利権団体となってしまっている可能性はそれなりにありそう。署長が中型種族の新人であるジュディとニック相手にムキになっていたのはそういう理由もちょっとあるのでは？
    • しかし中型動物のジュディが警察の団員として成果を上げ始めた今、この利権が揺らぐのは時間の問題である
  • 前市長(ヒツジ)が小型種は民主主義の場なら数で圧倒できると言っていたように、種族ごとに利権を独占している場がありそう
    • 例えば1でハムスターたちがオフィスビルから一斉に退社する様子が描かれていたが、彼らは特定のビジネス領域を牛耳っているのではないだろうか
    • 新しい市長として小型種ではなく大型種の馬が選ばれたのは小型動物の政治への利権が崩れたことを意味しているのだろうか？
    • 普通に馬の新市長が人気者だった可能性もあるが、暴かれたスキャンダルによって選挙での投票に重み調整などが入った可能性も捨てきれない
  • 島の外の世界との交流が存在することが明らかになった
    • 少なくとも貨物船でモノの取引はしているらしい
    • ということは島の外にも国家らしい集団がいることになる。ズートピアの規模感を踏まえると、ズートピアは小規模国家のようなもので、外にもっと大きな陸地と個体群が存在しているのではないだろうか
    • しかしズートピアの政治トップは「市長」と呼ばれており首相や大統領ではないことから、ズートピア自体は国家ではなく何かしらの国家の一つの自治体であると考えるのが自然だろうか？その割にはズートピア社会は外の存在に無関心な感じがする
    • 少なくともズートピア社会は爬虫類に対してかなり禍根があることが今作で分かったが… 外から侵攻とかされないのだろうか。国際情勢がどうなっているのかはあまりヒントがないので妄想の余地がある
    • モノの取引があるということは経済圏もありそうだが、これも今のところは妄想するしかない
    • ラストで前市長が島外逃亡(？)しようとしていたのを見るに、市民には移動の自由が与えられていることが伺える
  • 裏社会
    • 少なくとも、ハムスターと猫ファミリーの2つのグループがあることが分かった
    • 猫ファミリーは今作で壊滅したっぽいがズートピア社会にはどんなインパクトがあったのだろう？
  • 壁
    • ズートピア社会の超重要インフラの割に警備がかなり手薄そう。設備はほぼ無人で、入口には警備員すら立っていない。テロリストが乗り込んできたらズートピアは危機的な状況に陥りかねない

ジュディ

  • なんか (命懸けなくても良さそうな場面でも) かなり捨て身で行動している
    • 死にゲーの主人公なのかというくらい危険択を取っているがどういうマインドなんだろう？
    • 正義感駆動で安泰な家から飛び出して来たような子なので、そういう性格なのかもしれない
    • 一番危なかったのは味方だと思ってた猫に不意打ちされたときだけど、あれはどうしようもない気がする
  • ジュディが世界をそこまで深く捉えている感じはしない
    • 目の前に悪いやつがいたらとにかく捕まえる、というマインドが警察官なりたての頃からあまり変わってなさそうで、しかも成功体験まで得てしまっている
    • しかし人が集まれば色々後ろめたいことが付きまとうのは常で、そういう暗部を含めてうまく世の中の均衡を取ることが特に警察みたいなポジションの人物には求められそうだが、そういった感覚を得るタイミングがなさそう
    • これを極端に突き詰めるとズートピアの悪しき権力者がジュディによってすべて粛清される未来が見えるが、それは本当にやりたいことなのか？
    • ラストで鳥の羽が出てきたのは「次回作では鳥類が出る」という単純なメッセージなのかと思ったが、鳥は空から地上を見渡す存在であることを踏まえると、世の中を俯瞰することも大事というメッセージだったりするのだろうか？

裏切ってきた猫 (名前忘れた)

  • 振り返ると結構よくわからない行動をしている
  • リスクに見合わない道を取ってるように見える。途中まで特に勝算があるわけでもないのに警察に追われている者や爬虫類と一緒に行動していて普通に捕まってもおかしくない状態だった。いざとなったら二人を警察に差し出して自分は無罪だと押し通すつもりだったのだろうか？まぁでも一緒にバイクで走ってる時点でそれは無茶な気がする (実際銃で撃たれそうになっていた) し、あんまり後先考えてなさそう
  • 金属製の日誌の解読にヘビが必要なのは分かるが、ジュディは別にそうでもなかったのでは？性格としてちょっとお人好しなところがあって、たまたま遭遇しただけでも見過ごせなかったのだろうか
  • 古い屋敷に一緒にヘビと居合わせていたのはなんでだろう？ジュディと同じで、日誌解読のヒントをヘビと一緒に追っていた？

ツンドラの猫ファミリー

  • こいつらなんだったんだろう？
  • ツンドラ帯の権力者であり新市長を籠絡していたことからも実質的なズートピアの裏社会のトップの1グループであるとみなせる
  • ズートピアの壁の権利者であることを長年に渡って偽っており、それを盾に権力を手にした、ということのように見える
  • 暴力組織であるが、作中で家族以外の団員が見当たらなかったので組織の規模はそこまで大きくなかったのかもしれない
  • 新市長はなぜあのファミリーにビビっていたのだろう？壁はズートピアの根幹的なインフラなのでそれを握っている集団に対して大きく出られなかった？
  • しかし壁を猫ファミリーが運用しているという形跡は特に見られずあくまでも権利者、あるいは創設者であるというだけに留まっており、行政がこのファミリーに支配されていたのは間抜けにも見える。ズートピア自体の歴史が浅いので仕方ないのだろうか？

ジュディとニック

  • 思ったほど関係が成熟していなかった
    • ニックは長年自信を守るために身に着けていた仮面を外して自身の想いを伝えることができず、ジュディは自身がもう無敵の駒ではなく誰かにとっての失い難い存在になっていることに気づいておらず、結果として行き違いが起きてしまった
    • なんてじれったい…！
  • I love you 的な言葉がニックから出てきた
    • 良かった！
    • 思ったよりカジュアルに出てきた

ICPC 2025 国内予選 (審判長視点)

今年はICPC日本地区の審判長という役割をやっています。

自分がICPCに初めて出たのはもう17年前のことですが、いまは自分がそれを支える存在になっているのはそれなりに感慨深いような気がします。とはいえ、何かが特別変わったわけではなく今までの延長上にあることを粛々とやっていました。

審判団というのは問題セットなどのコンテストに必要なものを作っている人たちのことで、審判長というのはそこを代表して中間管理職っぽいあれこれをする人のことだと捉えています。以下はすべて個人的な振り返りです。

DOMjudge への移行

今年一番大きかった変更は国内予選システムを従来のものから地区予選で使っている DOMjudge に移行したことだと思います。例年は独自のジャッジシステムを使っていましたが難しい点があったと思っています。まず選手から見て

  • 実行時間が環境によって変わるので公平ではない
  • 提出方法が煩雑
  • 過去提出のソースコードを見れなくて不便

という不都合はあったはずだと思っています。しかしそれ以上に、運営視点から見たときにシステムの安定稼働という面で難を抱えていました。過去の例でシステムトラブルを引き起こしたことがあったように、メンテできる人があまりおらず潜在的なリスクも抱えており、いずれ限度が来るシステムだと感じていました。これは実際、去年のコンテストで自分が運用してみて感じたことです。

日本大会では DOMjudge を地区予選で10年以上使っていたのもあり、これに移行できないかと思っていました。しかしながら、オンサイトコンテストの中規模な大会では実績がありましたが国内予選のような大きな大会では未知数だったので、実際に運用できるかが焦点になりました。この点を綿密に計画し、実行まで頂いた ICPC secretaries の皆様 (特に今回リードしてくれた tossy さん) には感謝を申し上げます。

自分はこれに先立って、テストケースを少数のファイルにまとめればジャッジの負荷がほとんど問題にならないことをあらかじめ実験して確かめていました。これは貢献の一つだったと勝手に思っています。

Funini、これまで (20年くらい) ありがとう…

コンテストルール

国内予選のルールはなんか毎年変わっているような気がしていたのですが、振り返っているとやはり結構変わっています。

物事をよくするためにそうしているわけではあるのですが、以下の様な経緯になっていたようです。

  • 2019以前: 事前セットアップなどは禁止。最初の頃は結構適当だったが、年を経るごとに禁止事項が増えていっていた記憶…
  • 2020 - 2022: コロナ禍の影響でなんだかいろいろセットアップして良いということになった
  • 2023: コロナ禍が収束して2019以前の、色々セットアップできないルールに戻した
  • 2024: 紆余曲折あり、事前セットアップは認めた方がいいのではという形になり、色々できるようになった。ただし一定の禁止事項は残した
  • 2025: 去年のものを継続した。文面をクリーンアップしたり、include 文展開などの可否に対する明確化など、インクリメンタルな変更だけ行った

国内予選のルールを定めるのは難しいことだと思っています。

大きな方針として、地区予選などのオンサイトコンテストと同じ水準にするべきだというものがあります。もう一方で、そのようなものを各大学環境で揃えるのは現実的ではないから基本的にはできることはなんでも許す方針があります。いまのルールでは後者のスタンスを取っているのだと思っていますが、あまりになんでもできすぎると競技性が崩壊する面もあるので、一定の禁止事項を設けているような状況です。

プログラム自動生成の禁止は今年いくらか注目を浴びたような気がします。このルールは競技成立のためにある程度は必要なはずですが、一方でこのルールを広く解釈すると自分が一字一句タイピングしたものでないと駄目ということになり、あまりに窮屈というか、他のルールと整合性が取れていないように感じます。まだ何かしら手を加えることにはなると思うのですが、

  • 選手の人達が安心して競技に取り組める
  • 競技性を破ることは依然として禁止されていて、運営側も自信をもって運用できる
  • あまりルールをころころ変えない

ようなものにできるといいのだろうと思います。

問題セット

自分が思っていた以上にいっぱい解かれました。問題が難しすぎて順位表が凍りついているよりは良かったはずですが、上位チームのためにもう少し挑戦する要素は作りたかった気がします。ちなみに今回は B 問題と G 問題の原案者でした。

現場での進行

コンテスト前後で審判長として難しい判断を要求されるシーンがなく、スムーズに進行していました。過去の例を見ると、台風で交通機関が乱れて大学に集結できない状況に対応しなければならないこともあったようです。いい天気だったのは幸運でした。

DOMjudge の運用で不安になることがなかったのも良かったはずです。

競技シーンの未来…?

ところでICPCの外に目を向けると、生成AIは競プロの問題をだいぶ解けるようになってきています。これによってこの競技シーンが成り立たなくなるか、そこまでいかなくとも今ほどは注目されなくなるのではないかという声とか雰囲気がなんとなくあるような気もします。正直なところわかりません。IT技術者という職は、つい最近までそんなに大したものだと認知されていなかったような気がしますが、気がつくと世間から注目を浴びるようになっていました。AI が便利になってもシステムの面倒は誰かが見ないといけないので職は残り続けるだろうとは思いますが、いまほど人手が必要ではなくなったり、高級取りではなくなるのでしょうか。どうなのでしょう。

何にせよ、次の17年も、アルゴリズムを考えたり、コードを提出して解けたり解けなかったりする興奮が世界に残っていると嬉しいのですが。

ICPC Asia Pacific Championship 2025 準備記

熱のあるうちに。去年に引き継いで今年もジャッジメンバーとして問題準備や会場準備などをやっていました。問題セットの振り返りでもしようかなぁと思います

B: Three-Dimensional Embedding

もともとは去年の Championship に向けて提案していました。結局その時は他の構築問が採用されたので使われなかったのですが、今回は使われることになりました。 個人的に色々なことが思い出される問題です。初の Championship でコンテストがどんな感じになるか全然わからない中で模索していた日々とか、原案を少しでも増やしたくて暇な時間に解法を模索していた日々とか、転職を考えていた日々とか、外の公園を歩きながら解法をぼんやり考えていた風景とか… しかし問題自体はそういうことは関係なく、狭い空間に折れ線をとにかく詰めるという話です。 色々な解法がありえる問題であるようです。基本的には xy 平面と平行な面になるべく多くの折れ線を詰め込むという手段でいいですがナイーブにやるとぶつかって詰め込みきれないのでいくらかブレイクスルー的な発想が必要になります。

E: Minus Operator

原案を作った時期は2019年でしたが行き場がなくて困っていました。もともとは n2/2 くらいのクエリ上限を考えていましたが情報量を考えると 2n でできないのはおかしいだろうと思ってそれなりに頑張った結果 2.5n にすることに成功しました。証明できてませんが 2n は多分不可能だと予想しています。 コンテスト中に解けた方はおめでとうございます。

全体

二回目の開催ということでどんな問題を出したらどれくらい解かれるのかの感覚をだいぶ掴めていたのもあり準備はかなり取り組みやすかったです。 問題セットも Task Author のご協力により色々なジャンルのものが集まって個人的には満足しました。 60チームが4問以上解けたのもまぁ多分よかったのではないでしょうか。 トップ6チームの5完が全部ばらばらだったときが今回のハイライトです。チーム差がここまで出たセットは今回が初めてな気がします

ICPC Asia Pacific Championship 2025 準備記

熱のあるうちに。去年に引き継いで今年もジャッジメンバーとして問題準備や会場準備などをやっていました。問題セットの振り返りでもしようかなぁと思います

B: Three-Dimensional Embedding

もともとは去年の Championship に向けて提案していました。結局その時は他の構築問が採用されたので使われなかったのですが、今回は使われることになりました。 個人的に色々なことが思い出される問題です。初の Championship でコンテストがどんな感じになるか全然わからない中で模索していた日々とか、原案を少しでも増やしたくて暇な時間に解法を模索していた日々とか、転職を考えていた日々とか、外の公園を歩きながら解法をぼんやり考えていた風景とか… しかし問題自体はそういうことは関係なく、狭い空間に折れ線をとにかく詰めるという話です。 色々な解法がありえる問題であるようです。基本的には xy 平面と平行な面になるべく多くの折れ線を詰め込むという手段でいいですがナイーブにやるとぶつかって詰め込みきれないのでいくらかブレイクスルー的な発想が必要になります。

E: Minus Operator

原案を作った時期は2019年でしたが行き場がなくて困っていました。もともとは n2/2 くらいのクエリ上限を考えていましたが情報量を考えると 2n でできないのはおかしいだろうと思ってそれなりに頑張った結果 2.5n にすることに成功しました。証明できてませんが 2n は多分不可能だと予想しています。 コンテスト中に解けた方はおめでとうございます。

全体

二回目の開催ということでどんな問題を出したらどれくらい解かれるのかの感覚をだいぶ掴めていたのもあり準備はかなり取り組みやすかったです。 問題セットも Task Author のご協力により色々なジャンルのものが集まって個人的には満足しました。 トップ6チームの5完が全部ばらばらだったときが今回のハイライトです。人の得意差って面白い。

ICPC2024横浜地区予選 準備記

今年もジャッジメンバーとして問題準備をやっていっていました。

コンテスト全体を通して、ほとんどの問題は自分が予想を超える正解数で、個人的にはめでたいなぁと思いました。

  • 全チームが3完した: E 問題なんかまぁまぁ実装が面倒な気がするんですがちゃんと対応できていて素晴らしいなぁと
  • I 問題: それなりに難しいデータ構造問題だと思ったのですがなんだかサクッと通されていて驚きました
  • G 問題: 実装がかなり面倒でコンテスト中に手を出せる人はいるのか…？とやや懸念だったのですがそれを吹き飛ばすような提出と正解が来て良かったです。testing tool が活躍していたなら僕は喜びます

D 問題の思い出

E := 1 | ( E E ) というシンタックスがあって木の生成過程を表している。 2つの式に対してどちらからも生成可能な木はいくつあるか。

この問題に限らないのですが問題を作ったときの記憶というのがいまいち残っていません。最初は割とごちゃごちゃしたことを考えていて、整理し終えれば綺麗になるのですがその過程はいろんなものを選んだり捨てたりしていて言語化するのが難しいというのがあるのかもしれません。なので以下は半分くらい作り話ではあるのですが、書いてみます。

まず現代だと寂れた主題を扱いつつ中身が COOL な問題作ってみたい気持ち*1がありました。構文解析は定義通りに再帰関数を実装するだけの味気ないテーマですが、これを考えることにしました。 あとは変なものを構成して遊んでみたい気持ちもありました。これらが混ざりあった結果、無向木を作る構文を考えてみることにしました。 この時点だと何が生まれるのかよくわからんのですが、とりあえず終端記号はなんか必要で、二項演算子みたいなのも欲しい気持ちになります。 二項演算子というのは木と木から新しい木を作るわけですが、1本枝を足すのが自然そうに見えます。自然なのですが任意性が色々あってどれか一つに決めるのは難しいのでとりあえずはランダムに選ぶものだとしてみます。 そうすると式は木を生成するランダムな過程だということになります。ランダムならやはり確率とか考えた方が面白いんじゃないか… という気持ちが芽生えます。 芽生えたところでなんの確率を主題にするのかとまた悩むのですが、手で少し試行錯誤していると違う式から同じ木が生成できることがあるのに気づきます。そこでいまの原案に近いものができました。2つの式から木を生成して偶然同じになる確率はいくら？と。 このように最初は確率の問題として考えていたのですが、確率の分母のところは面白くないから要らないと思って削り、分子のところだけを問う数え上げの問題として仕上げました。 想定解も最初はよくわかってなくて2乗くらいのものを想定していたのですが少し冷静になって線形時間になることに気づいたり。

コンテスト後に面白かったと言ってくれた方がいてとても嬉しかったです。

その他

表彰式のホールが例年使っている場所と変わり、豪華で良かったです。yes/no セッションはだいぶ見入っていました (ジャッジはあらかじめ結果を知っているはずなのですがこのセッションのときは記憶が揮発しています。不思議)

選手だった人がスタッフになってコンテストを回してるのを見ると嬉しい。

*1:似た意識で出題したものとしてサイコロ職人があります

ソフトウェアの設計

ソフトウェアの設計方法について自分なりに述べてみたいと思う。

ソフトウェアは何であるか

ハードウェアとしての計算機が担うことは 1.入力を受け取り、2. 何かしらの計算処理をして、3. 結果を出力する、という3つに尽きる。これはソフトウェアでも変わらない。プログラミング上でこれを行う最小単位は関数であろう。関数は入力として引数を取る。関数内部では何かしら処理をする。最後には返り値を返す、もしくは結果をどこかに格納するといった形で出力を行う。これがもう少し大きな粒度になるとクラスやパッケージといったものになる。クラスでは意味をもつまとまったデータ群を一つに束ね、それに関連する関数を紐づける。パッケージとかライブラリはそれをさらに高階層でまとめたものになる。サービスとかアプリケーションと呼ばれるものは、これらの一連の処理をまとめてエンドユーザーにとって意味のある形で実行可能にしたものである。

ソフトウェア開発に伴う困難は何か

ソフトウェアにはアーキテクチャというもの(考え方)がある。これを理解するには、ソフトウェア開発に必然といえるほど伴う困難について理解しなければ、その存在意義は見えてこない。

必要とされる要件を満たすソフトウェアの実装方法は無数にある。作るべきソフトウェアがたった一度だけそれっぽく動けばいいのであれば実装方法はなんでもいいのかもしれない。しかし実際にはソフトウェアは長期的に動き続けるものでなければならない。それは建築物と類似しているかもしれない。建築物はそれができた後でも、災害や老朽化に耐えられるような作りにしておかなければそれに住む人は安心して暮らせない。

ソフトウェアでも似たようなことが言える。まずソフトウェアは完成当初から完璧であるということはあまりない。内部に何かしらの不具合を含んでいる。不具合が見つかり次第いつでも修正できる状況を保てなければ、やがてそのソフトウェアは信頼できないものとみなされるだろう。それとは別に、後から追加で要件がやってくることは普通である。無尽蔵に湧き出る欲求に対応できないソフトウェアもまた、信頼できないものだろう。逆に追加ではなく、あるものを撤収しなければならないケースもある。これについても同じことがいえる。

ソフトウェアが自分の書いたものだけで完結することは少ない。外にあるライブラリやエコシステム、外のクラウドサービス、土台となる OS など、様々なものに依存している。それらも同じように流動的であり、必須の更新パッチが当たったり、これまで使えていた機能が廃止されたり、メンテナンスが終了したりする。その際には自分のソフトウェアも追随して更新したり、場合によっては外部依存選定そのものを見直したりしなければならない。

また、仮にソフトウェアが一度しか動かないことが確定している場合でも、重要な用途を想定するソフトウェアなら開発にはそれなりに長い時間が掛かることも考慮が必要である。これは、ソフトウェアの内情が誰の目で見ても明瞭な形を保持し続けていなければ、やがて誰も手を付けられなくなり開発は停滞しうることを意味する。

つまるところ開発したソフトウェアは長きに渡って面倒を見続ける必要がある、ということを想定して作らなければならないのである。変更に耐えられるソフトウェアを作るのは容易ではないが、うまくやるためのパターンやノウハウがある。

ソフトウェア開発に伴う困難を克服する方法は何か

MVC というよく知られたパターンが有る。冒頭で計算機の行うことは入力、処理、出力の3つだと書いたが、MVC の3つの要素はだいたいこの計算機の基本の流れに沿っていると思っている。Controller はユーザからの入力に責務を持つ。Model は処理とデータ管理に責務を持つ。View はユーザへの出力に責務を持つ。ソフトウェアの構成要素が責務を持つ領域を明確に区切ることは単一責任の原則と呼ばれるが、これはコードの維持のしやすさに大いに貢献する。というより、実行したら入力に対して何が返ってきてどんな副作用を起こすかはっきりしないコードは危うい存在だといったほうが正しいのかもしれない。

MVC やそれに近しい存在である三層アーキテクチャはシンプルで良いが、不十分な点がある。クリーンアーキテクチャはこのような多層アーキテクチャをベースにして依存性や責務の明確化を推し進めたものだとみなせる。

大事なのは長きに渡って誰でも面倒を見れるものを作ることである。儀礼的にデータのバケツリレーをすれば必ずしも高い生産性を発揮できるわけではない。書いたコードが単純になにかのパターンに沿っていなければいけないというものでもないはずである。