ICFPC2025参加記

こんにちは、Digital Experts でエンジニアをしている仲吉です！

この度、Digital Expertsと丸紅デジタルイノベーション部の社員7名、そしてインターン生7名¹で構成されたチーム「DIgital Experts」として、ICFPC2025に参加しました。

Digital Expertsは2023年に設立された丸紅の機能子会社で、会社としてICFPCに参加するのは初めてです！ 初参加にあたってどのように取り組んだのかをご紹介します！

また、社内で定期的に開催しているLT会でもICFPCの概要や取り組んだ解法などについて発表しました！ その際の資料も部分的に記事に用いています。

コンテスト概要

ICFPC2025（ICFP Programming Contest 2025） は関数型プログラミングに関する学会が毎年開催しているプログラミングコンテストで、次のような特徴が有ります！

• 少し変わった問題が出題される
• チームの人数や所属に制限がない
• コンテスト時間は72時間
• 途中で問題設定に変更が加わることがある

人数が多い方が有利なこともあるため人海戦術を取りたいのですが、弊社だけでは十分な人数を確保できませんでした。 そのため、弊社社員だけではなく、丸紅DI部社員やインターン生にもお願いして同じチームとして参加してもらいました！

開催時間は日本時間で金曜21時から月曜21時まで。全員が最初から最後まで参加するのは難しく、途中参加・途中離脱するメンバーがほとんどでしたが、DE社員は全員最初から最後まで参加しました！

準備

宿

参加にあたり、みんなで集まって作業できる環境が重要です。また、「温泉に入りたい！」という強い要望があったため、温泉付き、または近くに日帰り温泉がある宿を探しました。

条件を満たす宿は少なく、ICFPCへの参加を決めたのが開催約1ヶ月前であったため、その少ない宿もほとんど予約が埋まっていました。最終的には、72時間連続で会議室を借りられ、ほぼ24時間入浴可能な温泉付きの施設に決定しました。

施設は海沿いにあったため、眺めもよかったです！

開発環境

問題によっては計算リソースを有効活用できると有利になるため、AWS環境を用意し、コンテスト中はメンバー全員が自由に利用できるようにしました。

実際に重い探索を伴う問題が出題されたため、高性能インスタンスを立てて活用しました。さらに、問題上アクセスする必要のあるAPIがEUサーバーにデプロイされていたため、応答速度の面でも多少有利に働きました。

コンテスト中の様子

コンテスト前

参加者は宿泊施設に現地集合としました。 コンテスト初日は台風の影響で東海道新幹線が大きく遅延していたため、当初は19時ごろ到着予定でしたが20時半ごろ到着となり、大急ぎでコンテストに向けて準備をしました。

1日目（最初の24時間）

まず、問題が公開されてからしばらく、各自で問題を把握して練習問題を解く時間を設けました。 これは他の人の解法に影響を受けず、多様なアイデアを出すためです。 しかし、チーム全員が共通のステートフルなAPIを利用する必要があり、「誰がAPIを使うかを宣言してから実行する」という運用になり、効率がとても悪かったです。 後ほどの反省点にも含まれますが、この段階で各自が使えるシミュレータを実装し始めるべきでした……

1日目の時点での問題概要は次のようなものです。

1日目の問題概要

$N$ 個の部屋からなる図書館があり、各部屋には $0$ から $5$ の番号が付いた $6$ 個のドアがあります。 ドアとドアはつながっていて、他の部屋のドアだけではなく同じ部屋のドア、もしくは同じドア自身とつながっている可能性があります。そして、あるドアを通ると接続先のドアがある部屋に移動します。 部屋はその部屋に書かれたマークでしか区別することができず、マークは A, B, C, D の4種類です（実際には、A, B, C, D ではなく、0, 1, 2, 3 が使われていました）。

目標はこの図書館の地図を作ることです。ここで、地図というのはすべてのドアに対してどのドアと接続しているかを表したものを指します。

地図の作成に必要な情報はロボットを操作して図書館を探索することで得ることができます。ロボットには通るドアの番号列で指示を出すことができ、そのときに通過した部屋のマークからなる文字列のみを取得することができます。

ただし、指示を出すときは番号列をまとめて与える必要があり、探索途中で次にどのドアを通るのかを決めることはできません。

