2014 TCO Marathon Round 2

とぷこだ 参加ログ

マラソンマッチに参加した。

モチベ

最適化力を高めていきたいので、できるだけいろんなマラソン系マッチに参加して勉強したい。
というか限られた時間だとしてもよい解を出せる能力身につけたいあああああ

問題

幅A[i]高さB[i]の箱がN個与えられる。
箱はx軸y軸に並行に配置しなければならないが、90度回転させることができる。箱は接することはできるが、重ねる事はできない。
箱によって囲まれた領域を作る。(領域の個数^2) * (領域の面積)を最大化したい。

やったこと

  • 領域の個数は1つで、領域の面積を大きくするとどの程度いくか？を見るために、できるだけ大きな正方形(ダイヤ形ではない)を作る
    • ここで最適形を検討。最適形が「ななめ市松模様」だと思ったけど、長方形なので、その接合部分がルール列挙しないといけなそうで面倒。
xxxoxx
xxoxox
xoxoxo
oxoxox
xoxoxx
xxoxxx


xox
oxo
xox
  • 箱を4つ使って中に領域を作る、というのを大量に用意して、その4箱同士を接するように配置するようにしてみる
    • 4箱を適当に重ねてつぶして領域がたくさんできることを狙ってみる(できた領域が面積最大は期待しない)
  • 横幅と縦幅をどの程度にするかで結果が少し変わるので、それを9秒間でできるだけ探してスコア最大のものを返す
    • スコアの計算がビジュアライザのをそのまま持ってきたから重い。というかスコア低すぎて絶望。


最終的に2万2千点程度/100万点(1位の人の2.2%ぐらい)で終了。

反省

  • 方針ミス・最適形の見積もり失敗
    • 「最適形が市松模様」であると信じて疑わなかったので、どれだけそういう形にできるか勝負と勘違い
      • 終わってからの上位の人の解を見て衝撃だった・・・
    • 原因は、大きさが1の正方形の箱(12個程度)で考えていたので、多いときでもそうだろうと思った
oooo
oxxo
oxxo
oooo


xxxoxx
xxoxox
xoxoxo
oxoxox
xoxoxx
xxoxxx
    • よくよく考えてみれば、
    • 箱がたくさんあるときに、N個の領域＆合計面積Aがあって、領域をm個程度削って代わりに面積Bを増やしたとすると、N-m個の領域＆合計面積A+Bで、スコア的には、N^2*Aと(N-m)^2*(A+B)なので、
    • (N^2*A-2AmN+m^2*A+(N-m)^2*B)-N^2*A = (m^2*A-2AmN +(N-m)^2*B)が0より大きくなる場合はスコアは大きくなる
      • (丁寧にまとめると、-2Am(N-m)+(N-m)^2*B = (N-m) * { (N-m)*B-2Am })
      • N=500, m=100, A=10000, B=10000とかだったら、400 * { 400*10000 - 2 * 10000 * 100 } > 0で普通にあり得る
    • 先入観でそれ以上考察しなかったのがよくない
  • スコアが低いときの対処
    • 最適形については、やってみた結果が著しくスコア低い場合に明らかに何かおかしいと気づくべきだった
  • 細かいテクニックの確認
    • 箱の形状による分類とか、領域をたくさん作るための方法とか、サブタスクに落としたときに他の方法を試す場合に使えるものをまとめておくとよさそう
    • 最終的にそういうサブタスクをいかに最適にできるか重要っぽい
    • あとユニットテストは重要。いくつか単体で試してちゃんと動くか確認(動いてるっぽく見えても間違ってるかも)