【一気読み】【参加記】頭脳のオリンピックに挑戦！ICFPC2024に挑んだ物語

2024年8月2日 13:00

*3部作でお送りしたものの一気読み専用記事です。

ALGO ARTISでは多くのエンジニアがプログラミングコンテストに参加しています。2024/6/28~7/1に開催されたICFP Contest 2024(ICFPC)というチーム戦のプログラミングコンテストに、社内有志でチーム"Heuristic Artis（ヒューリスティックアーティス）"として参加しました。
コンテストの面白さ、社内のメンバーの工夫、何よりもメンバーがコンテストを楽しんでいるさまを伝えたく参加記を書きました。
プログラミングコンテストの経験が豊富な方も、プログラミングコンテストって何？という方も楽しめる記事に仕上げましたので、ご一読いただければ幸いです。

ICFPCとは?

ICFPという国際会議が主催するプログラミングコンテストで、毎年7月頃に開催されます。今年は27回目の開催で、前世紀から続くとても歴史のあるプログラミングコンテストです。
特徴としては、

人数制限なしのチーム戦
コンテスト時間が72時間とマラソン系のコンテストとしては中間的な長さ
問題の形式やジャンルは毎年様々に変わり、AHCのようなヒューリスティックコンテストのような問題、手で解くパズルのような問題、果ては折紙を折るソルバーを作るなどの超難問が出されたことある

というもので、普段のマラソンコンテストとは一風変わったコンテストになっています。
今年はALGO ARTISとして初めてチームを組み、チーム”Heuristic Artis”で参加しました。

チーム紹介

総勢11名の競技プログラマーが参加しました(敬称略):
threecourse, terry_u16, G4NP0N, tempura0224, Jirotech, plcherrim, KawattaTaido, nrvft, yunix, yochan, takumi152
AHCレーティング合計28,484、平均約2590のなかなか強そうなチームになりました。
メンバーの得意分野もヒューリスティック・アルゴリズム・ゲームAI・パズル・フロントエンドと、多方面に隙のないチームを作ることができ、どのような問題が来ても良い成績を残してやるぜ!という気持ちで参加しました。
今年はメンバー間のコミュニケーションを円滑にして問題に集中して取り組むために、箱根にホテルの部屋を借りて4泊5日の合宿をしました。

余談ですが、AtCoderの社長のchokudaiさんも参加しているレジェンドチーム、Unagiと宿がかち合ってしまうハプニングがありました(しかも部屋が隣でした…)。
大浴場で考察を聞いてしまわないように、Unagiとの間にお風呂を使う時間の協定が結ばれました。
コンテスト中は、世界で一番ICFPCが強い宿じゃん、みたいな冗談をチーム内で言っていました。

隣の部屋でしたｗｗｗｗｗｗ
コンテスト中の温泉を利用する時間は、偶数時がUnagi、奇数時がALGO ARTISにしよう、って話になりました。そんなことあるんだねえ……ｗhttps://t.co/bhfEm25htS
— chokudai(高橋直大)@AtCoder社長 (@chokudai) June 28, 2024

今年の問題概要

問題の設定は以下のようなものでした:

“Cult of the Bound Variable”という宇宙文明が見つかった(2006年度のICFPCの問題設定に登場したものと同じらしい)
宇宙文明は関数型の言語(以下宇宙言語)を使ってコミュニケーションをしており、ICFPコミュニティは言語の仕様を概ね解読することに成功した
- 宇宙言語は関数型の言語で、string, integer, boolean, 単項演算子, 二項演算子, ラムダ式などが定義されている
宇宙文明は宇宙で生きていくために必須なスキルについて、オンラインコースで訓練を提供している
コンテスタントは各コースのテストにおいて良い点数を取ることが求められる

このような設定で、

hello
efficiency
lambdaman
spaceship
3d

という5つのコースで出題される問題に取り組んで回答をすることが求められました(各々のコースは10~20程度の小問題から構成されます)。
順位は以下のようにつきます:

全体の順位は、各コースの順位の合計値が小さい方から上位
各コースの順位は、コースの中の小問題ごとの全体順位の合計値が小さい順
小問題は答えが1つに定まっているもの(hello, Efficiency), 条件を満たす答えの中から良いスコアを求めるもの(Lambdaman, Spaceship, 3d)がある

このコンテストのユニークなところは、宇宙人のオンラインコースなので、宇宙言語のstring型の値で問題が出題され、宇宙言語のstring型の値で問題を回答しなければいけない点です。

[宇宙言語の問題文] SB%,,/}!.$}7%,#/-%}4/}4(%}M#(//,}/&}4(%}</5.$}P!2)!",%_~~<%&/2%}4!+).'}!}...