簡単な例

例として、ドアが4つある3つの部屋から構成される図書館を考えましょう。

リクエスト毎にロボットがスタートする部屋は A だとします。そして、私たちが次のようなリクエストを送ったとしましょう。（スキーマは改変しています）

1
2
3
4
5
6

{
  "requests": [
    "0123",
    "0000"
  ]
}

すると、次のようなレスポンスが返ってきます。

1
2
3
4
5
6

{
  "responses": [
    "ABBBC",
    "ABABA"
  ]
}

一つ目のリクエストに対するレスポンスは、最初に部屋 A にいたロボットが 0 番のドアを通って B に移動し、その後 1 番のドアを通って B に移動、 2 番のドアを通って B に移動、最後に 3 番のドアを通って C に移動したことを表しています。

一つの問題に対して複数のタスクが存在し、各タスクは部屋の数 $N$ だけが異なります。 タスクの挑戦を開始するタイミングでランダムに図書館が生成され、作成した地図を提出すると正誤判定がなされてその回の挑戦は終了します。

そのため、毎回違う構造の図書館に対して地図の作成を試みるということを繰り返すことになります。

スコア計算

正しい地図を作成できたときのスコアは探索の回数で決まります。 この問題では、一度に複数の探索をリクエストすることができ、返ってきたレスポンスを見て次のリクエストを送ることができます。

ここで、リクエストを送った回数と、探索の回数の合計がスコアになります。このスコアの最小化が目標です。例えば、1回目のリクエストで1回探索し、2回目のリクエストで2回探索を行った場合、スコアは5になります。

リクエストの送り方とスコアの仕様

探索の結果は次に送るリクエストで活用することができます。 そのため、スコア上は同じリクエストで探索したいですが、情報を有効活用するためにはリクエストを分割したくなるというトレードオフがあります。

また、各タスクのスコアはそのタスクでの最小スコアによって決まるので、確率的な方針で $1$ 回でも小さいスコアを取ることができれば十分であることも非常に重要でした。

1日目の方針

この問題の難しい点は主に2つあり、1つ目は現在いる部屋がどこなのかわからない点、2つ目はすべてのドアについて対応しているドアを見つけないといけない点です。

この2つをどのように解決するかが問題になりますが、最初の練習問題では1つ目は考える必要がありませんでした。

練習問題（すべての部屋が識別可能な場合）

最初の練習問題 probatio は3部屋かつすべての部屋のマークが異なるため、適当に探索を行って全部のドアを開けることができれば正解が得られる問題です。

そのため、適当に長い探索を 1 回やって、整合性が取れているドアの接続関係をDFSで求めるという方針を取ると、時々正解が得られるのでスコア 2 を獲得できます。

また、次のような確実な方法もあります。

簡単のため、ドアを4つとします。まず、最初の部屋を A としたとき、A から出ているドアがどの部屋につながっているかわからない状況です。

ここで、ドアを1回だけ開ける探索を 4 回行うと次のように、各ドアがどこにつながっているのかがわかります。

1
2
3
4
5
6
7
8

{
  "requests": [
    "0",
    "1",
    "2",
    "3"
  ]
}

後は、部屋Bと部屋Cのドアがそれぞれどの部屋につながっているか確かめるだけです！そのため、次のようなリクエストを送って調べます。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

{
  "requests": [
    "00",
    "01",
    "02",
    "03",
    "30",
    "31",
    "32",
    "33"
  ]
}

これで、すべての部屋についてドアの行き先がわかったので、地図を作成することができます！ スコアとしては、2回のリクエストでそれぞれ4つ、8つのリクエストを送ったので、$(1 + 4) + (1 + 8) = 15$ となります。

部屋 A から部屋Bと部屋Cのどちらかにしかつながっていない可能性もありますが、その場合はもう一回リクエストを増やせば大丈夫です。

ちなみに、各ドアがどの部屋につながっているかだけを確かめており、どのドアにつながっているかは考えていません。適当に矛盾しない組合せを提出したら正解できます！

部屋がマークだけで識別できない場合

練習問題以外は部屋の数が $6$ 以上になるため、マークだけでは識別できなくなります。

