AHC018(水路掘り) 参加記 173位/1086 解法と細かいテク

in/0002.txt

試し掘りした箇所 (BFS + Grid)

問題

提出

私の環境

  • Windows 11 + WSL2

大まかな解法

  • グリッド状(飛び幅10)にサンプリングして最小全域木（森）のように構築する
    • 掘るのに成功：ほぼ固さが分かる
    • 掘るのに失敗：固めに仮設定
    • 座標的に近い点同士を辺として張る。遠い辺は信用できないので張らない
  • 最短距離はワーシャルフロイドを使ったがダイクストラでもよい

細かい事

  • BFSサンプリング：水源、家を始点としてBFSで(飛び飛びの)サンプリングを実施。掘る合計パワー40以内で成功したら4方向に伸ばす。1度サンプリングした点の周辺は再度サンプリングしない
  • グリッドサンプリング：上記でサンプリングしきれなかった箇所もグリッド上にサンプリングする
  • 凸包：水源と家を点とした凸包内のみサンプリング。実際は少し膨らませた
  • 水源除去：マンハッタン距離で最短の家と接続していない水源は除去。水源４、家１などの事もあるため

テク.cpp

  • 実装の可視化のため、テキスト形式の画像(pbm形式)を作成。ブラウザで見たいのでこの後imagemagickでpngにしている
void write_as_image(){
  ofstream of("dig_image.pbm");
  if(!of){
    p("#file can't be opened");
  }
  of<<"P1"<<endl;
  of<<"200 200"<<endl;
  rep(i,200){
    rep(j,200){
      if(accumulated_dig[i][j]==0){
        of<<0;
      }else{
        of<<1;
      }
    }
    of<<endl;
  }
}

テク.py テスト並列化

  • import threadingでテストの並列化。Python 3.7以降なら最初から入っている。これによりタスクマネージャーでのCPU使用率が100%に

テク.sh

# 標準エラー出力をファイルに保存
myprogram 2> error.log

# copy to clipboard
cat out.txt | clip.exe

# 連結実行
# 例
gpp ../answer.cpp && gpp -o b.out ../base.cpp && python a.py && python img.py

テク.その他

  • 最後に提出したファイルをb.cppとしてバックアップしておき、それをコンパイルしたb.outと現在作成中のコード(a.cpp, a.out)をRustのテスト100件などで比較する
  • それぞれに勝ち負けを出して統計的に改善していると自信が持てた時のみ提出する
  • これにより無闇に出して30分待つことはなくなるし、暫定テストケースに最適化されてしまうこともなくなる

コンテスト後

  • Twitterの#AHC018タグで他の人の解説を読む
  • すぐ取り入れられそうと思ったのは、掘るパスを決めたらパス上のいくつかを掘ってみて再度距離計算する方法
  • 皆さんのeditorialも読もう