[英語に翻訳された問題文] 
Hello and welcome to the School of the Bound Variable! ...

copy

宇宙言語のstringと英語の間の変換は規則が与えられており、翻訳の規則自体は単純です(変換規則が既知の単一換字暗号)。
spaceshipと3dは英語にすると普通のヒューリスティックな問題とパズルになり、宇宙言語についてあまり気にしなくて済みました。一方で、efficnecyとlambdamanについては宇宙文明が使用している関数型言語に真面目に取り組む必要がありました。
以下ではhello以外の各コースの問題の概要、解法のアプローチや面白かったところについて、各コースを担当していたメンバーが解説をします。

efficiency

問題概要

efficiencyは宇宙言語で書かれたプログラムが与えられ、その実行結果を解答として提出することが求められる問題でした。
例えば、以下のような文字列が問題として与えられます:

B$ B$ L# L$ v# B. SB%,,/ S}Q/2,$_ IK

上記のプログラムを宇宙言語の仕様に則ってHaskell風に変換すると、以下のようになります:

((\v2 -> \v3 -> v2) ("Hello" . " World!")) 42

copy

この場合には実行結果が”Hello World!”になります。

問題へのアプローチ

宇宙言語をそのまま理解するのはかなり辛そうだったので、まずは見覚えのある形式のプログラムに変換することを目指しました。yunixが徹夜で字句解析器、パーサー、プリンタを書いて、宇宙言語からJavaScriptの無名関数を使った記述に変換するツールを作りました。

[宇宙言語]
B$ B$ L# L$ v# B. SB%,,/ S}Q/2,$_ IK

[変換した式]
((v2)=>((v3)=>(v2)))("Hello"+" World!")(42)

copy

変換した式はJavaScriptの記法になっていて、実際にJavaScriptの式として実行することもできます。
トランスパイラができたのであとは楽勝だぜ、などと思っていたのも束の間、実際に出題される問題を変換してみると見通しが甘かったことがわかりました。
efficiencyの3問目の内容を見てみましょう:

[宇宙言語]
B+ I7c B* B$ B$ L" B$ L# B$ v" B$ v# v# L# B$ v" B$ v# v# L$ L% ? B= v% I! I" B+ I" B$ v$ B- v% I" I":c1+0 I"

[変換した式]
2134 + ((v1) =>(((v2) =>(v1(v2(v2))))(((v2) =>(v1(v2(v2)))))))
(((v3) =>(((v4) =>(v4 == 0 ? 1 : 1 + v3(v4 - 1))))))(9345873499) * 1

copy

変換した式を見ても何が何だかさっぱりわかりません。この式はJavaScriptの文法としては有効ですが、実際に実行しようとするとスタックオーバーフローが起きてしまいます(この事情はlambdamanでのtempura0224の解説にも書いてあります)。再帰と無名関数が多すぎて意味が不明です。

頭を抱えていたら、関数型言語の処理を調べていたterry_u16が颯爽と現れ、このプログラムの読み方を教えてくれました。

"((v1) =>(((v2) =>(v1(v2(v2))))(((v2) =>(v1(v2(v2))))))) "の部分はYコンビネータというもので、後続の無名関数を再帰的に処理できるようにするもの
- https://en.wikipedia.org/wiki/Fixed-point_combinator
"(((v3) =>(((v4) =>(v4 == 0 ? 1 : 1 + v3(v4 - 1)))))) "の部分をYコンビネータと組み合わせると

const g = (v) => {
  if (v==0) return 1;
  return g(v-1)+1;
}

copy

というような再帰的な処理をする関数になる。(細かいことは今でもよくわかっていませんが、Yコンビネータ部分をうまく読み飛ばして後続の関数を再帰的に処理するものとして理解すれば良い)

terry_u16の教えてくれた通りに問題を解いて(というか全部解いてくれたのですが)、9345873499 + 1 + 2134 = 9345875634が答えになりました。

他の問題でも同様のアプローチでterry_u16が解きました(以下は5問目をJavaScriptに変換したもの):