そのため、どのようにして同じマークの部屋同士を識別するかが一番の問題となります。もし部屋を区別することができたら、先ほどの方法でそれぞれの部屋からすべてのドアを開ける探索を行うことで地図を作成することができます。

最初に出てきたアイデアは、あるドアの開け方の列を固定して、その探索に対するマーク列を用いて識別する方法でした。違う部屋であれば同じマークであっても、同じドアの通り方をしたときに出てくるマーク列は異なるだろうという発想に基づくものです。 この固定したドアの列のことをシグネチャと呼んでいました。

シグネチャを使うとすべての部屋を識別することができ、各部屋からそれぞれのドアを開けたときの部屋ももう一回シグネチャを使って識別することができます。スコアがある程度大きくなってしまいますが、これで1日目の時点の問題はすべて解くことができます！

日本時間で9月6日(土)午前1時30分頃に、全体で1位となりました！ この後、シグネチャを 1111111 のように同じドアを連続させると少し効率が良くなることを用いて改善しました。

また、この頃には他のチームが $N \ge 6$ の問題でスコア $2$ を出していたため、$1$ 回の探索でも十分解けるということがわかります。そこで、探索を $1$ 回だけ行って、DFSや焼きなまし法で整合性がある地図を作成する方針を数人で進め始めました。

DFSによって $N=6$ のタスクをスコア $2$ で正解することができましたが、$N > 6$ に対しては探索するべき要素が多く時間がかかりすぎてしまいます。そのため、焼きなまし法で解けるように評価関数・状態の持ち方・遷移などを試行錯誤しているうちに24時間が経過しました。

ちなみに、焼きなまし法やDFSで解くためには $1$ 回の探索でできるだけ多くの情報を得る必要があります。そこで、探索につかうドアの番号列についても焼きなまし法で生成しました。

練習問題について

ところで、練習問題は $N=3$ と非常に部屋の数が少ないです。また、送る回答はドアを通った後のマーク列が同じであれば正解と見なされます。そのため、正解となる確率がとても高い解があり、探索を一度も行わずにその解を送り続けることが考えられます。

実際に同型の図書館が多そうなドアのつなぎ方を考え、それを送り続けてみたところスコア $0$ で正解することができました！

正解したときにはチーム全体で喜んでいたのですが、正解しても順位は上がりませんでした。 不審に思い確認してみたところ、コンテスト序盤で全体スコアに含まれていたのはバグだったため修正されたということが、コンタクト用の Discord で告知されていました…..

コンテストのDiscordにはちゃんと参加するようにしましょう。

2日目以降（24時間目以降）

24時間経過して Lightning Round が終了すると、新しい問題設定の追加とその問題設定に対応したタスクが追加されました。

2日目の問題概要

$N$ 個の部屋がある図書館に対して、部屋をすべてコピーして別の層を作成します。そして、部屋同士の接続は、ランダムに別の層との接続に置き換えられます。層の数は $2$ 層と $3$ 層の2種類があります。

ロボットが行える行動も追加されます。移動に加え、現在いる部屋のマークを指定したマークに書き換えるという指示ができるようになります。

簡単な例

例として、次のような $N=2$ の図書館をまず考えましょう。

これを複製して、部屋Aのドア1と部屋Bのドア0をつないでいる辺を別の層との接続に置き換えます。 更に、部屋 B のドア 1 とドア 2 をつないでいる辺を置き換えてみると、次のような図書館になります。

便宜上 ' を付けていますが、それを無視すると A から出発しても A' から出発しても、同じドアの通り方であれば同じマークの部屋にたどり着くことが確認できます！ そのため、このようにして作成した図書館では、いくら歩き回ったとしても A と A'、B と B' はマークを書き換えない限り区別できません。

そこで、途中の部屋でマークを書き換えることでコピー先と区別する必要があります。

2日目以降の方針

元が同じ部屋同士をどのように区別するかが問題になります。ただ、層を区別せずに $N$ 部屋の図書館として見たときの構造を少ないリクエスト数で特定できないと、複数層ある場合にもスコアが悪くなってしまいます。また、1日目のタスクも引き続き順位に関係するので、他のチームと同様にスコア $2$ で解けるようにする必要があります。

