60

超苦労したのでメモ。以下ネタバレ注意。

とりあえず状態空間がどのくらいの大きさになるのかが全くわからなかったので、自分の中でかなり広めに設定しておいた。

• 普通に集合を作る
• グラフを作って、ノード数が5の完全グラフを探す

とかを考えたんだけど、あまりにも大量に素数を用意しすぎたせいでかなり無理があった。素数を3で割ったときの余りが1の集合と2の集合に分けて、その集合の中だけで処理をしてみたんだけどそれでも無理。まあ当然だけど。

手順としては、とりあえず深さの限度がわからないので、適当にBFSで一個解を探した。次にそれを上限値にして、それ未満になるような解を探す。後は収束するまでそれを繰り返すだけ。探索速度がどの程度あがるかはわからないけど、上の(mod 3)で分けた集合内だけで探索してみた。意外と早く求まった。