((v6) =>
  ((v7) =>
	  // Yコンビネータ部分
    ((v1) => ((v2) => v1(v2(v2)))((v2) => v1(v2(v2))))(
	    // 以下の箇所を再帰的に実行する
	    // 初期値2を1つずつincrementして、v4>1000000 && v6(v4) && v7(v4+1)を満たす最初の数を返す
      (v3) => (v4) => v4 > 1000000 && v6(v4) && v7(v4 + 1) ? v4 : v3(v4 + 1)
    )(2))(
	   // v7部分
    ((v1) => ((v2) => v1(v2(v2)))((v2) => v1(v2(v2))))( //v7のYコンビネータ
      (v3) => (v4) =>
        // v4が1だったらtrue, 奇数だったらfalse, 偶数だったら2で割って再帰的に実行
        v4 == 1 ? true : v4 % 2 == 1 ? false : v3(parseInt(v4 / 2))
    )
  ))((v5) => // v6部分、素数の判定をしている
  ((v1) => ((v2) => v1(v2(v2)))((v2) => v1(v2(v2))))(
    (v3) => (v4) => v4 == v5 ? true : v5 % v4 == 0 ? false : v3(v4 + 1)
  )(2)
);

copy

terry_u16の教えに従って読むと、

1000000より大きい
1をプラスしたものが2の累乗
素数

つまり、100万より大きい最初のメルセンヌ素数を返せば良いことになります。

順調に問題を解いていたのですが、terry_u16でもアプローチの仕方がわからない問題がありました。それは次のような問題でした(長いので一部省略):

