Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

京セラプログラミングコンテスト(AtCoder Heuristic Contest 006)

HTTF 2022 qualに引き続き、思考過程をまとめていたScrapboxからのコピペ

過程

  • 初手
    • 1-50を順番に
      • みんな大好き181,296点
  • 二手目
    • 403,888点
    • 以下の条件(数値を足し合わせただけ)
      • (400, 400) に近い位置
      • sourceとdistが近い
  • 三手目
    • 470,312点
    • 上記で得た配達先を時間いっぱいランダムに回して一番いいやつ
      • いきなりのランダム頼み・・・
  • 四手目
    • 457,296点
    • 上記で得た配達先で
      • 先に全部ピックアップ
      • 時間いっぱいランダム
    • seed0だと上がったが、やはりだめだったか
  • 五投目
    • 600,243点
    • ピックアップした後、次のピックアップ先に行くまでに配達しやすそうなものは配達する
      • ピックアップ先同士で長方形を作ってその中にあればOK
      • 配達経路はまだ最適化していないので、次でする
        • 無邪気にnext_permutationすると時間が足りないことがある・・・
  • 六投目
    • 601,466点
    • 配達経路をnext_permutationして良さげな順を採用
      • 配達候補が多すぎると時間が足りなくなるので10000回で切る
    • えー、これ微増なのか・・・
    • 最後に残った配達先を最適化するのを忘れていたので、してみた
      • 何故かスコアが下がる・・・
      • 何回か回すと結構ばらつきがあることがわかった・・・
  • 七投目
    • 636,905点
    • 配達先の候補の判定を、長方形の中を止めて、店舗間の距離+50に収まる場所に限定してみた
    • 伸びたけど、思ったほど跳ねないなぁ
    • 最後余った配達先に配達する動きが無駄になりすぎてるっぽい
      • それはそう
      • 余るのは店舗から遠い配達先だからなー
  • 煮詰まった・・・
    • 順位表のスコアの勾配から察するに、根本的に見直さないとだめっぽい
  • 八投目
    • 1,265,077点
    • めっちゃ伸びたw
    • 配達先の候補はそのまま
    • 移動先を、とにかく現在地から一番近い場所にした、だけ
      • まじかよこんなんでスコア倍になるんかよ・・・
  • 九投目
    • 1,265,118点
    • 41点伸びたwww
    • 配達先の候補を求めるロジックをちょっとだけ変えた
      • (400, 400)からの近さだけをみるようにした
  • 十投目
    • 1,423,039点
    • ランダムでまれに最も近くても採用しない場合を作るようにしてみた
      • 結局ランダム頼み
      • 最適化するロジックが思いつかなかったんや・・・
      • しかし、思いのほか伸びた
  • 時間切れでーす
    • 結局、最終提出のコードにろくなロジックが含まれていない件・・・

感想

最終的に、苦し紛れに出したつもりの、適当に原点(400, 400)から近い場所を選択 and とにかく近い順に移動+ランダム要素という雑な処理で出した、ろくなロジックが含まれていないものが自分の中での高得点を叩き出してしまい、最初の3時間はなんやったんや・・・となってます。

2-opt勉強しなきゃなのです・・・。