2011 TCO Marathon Match Round2 : QualityPolygons

TopCoder

赤コーダーの安定感すごい。結果が出たらまた追加で書くつもり。採点システムについてとか、順位表の使い方とか、考えていたこととか。

解法の前提

small(点の数<500)とlarge(点の数>=500)は別物。smallでは最適解を目指さないと上位は厳しい。
あと、向こうのサーバはgettimeofdayのコストがやたら高い。なので一部では時間の計測をカウンタで代用。
また、large解法もsmall解法も速度は割と重要。

large解法

  • まず前処理として各格子点についてある近傍内にある距離の近い点を計算してソートしておく。
    • 愚直にやると時間をとられるので、ローリングハッシュを計算するように出し入れしながら処理する。
  • 後はnの大きい方から、n角形を愚直に探す。具体的には円の中心や半径を小刻みに動かしながら円の周付近を調べ、辺の制限や半径の制限や凸の制限を満たしそうな点をn個集める(このとき前処理を利用)。あとはチェックしてみて大丈夫なら即採用。
    • 凸の制限を簡易的にチェックするのには行列式の符号を見ればよい。
  • 少し工夫した点として、探す範囲(円の縁のまわり)における点の濃度を計算して，濃いところでは刻み幅を小さくして、そうでないところでは大きくしたりした。
    • 濃度の計算は真面目にやると時間を食うので中心をくりぬいた四角形の部分和で代用。BITだと遅い((log 700)^2は100もある)ので、累積和で代用。更新はたまにしかしない。
    • 効果は微妙。だけど無いよりは確かにマシ。
  • 最後に三角形を落穂拾いして終了。書いてみると工夫は少ないけど、こんなでもそこそこ戦えた。

small解法

  • 点の数が多めで制限が緩めのときはlarge解法を利用する。
  • それ以外のとき、今度は探索でn角形を探す。
  • やはり前処理で各N個の点について、他の点までの距離を求めてソートして持っておく。
  • 探索の方法は、まず２点を決める。それから仮の重心を決めて、後は辺の制限や半径の制限を満たすような次の点を選びながらDFSする。
    • 辺の制限を満たすような次の点を選ぶのに前処理で計算しておいたもの+lower_boundを使う。
  • この方法だとそこそこ枝刈りが効いて六角形くらいまでなら間に合う。
  • これでそこそこ稼げるのだけど、発見即採用ではダメな場合もある。選ぶ順序は重要。
    • 例えば、この五角形1個を採用してしまうと他の五角形2つが使えなくなってしまう、とか。
  • これを回避する方法は正直全然思いつかなかったので、多スタート法で何度も反復して一番良いものを選ぶことにした。
  • 三角形の落穂拾いはここではかなり重要で、発見即採用をやめると得点が劇的に伸びる(3点くらい)。
    • 代わりにどうするかというと、制約を満たす三角形を全部列挙して、各頂点の重複回数の最大値が最小のものから貪欲に選ぶようにする。

問題点

  • このlarge解法は直感的に無駄が多いし、その上歪な多角形の検出が下手という致命的な欠陥を抱えている。
  • small解法も頭の良いやり方がありそうな気がするんだけど、結局最後まで分からなかった。多スタート法じゃ最適解の検出があまり期待できない。
  • 中盤まではsmallの点が取れなくて四苦八苦していたけど、最終盤はむしろlargeの方で点を落としていた気がする。
  • そもそもsmallとlargeを完全に別ゲーとして捉えるべきかどうかも断言できない。
  • パラメータの調整が不完全。結果的にpretestだけに頼っているので過学習の可能性大。
    • 実は自分は今まで100% provisional rank <= final rankになっている。等号成立は１位を取ったときのみ。

懺悔

  • submit回数がやたら多くなってしまった。ローカルが遅すぎるから向こうで実行しないと効果がまったく分からない。だから仕方がなかった、というのが言い訳なんだけど、単にO2オプションつけてないだけでした。

目標達成度

  • 実は今回は始まる前に目標を立てていた。
    • 相当酷い出来だった前回(クロスワード)の反省を生かすこと。
    • visualizerやtesterをきちんと作る。
    • スクリプトを準備してパラメータの調整を自動化する。
  • まず一つ目。前回の反省はそれなりに生かすことができたと思う。
    • 前回は方向性を間違えたまま(その方向性は正しいと思い込みながら)走りつづけてしまったので、今回は小手先の技術で点を稼ぎにいくというよりは正しい方向性を探すことにリソースを割いた。
    • とはいえ、最初の1週間は間違えたままだったので、その初動の遅れが後に響いたという説はある。
  • 二つ目。visualizerやtesterなどの環境の整備には気を配った。
    • Makefile書いて分割コンパイルして、というのは基本。
      • あとで関数をinline展開するときちょっとハマったけど。
    • testerは公式のものを忠実に移植した。
    • visualizerは結構機能を取り揃えたつもり。機能としては
      • 点の表示/非表示
      • 特定の点の強調/非強調
      • n角形のみ表示/非表示
      • ある領域の拡大/縮小
      • 各点を、テストケース生成の際に用いた円毎に色分けして表示
      • グリッドの表示/非表示
      • グリッドの幅変更
    • visualizerが本当に役に立ったかどうか、は微妙。でも結果を見て楽しかったのは事実。
    • セグフォしたら即gdb。
    • 終盤はプロファイラも使った。結果的にはそんなに使いこなせなかったけど。
  • 三つ目。パラメータ調整の自動化。これは全くできなかった。
    • そもそもパラメータ調整をするためにテスターを走らせるマシンが無かった。
    • eclipse使ってコーディングしながらテスター走らせたら落ちた。仮想環境が。

役に立たなかったもの

  • 最初の１週間はバケット法みたいに解像度を下げた状態で探索していたけどあまり役に立たなかった。
    • 本当にこれがド本命だと思っていた。
  • n角形を見つけたら2*n角形にならないか試す。夢物語ですね、はい次。
  • 円の中心を検出する。ハフ変換とかあるらしいけどそのままでは役に立たなすぎる。