初マラソンマッチ!(AHC001 雑感)

楽しい

 

 

概要

シンプルな更新で山登り法を書き、それを焼きなまし法に伸ばした。

時系列順やったこと

  • ラソンマッチの入門記事を読み込む
  • 必要な部品の作成 (スコア機能や、重なってないかの判定機構)
  • 長方形を1つ選び1方向更新する方針で、山登り法を試す(452くらい)
  • 上に加えて、長方形を2つ選び同じ方向に微調整する方針を実装(a[i] += diff, c[j] += diff 的な)。それで山登り法を試す。(476くらい)
  • 焼きなまし法を試す。(480くらい)
  • パラメタの調整。スコアが頭打ちになる(481弱)
  • 他の更新方法を試す ->うまくいかず・・・

感想

人生初焼きなましだったが、山登り法ができたら焼きなましするのは比較的容易

ただしパラメタ調整は限界がある

なので、頭いい変遷やスコア関数を考えるのが本質パートっぽい。いろんな作戦を思いつけるよう、今度はもっと時間をかけようね!(前日からやった人並感)

パソコン由来の制約あり。途中のビジュアライザが欲しかったけど時間的・技術的にあきらめた / 同時に何パターンも走らせてスコア評価したかった、など。今度はもっと時間をかけようね(前日からやった人並感)

問題由来、データ由来の作戦が取れるといいね。

 

以下Twitterを眺めて思ったこと:

差分計算をO(1)でやってたけど、nが小さいのでO(n)でもそんなに重くない。O(n)だともっと複雑な遷移ができそう。

テストケースやスコア関数を眺めるのは大事。

「面積の和が全体&面積Overしても減らせばよい、ので最初から全領域含める」とか見かけていいなと思った。

「あとはスコア関数は比率1の付近で大体二次で、そのせいで面積比率がそこそこ(0.8くらい)でも十分なスコアなので、位置関係上厳しいところ先にあるていど確保する」とか。

焼きなましの解説書に「スコア関数をいじる」とあってんなもんできるんかよと思ったら、「重なりをゆるしてペナルティを与え、時間と共に増やす」というのを見かけた。すげー

焼きなまし以外(貪欲やビームサーチなど)を局所的に挟むのはあり。検討はしたが頭を使いたくなくて()やめちゃった。 

近い長方形をどうにか触りたくて、結局ランダムに頼ることにしたけど、木構造を使うとか言ってる人がいてなんか怖い。

 連続最適化ってなに?怖そう