SuperCon 2022 参加記

はじめに

　チーム「sns」で SuperCon 本選に出場しました！今年で 2 回目です。

予選

　厳密解があっさり出てびっくり

本選

問題概要

1000頂点2000辺の有向グラフがあるよ (実際はオートマトン)
各頂点からランダムな頂点へ2本辺が生えてるよ
それぞれ a と b というラベルが付いてるよ
頂点には 0 と 1 が書き込まれてるよ

a と b からなる 500 字くらいの文字列が 2000 個あるよ
これらを適当な頂点からラベルに沿って移動させ、最終的に到達した頂点に書かれていた数字を記録していくよ
開始した頂点と記録された数字の組み合わせで文字列を区別するよ

1000 頂点全てをスタートに選んだときと同じように文字列を区別することができるような頂点の組み合わせのうち、なるべく選んだ頂点の数が少なくなる & 頂点番号の和が小さくなるようなものを答えてね

かな～～り分かりづらいため「1000桁の2進数が2000個あるよ！1000桁のうち何桁かを、選んだ結果元の種類数と等しくなるように選んでね！」というような問題だと思ってもらえれば良いです。

変数名

一々言葉で説明するのも分かりづらいため各変数を以下のように定義します。(括弧内は制約です)
n : 頂点数 ( n=1000)
m : 文字列数 ( m=2000)
w : 文字列長の平均 ( w=500)
k : 解として出力した頂点の数 ( 1\leqq k \leqq n)
loop : 1 回の山登りで近傍をとるおおまかな回数 ( loop=2000)

最終的にやったこと

  • 60 秒間 48 並列で大量に山登りをしよう！
  • 条件の判定がネック ( O(km^{2})) だから Zobrist Hash と hash set を使って高速化しよう！

　通称「下手な鉄砲も数撃ちゃ当たる」作戦です。
　この解法では (たぶん) 一回山登りをするときの計算量が O(loop(n+m\ log\ m)) になるのですが、富岳パワー & 並列化パワーで概算で 10000 回ほど山登りをすることができていました。すごい
　また前計算の計算量は O(nmw) と激重でしたが、こちらは OpenMP の力で 0.15 秒程で終わっていました。

本選中にやっていたこと

開会式(1日目)

　8:30 に起床
　前日？寝たのが午前 3 時とかだったため眠気に襲われながら開会式に参加しました。(実際後半 1 時間くらいの記憶がありません)
　参加者一覧を見ていると、チューターに去年同じチームで本選に参加した mencotton さんがいてびっくり。

　問題のテーマはオートマトンを使った文字列の分類だと判明。
　去年は感染症の疑似モデルを使った実験のような問題だったため、急に抽象的な話題になったなと思うなどしました。
　この時点で条件判定パートの計算量が [tex: O(m2)] なのはまずいという話になり、hash を使った準線形の判定を実装することを決定。

1日目

　サンプルコードを参考にやりたいことの実装 (hash による判定、焼きなまし) をほとんど進めました。
　いい感じの解が出てくることを期待し、富岳で動かしてみるとジャッジに「出力が条件を満たしてないで」と怒られてしまいます。
　結局この日はこれの原因が分からずに時間が来てしまいました。

　夜は富岳を使うことができないため、Python を使ってスコアの挙動を調べたりしていました。

2日目

　前日のバグの原因が「全ての入出力例について全ての文字列を区別することができる」と勘違いしていたためだと判明します。
　これを直し投げますが、まだ通りません。
　その後、バグの原因のうちのひとつが「2進数 mod 2^{61}-1 を hash として使っていたから」だと判明します。何で衝突しないと思った？？？

　↓ちなみにこれはまだそのバグに気付いていないときの発言です。

これはなんですか

　しかし、それでもまだ条件を満たしている解が出力されません。
　2日目はほぼ何も解決しないまま過ぎて行ってしまいました。

3日目

　この日も午前中はバグと格闘していましたが...

　午後1時頃、Zobrist Hash と hash set を採用することで、やっと全てのケースで条件を満たすような解の出力に成功します。
　その後はこれをベースに改良を進めていき、最終的に平均で k=58 くらいの解を出力できるようにしました。

4日目

　探索パートの試行回数をもっと増やせないか？という話になり、OpenMP による並列化の実装に取り掛かります。
　普段並列化なんて実装しないためバグの量がとんでもなく、最終的に正常に動くコードが完成したのは 12:24, 提出期限の 30 分程前でした。
　並列化した結果、上手くいけば k=49 くらい、悪くても k=60 くらい、平均 k=55 くらいの解を出力するようになりました。

　ただ期限ぎりぎりまで動かなかったコードですので、審査時に上手く動くかどうかはかなり心配でした。

5日目

　結果発表～～～～～！！！！！(120db)

　閉会式にて実装時の工夫などを喋った後、遂に結果発表の時間がやってきました。

　結果は......

　公開ダメらしいので伏せます(入賞は逃しました)

おわりに

　普段 Python をメインで使っていることもあってか、かなり実装スピードが落ちてしまった印象がありました。
　来年は参加できるかどうかかなり怪しいですが、もし参加できたらリベンジしたいですね。