とすなで！（５） 女子大生とペアプロ 結果発表

【結果発表】女子大生プログラマの心を鷲掴みにした最強のコード8選 - paiza開発日誌

テストケース７のC言語最速レコード該当者は8名（chanさん、macchaさん、Leonardoneさん、miswilさん、hkさん、amoriさん、hakoaiさん、laycrsさん）、0.01秒が最速でした。 

おおっ　（＾＾）　そういえば一度0.01秒出してたんだった。

じつは　とすなで！（３）で作成したコードにとすなで！（４）での工夫をちょっといれていデバッグしている過程で、サーバーの負荷の狭間かなにかのせいで0.01秒を出したことがあったのです。

基本的には（３）のアルゴリズムでクリアしていたような状況です。

これ自体でも読み込みテーブルやRun Lengthテーブルの削減などアルゴリズムを簡略化しかつちょっと速度をあげるという工夫をしているのですが、0.01秒近辺だと分解能が足りなくて、コード修正が効果があったのか計測の誤差なのかが区別がつきにくくなって今一つコード修正のモチベーションがおこりませんでした。

そこで自前のテストケースとclock()による自前の時間計測を準備しつつ改良をしてはみたのですが、やっぱり分解能が足りませんでしたので、あとはテストケースをさらに大きくするしかないということになり、その辺でフェードアウトしてしまったという・

このアルゴリズムは基本的にO(H×W×H'＋N)のオーダーです。

このアルゴリズムは配置可能領域の連続性を最初に調べるので、各マスごとの探索はH＞H'を期待できるようになってますのでそこそこの速度が出たといえます。

実はこのアルゴリズムは少なくともまだ2段階の改善の余地というかアイデアが残ってまして、配置可能領域の連続性をベースにもとのH×Wの探索領域をさらに半分程度にする改良アイデアと、さらに半分ぐらいにできそうなアイデアがあったのですが、結果的にどうもコードが綺麗にならないので、そのまんまになってしまいました（＾＾；

機会があればいずれ解説してみたいと思います。