そのため、引き続き $1$ 層をスコア $2$ で解く人と、$1$層が解ける前提で複数層を解く人に分かれて取り組みました。

スコア $2$ で $1$ 層を解く

スコア $2$ で $1$ 層を解くには、適当な長いリクエストを送り、その結果に対して実際の部屋がどれだったかを割り当てる必要があります。そのために、焼きなましで実際の部屋がどれだったかを割り当てることを試みました。

重要な特徴として、部屋に書かれたマークは部屋番号の下 $2$ ビットを表していることがあります。例えば、部屋の総数が $6$ の場合、マークは 0, 1, 2, 3, 0, 1 となっていました。そのため、レスポンスのマークに対して、そこに割り当てられる可能性のある部屋は絞られます。

焼きなまし法を用いるにあたって、次のような評価関数を設定しました。

• 同じ部屋が割り当てられていて次に使うドアが同じとき、それぞれのドアを開けた後の部屋が違うときにペナルティを与える
  • 例：リクエスト 0000 でレスポンスが ABACB だったとき、最初の A と次の A は異なる部屋
  • レスポンスが ABABC の場合でも、00 を開けた後が A と C になっており異なる部屋だとわかる
• 部屋に必要なドアの数が $6$ を超えたらペナルティ
  • 部屋割り当て後、ある部屋につながっている(部屋, ドア)の組合せが $6$ を超えることがある

ただ、この焼きなましで解くにはとても時間がかかるため AWS のc7a.48xlarge のインスタンスを使い、$N=30$ のタスクでスコア $2$ を達成することができました！

複数層を解く

複数層の場合、層を区別しないときの $N$ 部屋の地図を先に作成し、その地図をもとに各部屋がどの層に属しているかを特定するためのリクエストを送る方針を最初は取っていました。しかし、上位のスコアを見るとそれよりも削減できるということがわかり、$N$ 部屋の地図を作るためのリクエストと適当に部屋のマークを書き換えるリクエストを同時に送ることでリクエスト送信回数を削減しました。

ただ、$2$ 日目の問題設定では $1$ 回の探索で開けられるドアの数も少なくなり情報が足りません。 そのため、層を区別しない地図も、矛盾が発生しない割当だとしても間違っている可能性が高くなります。さらに、層の割当が無矛盾であっても正解であるかはわかりません。

解法の実装ができても、各タスクに対して実行を繰り返して正解が出るまで見守る必要があります。

また、宿泊していた施設から車で30分ほどのところにさわやかがあるので、最終日の昼に食べに行ったりもしました。

結果

$2$ 日目以降の問題に対しては合計で $10$ 個のタスクがありましたが、コンテスト終了時までに最終的な解法で解けたのは $8$ 個でした。残りの2問は、2日目が開始してから数時間で達成したスコア $1421, 1391$ のまま終了しました。

ただ、そもそも正解できているということと、他の問題では上位勢と並ぶスコアを出せていたため、結果としては全体で 11 位となりました！ ICFPCに挑戦するのはほぼ全員初めてという状況だったので、11位という結果はまずまずだったのではないかと思います！

感想・まとめ

会社として初参加でありインターン生にも参加していただくということで、準備から少々不安がありましたが特に問題が発生することもなく無事終えることができました！あまり会話したことのないインターン生同士や社員とインターン生の組合せもありますが、今回のICFPC合宿では参加者同士の交流も盛んに行われて非常に良い機会となりました！

コンテストの反省点として、多人数で参加するチーム戦に慣れておらず、情報共有や役割分担がうまく行えていなかったことがあります。 問題の仕様に関する同じ勘違いを複数人がしていたり、シミュレータなどの便利ツール作成が遅くなっていました。また、問題を解くこと自体がおもしろすぎるため人が集中してしまい、ビジュアライザなどは最後まで作成されませんでした……

72時間のコンテストは周辺環境の整備が後々とても効いてくるということは実感できたため、来年以降に活かしていきたいです！

おわりに

今回のICFPC参加は会社イベントとして行いました。今後もこうした技術イベントを含め、様々な取り組みを行っていく予定です。

Digital Experts株式会社はインターンシップ・新卒採用・中途採用のいずれも積極的に行っています！ 興味のある方は採用ページをご覧ください。