AHC003 参加記

記事をお読みいただきありがとうございます。

AtCoder Heuristic Contest 003 に参加して、88,128,103,230点(システス前)で423位でした。

2021/05/31追記
システス後:2,648,223,238,697点, 416位
(88,128,103,230×30=2,643,843,096,900 < 2,648,223,238,697)

期間中ほとんどの時間費やしたにも関わらず、90,000,000,000点を超えられませでした。

おしまい

これだけだと少し悲しいので、供養の意味も込めて、日記っぽくして書いておきます。(期間中一応メモをつけてました、メモ部分はコードで囲ってあります)

5/22

とりあえず、xの差、yの差で愚直解 (xとyどっち先にやるかで差が出る)
コストの平均をメモして、愚直の2択を選ぶ、帰ってきた平均をメモして繰り返す

愚直解を投げるのに、スコアの入力の受け取りを忘れたりしてペナを量産してました。

1万ケーステストケース生成しました。

カスみたいなclarを投げました。ごめんなさい。

5/23

負の辺がなさそうなので、ダイクストラをしてみる
辺は10000テストケースの辺の値の平均にする
最初だけ愚直に2択ランダム
その後はコストをメモして更新しながらダイクストラ
(間に合わなさそうなら部分ダイクストラ？そもそも遠回りするメリットないから、どこで曲がるかの判定だけでいいかも)
->つもりだったが結局部分的なdpをして経路復元をした

(sik,sjk)から(tik,tjk)のDPをしてみました。
https://atcoder.jp/contests/ahc003/submissions/22860551

5/24

平均のメモをcountごとに調整
ダイクストラやったほうがよさそうなことが判明(時間足りなさそうだったら、後ろのほうだけでも)

辺の重み予測とか色々やってました

5/25

ダイクストラをバグらせる

そのままです。提出はなし。

5/26

提出してみるとめっちゃ下がった
原因は明らかな遠回りをしてしまっている
DPに戻した

ダイクストラしたら点数が下がりました。原因は辺の重みの予測を失敗していたらしい。

始点と終点のx座標or y座標が同じとき dpをしていなかったので、±1の範囲でdpしました
関数化してなかったせいで実装が地獄でした。
https://atcoder.jp/contests/ahc003/submissions/22934124

5/26 深夜

点数で追い越せないからレートで追い越した pic.twitter.com/vaQ56fed0m

— harurun🌹 (@harurun_p) 2021年5月26日

AHCのレートで順位表を色付けするスクリプトを作って遊んでました。
あとから見ると、レート高いのに負けてて悲しくなっています。
スクリプトURL:
greasyfork.org

翌日寝坊しました。反省しています。

5/27

パラメータいじったけどあまり変わらなかった
他のDPの場所も1マス広げてみたい

辺の重みと増分を色々といじりました。

5/28

ローカルジャッジが3日目からバグっていたことが判明
どうりで点数がかわらないわけで...

ローカルジャッジのために以下のスクリプト(Python)を使ってました。

import sys
import os
M=0
N=10000
if len(sys.argv)>3:
  raise Exception
elif len(sys.argv)==3:
  N=int(sys.argv[-1])
  M=int(sys.argv[-2])
  if M>=N:
    raise Exception
elif len(sys.argv)==2:
  N=int(sys.argv[-1])
with open("result.txt",mode="w")as f:
  pass
for i in range(M,N):
  t=str(i).rjust(4,"0")
  input_file=f"in/{t}.txt"
  os.system(f"cargo run --release --bin tester {input_file} solve/main9.exe >> result.txt")

f=open("result.txt")
L=f.read().split()
f.close()
s=0
for i in L:
  s+=int(i)
print(s/(N-M))

バグっていたというか変え忘れなんですが、main9.exeの部分が3日目あたりのmain3.exeになってました。
(Rustのコードを少し変えて、スコアだけを出力するようにしてました)

5/29

dpの小手先改善
tabnineの自動入力に頼った結果、添え字バグ

(sik,sjk)から(tik,tjk)のdpの範囲を上下左右に1つづつ広げました。
思った以上に実装が地獄で、大変でした。

こんな感じ。すべて場合分けしました。

tabnineで自動入力しまくってましたが、たまに変になってバグりました。
あったほうが100倍いいのでtabnineはおすすめです。

パラメータガチャのためにたくさん回し続けてたら、tester.exeが削除されてしまいました。(まぁコンパイルし直せばいいだけでしたが)

結局、辺の重さを3500、増分を0にしました。

最終的な提出コード
atcoder.jp

感想とまとめ

コンテストが終ってから、最初だけdpして、後半ダイクストラすればよかったなと思いました。次の短期コンテストは頑張ります。
長くなりましたが、最後まで読んでくださった方、そうでなかった方もありがとうございました。