((v1) =>(((v2) =>(v1(v2(v2))))(((v2) =>(v1(v2(v2)))))))
(((v2) =>(((v1) =>(((v11) =>(((v12) =>(((v13) =>(((v14) =>
(((v15)=>(((v16) =>(((v17) =>(((v18) =>(((v19) =>(((v21) =>
(((v22) =>(((v23) =>(((v24) =>(((v25) =>(((v26) =>(((v27) =>
(((v28) =>(((v29) =>(((v31) =>(((v32) =>(((v33) =>(((v34) =>
(((v35) =>(((v36) =>(((v37) =>(((v38) =>(((v39) =>(((v41) =>
(((v42) =>(((v43) =>(((v44) =>(((v45) =>(((v46) =>(((v47) =>
(((v48) =>(((v49) =>(((v51) =>(((v52) =>(((v53) =>(((v54) =>
(((v55) =>(((v56) =>(((v57) =>(((v58) =>(((v59) =>(((v61) =>
(((v62) =>(((v63) =>(((v64) =>(((v65) =>(((v66) =>(((v67) =>
(((v68) =>(((v69) =>(((v71) =>(((v72) =>(((v73) =>(((v74) =>
(((v75) =>(((v76) =>(((v77) =>(((v78) =>(((v79) =>(((v81) =>
(((v82) =>(((v83) =>(((v84) =>(((v85) =>(((v86) =>(((v87) =>
(((v88) =>(((v89) =>(((v91) =>(((v92) =>(((v93) =>(((v94) =>
(((v95) =>(((v96) =>(((v97) =>(((v98) =>(((v99) =>
(!v11 == v12 && !v11 == v13 && !v11 == v14 && !v11 == v15 && 
!v11 == v16 && !v11 == v17 && !v11 == v18 && !v11 == v19 && 
!v11 == v21 && !v11 == v22 && !v11 == v23 && !v11 == v31 && 
!v11 == v32 && !v11 == v33 && !v11 == v41 && 
...(省略)... 
&& !v95 == v98 && !v95 == v99 && !v96 == v97 && !v96 == v98 && 
!v96 == v99 && !v97 == v98 && !v97 == v99 && !v98 == v99 
? v1 : v2(v1 + 1)))
(1 + parseInt(v1 / 1) % 9)))(1 + parseInt(v1 / 9) % 9)))
(1 + parseInt(v1 / 81) % 9)))(1 + parseInt(v1 / 729) % 9)))
(1 + parseInt(v1 / 6561) % 9)))(1 + parseInt(v1 / 59049) % 9)))
...(省略)...
(1 + parseInt(v1 / 21847450052839212624230656502990235142567050104912751880812823948662932355201) % 9))))))(1)

copy

変数が多すぎる & 条件式が多すぎる & 謎の大きな数値で割り算をしていて意味が不明な問題で、これが一体何の問題なのか困っていました。
そこに通りかかったtempura0224がこの問題は数独じゃないかと言い出しました。初めに聞いた時には何を言っているかわからなかったのですが、

変数がv11からv99までの81個ある
- v11は(1, 1)マスに対応する変数
v11 ≠ v12 && v11 ≠ v13… のように数独特有の9マス内で同じ数値が重複しないような条件式が書かれている
変数として1が与えられて、条件に合わなかったらインクリメントされている
最後の(1 + parseInt(v1 / 81) % 9))) のような箇所は数独の各マスの数値を9進数で表している

ということらしく、言われてみれば確かに…となりました(なぜ気付けるのかわからないですが、efficiencyを全部正解していたチームはたくさんいたので、わかる人にはわかるものだったのでしょう…)
従って、辞書順で最小の数独の答えを返せばよく、「そんなものOEISにないわけがない」というtempura0224の言葉通りhttps://oeis.org/A114288 が答えでした。

最後に

上記以外の工夫としては、

処理内容をLLMに問い合わせて、処理内容をエスパーする
小さな数値を関数の入力にあたえて実行結果を見て、処理内容をエスパーする

なども行いました。
各メンバーの協力もあって、コンテスト開始から24時間くらい経つ頃にはefficiencyの問題は全て討伐できました。

efficiencyはコンテスト序盤に取り組んでいた問題だったので、関数型言語のプログラムを読むことに慣れておらず手間取ったところもあります。このあとterry_u16とtempura0224はlambdamanでさらに宇宙言語に手を焼くことになります。
最終的にterry_u16は宇宙言語をそのまま読み書きできるようになりました。terry_u16を見かけたらSB%,,/と挨拶してみましょう。

lambdaman

問題概要

lambdaman では迷路とスタートマスが与えられ、上下左右への移動を繰り返して全ての . マスを1度以上通るような操作を求める課題でした。# のマスや盤面の外側に出ることはできません。そのような操作をしようとした場合その場に留まります。
例えば、以下のような迷路に対しては、LLLDURRRUDRRURR(左左左下上右右右上下右右上右右)と回答することで正解となります(Lがスタート位置を表すマスです)。

###.#...
...L..##
.#######

copy
lambdaman は全部で21問出題されました。問題ごとに様々な特徴があります。

lambdaman は efficiency とは異なり、ただ正解すればよいというわけではなく以下のような特殊なルールが設定されていました。

提出は、文字列をそのまま送ってもよいし、迷路を解く文字列を生成する宇宙言語のコードを提出してもよい
正解の中でも、より短いコード量で正解できたほうが高順位になる
出力される文字列の長さは100万文字以下に収めること

具体的な問題で説明しましょう。
問題6 は以下のような迷路でした。

L...........(略)...

copy
. の数は省略した部分も含めると199個でした。これを迷路と呼んでいいのかは謎ですが、何はともあれ右に199回(以上)移動すれば正解できます。
したがって、最も簡単な正解方法は R を 199 個繰り返した文字列をそのまま出力することですが、これだと 199 文字かかってしまいます。
しかし宇宙言語を使って例えば以下のようなコードを書くと 74 字で R を 200 個繰り返した文字列を生成することができます。

B$ L' B. v' B. v' B. v' B. v' v' SLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL

宇宙言語に精通されていない読者のために JavaScript に変換したコードを添えると以下のようになります。
「同じ文字列を5回繰り返す関数」を作ってそこに「Rを40回繰り返した文字列」を代入する、ということですね。

((v1) => v1 + v1 + v1 + v1 + v1)("RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR")

copy
ちなみに、実際のこの問題を解く最も短いコードはこのようになります。

B$ L" B$ v" B$ v" B$ v" SLLLLLLLL L! B. v! B. v! v!

JavaScript で書くと以下のようになります。もはや JavaScript にしても難読ですね。
ざっくり説明すると、「Rを8回繰り返した文字列に”ある操作”を3回繰り返す」という関数に「文字列を3回繰り返す」という操作を代入することで R を 216 回繰り返した文字列を生成しています。

((v1) => v1(v1(v1("RRRRRRRR"))))((v2) => v2 + v2 + v2)

copy

問題へのアプローチ

efficiency で「宇宙言語を読む」ことはある程度できるようになっていた我々ですが、ここで2つの大きな問題に直面しました。

宇宙言語を自分たちで書かないといけない
自分で書いた宇宙言語が正当であるかを確かめるために、実行できる環境が欲しい

yunix の貢献により宇宙言語をJavaScriptに変換することはできていましたが、前述の通り再帰関数を実行しようとすると落ちてしまうなどの問題があり、機能としては不十分でした。
そこで、tempura0224 がJavaScriptで遅延評価を実装することで再帰関数の実行を可能にし、さらに JavaScript のコードを宇宙言語に変換する逆トランスパイラを追加で開発しました。これにより、「JavaScript で迷路を解くコードを作成し、手元で実行結果を確認しつつ、宇宙言語で提出する」ということが簡単に行えるようになりました。
(tempura0224 がこれの実装に手こずっている間に terry_u16 が「94進数整数を4進数に変換する関数を作成することで回答文字列を圧縮する」という方針のコードを宇宙言語を直接書くことで完成させていて目と耳を疑ったのですがそれはまた別のお話です。)

最初、私たちのチームでは、「ランレングス圧縮した文字列を埋め込んで復元するコードを作成すると短くなるのではないか」「ランレングス圧縮を前提としたときに、短くなるような経路を見つける必要がある？」といったことを考えていましたが、ここで terry_u16 が閃きました。
「100万回も移動して良いならランダムな移動を繰り返すとわりとうまくいくのでは？」
通らないといけないマスの数は最も大きい問題21(約4万マス)を除けば数千マス程度、小さい問題だと数百マスしかないので、確かに100万回も移動すればいけそうな気もします。
早速線形合同法を用いてランダムな文字列を生成するプログラムを書くことにしました。宇宙言語でのコードは割愛しますが、以下のような再帰関数を実装しました。


const solve = () => {
   const start = 23;
   const end = 1;
   const a = 23;
   const m = 799999;

   const rec = (x) => {
      if(x === end) {
         return "";
      }
      const next = a * x % m;
      return "LURD"[x % 4] + rec(next);
   }

   return func(start);
}

copy
一般的な線形合同法は ax + b の形を用いますが、+ b に使う文字数も惜しいので a 倍するだけの簡易実装です。
このコードを宇宙言語に書き直して提出すると数百マス程度の迷路は全て解くことができました。
数千マス以上の問題はこのままでは厳しかったのですが、以下のような努力をすることで結果的にはほぼ全ての問題を線形合同法によって解くことができました。

単にLURDをランダムに繋げるのでなく、問題に応じて、同じ文字が連続しやすくなったり、左折/右折が連続しやすくなったりするような工夫を加えました。
マシンパワー(180コア360スレッドのGCEインスタンスを借りました)を信じて、迷路を解くことのできるパラメータ(start、end、a、m)の組み合わせを探索しました。コード長が短いほうがよいというルール上、ただ迷路が解けるだけでなく各種パラメータの桁数が短いほうが良いので、必死に探索しました。

最終的に、僕たちのチームの解法の内訳は全21問中

迷路が小さく文字列をそのまま出力するのが最短だったもの: 3問
線形合同法などランダムな文字列を出力することで解いたもの: 13問
それ以外の方法(問題6のようなルールベースなど)で解いたもの: 5問

となりました。多種多様な迷路があるにも関わらず半分以上の問題が線形合同法で解けてしまうというのは少し切ない気持ちにもなりつつ衝撃的で面白かったです。
余談ですが、コンテスト終了後に各問題の最短解法が公開されており、そこでは僕たちがランダム解法を採用しなかった3問を含めた実に16問がランダム解法で更なる衝撃を受けました。
僕たちのチームは、lambdaman 単独では、順位表凍結時点では5位とまずまずの結果となりました。上位に食い込めた理由は線形合同法でうまく解けるパラメータを見つけることに成功していたからですが、逆に最上位に入れなかったのは、線形合同法のそもそもの実装が良くなかったからでした。再帰関数を実装するのにYコンビネータをそのまま使用していたのですが、実は一工夫加えることでより短いコード長で再帰関数を実現できたようです。
「実は再帰関数をもっと短く書ける」以外のほぼ全ての要素をクリアしていただけに悔しさの残る結果とはなってしまいましたが、最後まで楽しく向き合うことができました。
最後に、線形合同法以外の方法で面白く解けた問題を2問紹介してこの章を締めくくりたいと思います。

問題5

中央から渦巻きのような形で外側に出ていく問題です。
「LLRDDDLLUUULLULLRUURUDRDRRRURDLD という文字列を27回繰り返す」という解法で上位に入ることができました。LLRDDDLLUUULLULLRUURUDRDRRRURDLD という文字列は山登り法によって見つけられました。こういった設定でも山登り法で解けるのは面白かったです。

問題19

フラクタルのような形状になっています。マス目の数や行き止まりが多く線形合同法などの解法では解くことが難しい問題でしたが、Jirotech がこのフラクタルの構造を解析し、以下のような再帰関数を実装しました。
この問題では全体で単独1位(順位表凍結前時点)のコード長を達成することができました。

const solve = () => {
  const func = (n, idx) => {
    if (idx === 0 || n === 0) {
      return "";
    }
    return (
      "UDDULRRL"[idx / n] +
      (idx % (2 * n) === n ? func(n / 2, 4 * n - 1) : "") +
      func(n, idx - 1)
    );
  };
  return func(64, 511);
};

copy

spaceship

問題概要

SpaceShipは宇宙言語を読み解く他の問題とは異なり、ヒューリスティックコンテストに出てくるような形式の問題でした。※ただし、入出力は宇宙言語を変換する必要があります。

ルールは以下のようなものです:

ゲームは2次元座標上で行われ、次のように進行します。
宇宙船は最初、原点 (0, 0)に位置し、速度は (0, 0) からスタートします。各ターンで宇宙船は以下のように行動します。
1. 速度のx座標、y座標をそれぞれ±1だけ変化させるか、そのままにする（3×3=9通りの操作）。
2. 宇宙船の位置を現在の速度分だけ移動させる。
訪問する必要のある地点のリストが与えられるので、なるべく少ないターン数でそれら全ての地点を訪問する手筋を見つけてください。

速度と加速度を使って目的地に移動していく問題なので、第一回マスターズ決勝にどこか似ていますね。

速度は毎ターン高々1のみ変化する
速度にノイズが加わることはない

という点がマスターズ決勝と異なっています。決定的に位置・速度が決まるので、工夫すればターン数の理論値が出せそうな雰囲気が感じ取れます。

例

訪問する地点として、(1,-1), (1,-3), (2,-5), (2,-8), (3,-10)が与えられた場合を考えてみます。
原点からスタートして与えられた順番で地点を訪問してみます。各地点から次の行き先までの座標の差分は、(+1, -1), (0, -2), (+1, -2), (0, -3), (+1, -2) になります。
さて、速度は各ターンに±1だけ変化させることができるはずです。上記の隣り合う差分どうしはx,y座標ともに±1以内で増減しています。各ターンの速度を上の差分の通りに変更すれば、1ターンごとに次の地点の座標に移動することができそうです。
実際に宇宙船を移動させてみると、以下のようになります。

宇宙船が全ての地点にうまく到達しました！ 5箇所の地点を5ターンで訪問することができたので、このケースの最適な経路を見つけることができました。

問題ケース

Spaceshipの問題ケースは全部で25個あります。実は、先ほどの例題はこのうちの1つ目のケースであるspaceship01でした。
spaceship01のように地点数が数個のケースもあれば、地点数が数万個に及ぶケースも存在します。ケースによって解法を変える必要がありそうです。
それぞれのケースには特徴があって、大きく分けて以下の3種類に分類できます。実際のケースを見ながら紹介・考察をしていきます。

(1)地点が一筆書きされたケース
まず1つ目です。この種類のケースは端から端へと一筆書きのように並べられた地点が入力で与えられるのが特徴です。spaceship06、spaceship09を例として見てみます。

spaceship06は地点が緩やかな曲線状に並べられています。地点間の間隔に多少差はありますが、どちらかの端から出発して、まだ訪問していない最も近い地点を順に辿っていくことで全地点を周ることができそうです。

spaceship09は一筆書きの要領で地点が並べられてはいるものの、2つの経路が交差する箇所や集中的に地点が入り混じっている箇所が見られます。spaceship06のように最も近い地点を辿っていく方針では厳しそうです。
経路が交差する箇所は2つの経路がなだらかになるように、交差している地点を2つに分類することで、うまく経路を切り分けられそうです。
地点が集中している箇所は、宇宙船の速度が急激に変化しないように経路を決めてあげると良さそうです。速度は毎ターン1のみ増減する制約上、速度の急激な変化はターン数をより消費してしまうためです。

(2)地点が模様を描くケース
次に2つ目です。この種類のケースは特定の模様の形に並べられた地点が入力で与えられるのが特徴です。spaceship21を例として見てみます。

spaceship21は渦巻き模様に地点が並べられています。中心から渦が4つに分かれているので、それぞれを辿ることで効率よく訪問できそうですが、画面端で見切れているのが問題です。例えば、左下、右下、右上で見切れた同じ渦はこれらをそのまま辿るよりも、近くにある別の渦の端と繋げることでより短いターンになると考えられます。
宇宙船は左上の点から始まるので、このスタート地点から模様を辿りつつ、渦の端と端を繋いで一筆書きの経路を作ります。「どの端と端を繋げるか」、「ゴール地点をどこに定めるか」をうまく決める必要があります。

(3) 地点が散在するケース
この種類のケースは地点が無作為に散りばめられているのが特徴です。
1,2つ目では貪欲に近い地点から選んでいくことで効率の良さそうな経路を決められましたが、このケースではその方針は難しそうです。
巡回セールスマン問題（TSP）の要領で経路を決めるとそれなりに効率の良い経路が求められそうです。ただし、本問題では宇宙船は速度を急激に変化させることができないため、速度がなだらかに変化するような経路が理想的です。

解法

私たちの解法は2つの手順に分けられます。

(1)経路を決める

一筆書きのケース
- 両端のうち、宇宙船のスタート地点から近い方の端を始点として、貪欲に近い地点を辿っていく
模様のケース
- 地点の中からスタート、ゴールを決めて、見切れている模様の端同士を手作業で繋げて一筆書きの経路を作成する
地点が散在するケース
- 巡回セールスマン問題（TSP）の要領で経路を求める
  - 焼きなまし法を使って、以下の2つを評価して経路を作成した
    1. 経路の長さ
    2. 経路で隣り合う地点間の速度変化の大きさ
      - 経路の連続する3地点について、1つ目→2つ目の速度ベクトル、2つ目→3つ目の速度ベクトルの変化量に注目する
  - 他にも、後述するDP解法の結果を評価値とした

(2)経路から少ないターン数の手筋を求める

経路に対して最短のターン数を求める動的計画法（DP）を使用
- 具体的には、「経路のi個目の地点に速度が(vx,vy)の状態で到達した時の最短ターン数」を管理する
  - 地点数が多いと実行時間が長くなるため、以下の枝刈りを使用
    - 速度の上限・下限を設定
    - 途中経過でのdpの最短ターン数+αを下界として、遷移する候補を絞る
    - ある地点から別の地点まで到達するためのターン数に上限を設定
- dpの遷移では、以下の問題を解けば良い。
  現在の地点での速度がv1の時、次の地点に速度v2で到達することは可能か？また、可能な場合は最短ターン数とその手筋を求めよ。
  これは実際に解くことができる（詳細は省略）。

結果

前述したケースごとの方針と解法をふまえて、実行結果を確認します。

(1)地点が手動で一筆書きされたケース

spaceship06

スタート地点から近い方の端から順番に地点を辿ることができていますね。
動的計画法を使うことで最短ターン数も達成しています。

spaceship09

経路がなだらかになるように地点を振り分けたことで、宇宙船が不自然な挙動をせずに交差する地点を辿ることができています。
地点が集中している箇所では右往左往することなく宇宙船が動くことができていそうです。

(2)地点が模様を描くケース

温かみのある手作業で模様の端を繋ぎ合わせて効率の良さそうな経路を作成しています（こだわりポイントは画面右下）。
この経路で順位表凍結前まで全体1位を達成することができました。

(3)地点が散在するケース

宇宙船が緩やかにカーブしながら経路を辿っている様子がわかると思います。

感想

とても面白い問題でした！
3日間でSpaceshipの全てのケースに対して解答を提出することができました。
最終日にはSpaceship部門で瞬間的に1位になることができました。
順位表凍結前の時点で、ケースの7割は単独1位か1位タイのスコアで、残りのケースもTOP10以内のスコアでしたが、Unagiチームにリードを許す結果となりました。
チームで協力して解法を組み合わせることで、様々なケースでスコアを改善することができました。特に、ビジュアライザのおかげで一筆書きされたケースや、模様が描かれたケースの経路を工夫して考えることができました（yunixさんありがとうございます！）。
チームHeuristic Artisの名に恥じず、ヒューリスティック形式の問題で良い結果を残せたのではないかと思います。

3d

問題概要

3dでは、問題タイトルにもなっている3d言語というオリジナルの難解プログラミング言語を使って、3d1から3d12の12問の問題を解くことを要求されます。この言語は名前の通り、X軸,Y軸,そして時間軸という3次元空間上で動作するプログラミング言語です。

まずは、実際に3d言語で書かれたプログラムを見てみましょう。

. B .
A + .
. . .

copy

AとBが入力として与えられ、+ は加算を表す演算子です。
例えばA=1,B=2を与えると、上のプログラムは以下のように動作します。

(0ターン目)
. 1 .
2 + .
. . .

(1ターン目)
. . .
. + 3
. 3 .

copy

演算子の左と上に数字がある場合、演算子はそれらを消去し、代わりに演算結果を右と下に吐き出す動きをします。同様の二項演算を行う演算子として、四則演算,一致判定演算,不一致判定演算が用意されています。
また、移動演算子として>,v,<,^が用意されており、これは数字を上下左右に移動させることができます。

(0ターン目)
0 > . . < 1
2 . . . . .
v . . . . ^
. . . . . 3

(1ターン目)
. > 0 1 < .
. . . . . 3
v . . . . ^
2 . . . . .

copy

そして最後に、この言語の大きな特徴である、タイムワープ演算子@があります。
これは、以下のような記法で命令を出します。

. a .
x @ y
. t .

copy

これは、”盤面をtターン遡り、@ 演算子から見て相対位置が(-x,-y)の場所にaを上書きする”という挙動をします。
とは言われてもピンと来ないと思うので、実際に問題を解くコードを動かしてみましょう。

問題例

【3d1】
入力Aが与えられる。Aの階乗を求めよ。

copy

解答コードが以下になります。Aに入力が与えられ、Sで回答を出力します。

. . . 1 > . .
. . . v . v .
. . . . . . .
A > . * . = S
v 1 . . . . .
. - . v . . .
. . . . > . .
. v . . 2 @ 7
. . > . . 4 .
. . 3 @ 6 . .
. . . 4 . . .

copy

これは以下のようなコードを実行しています。最上部にある1がproductで、ループごとに上書きすることで積を更新していきます。

product = 1
while(true){
	if(A * product == product) return product;
	product *= A;
	A -= 1;
}

copy

入力としてA=3を与えた時の実際の挙動を見てみましょう。

なんとなくループしている感じが伝わったのではないかと思います。プログラミング言語というよりはピタゴラスイッチみたいですね。

実行環境

後から振り返るとコーディング環境やビジュアライザを作成するべきではあったのですが、実際のところ3dを担当したほとんどのメンバーはExcelコーディング・脳内エミュレータ実行という力業で解決していました。なんとか可読性を上げようと、色分けを行ったりコメントを付けたりと、各自工夫を凝らしていたようです。
途中でtakumi152が最低限動くシミュレータを作成してくれたので、デバッグはそちらで行っていました。

コードゴルフ

さて、3dの各問題のスコアは、以下で算出されます。スコアは小さければ小さいほど良いです。

(使用した空間の幅) x (使用した空間の高さ) x (使用したターン数)

copy

問題1の解答コードを改めて確認してみましょう。

. . . 1 > . .
. . . v . v .
. . . . . . .
A > . * . = S
v 1 . . . . .
. - . v . . .
. . . . > . .
. v . . 2 @ 7
. . > . . 4 .
. . 3 @ 6 . .
. . . 4 . . .

copy

幅が7、高さが11、ターン数は5ターン必要なので、このコードのスコアは385点となります。もう少し上手く配置することで、スコアを減らせないでしょうか？
Excel上で色々並び替えてみます。人力焼きなましです。

 . . . . 1 > . 
 . . < A * . = 
-1 + . . . v S
 . . . . . . .
-2 @ 3 . 1 @ 4
 . 2 . . . 2 .

copy

お、これはよさそうです！
幅が7、高さが6、ターン数が3なので、126点となります。スコアを1/3にできました！
こんな感じで、ただでさえ読みにくい3d言語を、なるべく小さな空間内にうまく詰め込むことを求められます。難しいですね。

感想

めちゃめちゃ面白かったです！！！
難解言語でコードゴルフをさせるという取り組み自体はMAOなどいくつか先例がありましたが、3d言語はタイムワープという概念を導入した結果として驚くほどの自由さと複雑さを実現しており、3日間考え続けても新しいアイデアが尽きることがありませんでした。
最終日までUnagiと1位争いをし続けることができましたが、副作用としてしばらくは夢の中に3d言語が登場する羽目になりました……。

最後に

参加したメンバー一同、ICFPCを非常に楽しむことができました。
大量の興味深いタスクが与えられて、非常に充実したコンテストでした。始まる前には、やることがなくなったら箱根観光に行くかw、などと言っていたのですが、宿から外に出る暇がありませんでした。

成績も初参加にしてはかなり健闘できて、順位表凍結直前には全体で4位となかなかの位置にいました(これは人海戦術が効く回だったことが大きいですが… これだけのメンバーをこの人数揃えたのは少しずるいような気もします笑)。

もしこの記事を読んで興味を持った方がいたら、来年はぜひ参加してみてください!　個人でも参加できますし、Xなどでチームメンバーを募集しているチームもあるようです。
弊社チームは来年も参加予定です! 対戦よろしくお願いします!

最後まで読んでしまったあなたは、きっと来年ICFPCに参加しているでしょう！

最後までお付き合いいただきありがとうございます。
良かったら、ALGO ARTISのSNSやHPをチェックしてみてください。最新情報をお送りしています。

ALGO ARTISについて：https://www.algo-artis.com/

https://www.algo-artis.com/

最適化ソリューション『Optium』：https://www.algo-artis.com/service

https://www.algo-artis.com/service

化学業界DXソリューション『Planium』：https://planium.jp/

https://planium.jp/

X：https://twitter.com/algo_artis

https://twitter.com/algo_artis

Linkedin: https://www.linkedin.com/company/algo-artis/

【一気読み】【参加記】頭脳のオリンピックに挑戦！ICFPC2024に挑んだ物語

目次

ICFPCとは?

チーム紹介

今年の問題概要

efficiency

問題概要

問題へのアプローチ

最後に

lambdaman

問題概要

問題へのアプローチ

問題5

問題19

spaceship

問題概要

例

問題ケース

解法

結果

感想

3d

問題概要

問題例

実行環境

コードゴルフ

感想

最後に