#procon26「石畳職人Z」のソースと簡単な解説
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
README.md
dancing_links.cpp
dancing_links.hpp
main.cpp
procon26.cpp
procon26.hpp
type_definition.hpp

README.md

まきとまと

言語

  • C++14(ソルバー、回答提出システム)
  • PowerShellのスクリプト(問題取得&ソルバー起動用)

ライブラリ

  • C++標準ライブラリ
  • Boost(Filesystem, Optional)
  • SDL2, SDL2_ttf

アルゴリズム1

ここに上がっているやつはこれの実装です。
基本的にはDancing LinksとAlgorithm Xを使ってペントミノを解く方法に、今回の問題の特有の条件(石を置ける場所とか順番とか)を組み込んだだけです。
簡単に説明すると、一番おける石が少ないところ(=狭い)ところを優先的に埋めていって、おける石がないマス(空きマス)が出たらバックトラックする感じです。
人間が見たら明らかにその先に答えがないのに、解を求めようとすることが多々あるので、状況を見ながら人間がリセットをかけるようにしてあります。
空きzkに対して石の合計zkがだいたい1.5倍以上あると割りと埋まるのですが、そうでないと綺麗に空きマスを残してしまいます。

アルゴリズム2

深さ優先探索のアルゴリズムです。人間の手がいらないので、アルゴリズム1の後ろで動かしていました。
アルゴリズム1で詰む問題も、これだと良い答えが出せる時がありました。 もう一人のメンバーが作ったもので、ここにはソースはないです。

回答提出システム

最後に出したのが回答になってしまうので、複数台のPCで解く場合は1回どこかに回答を集める必要があります。
運営サーバー側で最良の解を最終回答にしてくれれば...
うちのチームでは↓みたいな感じで実現しました。

  1. まず、回答ができたらWindowsのネットワーク共有機能を使って、サーバーとなる1台のパソコンに回答を書き出します。
    例えばC++だとifstream f("\\SERVER_PC\ans\hoge.txt");みたいに書けば勝手にSERVER_PCのansにファイルが作成されます。実際は回答ファイルの名前はソルバのインスタンスごとに違わないと衝突してしまうので、起動スクリプトが適当に乱数を決めてそれを使うようにしました。
  2. サーバーとなっているパソコンでは500ミリ秒ごとに回答をチェックして、更新されていればそれを送信します。

結果

準決勝2回戦2問目で敗退

  • 1回戦

    • 1問目 1位
    • 2問目 2位
    • 3問目 6位
  • 準決勝

    • 1問目 2位
    • 2問目 10位(9位以上が勝ち抜け)