Kyo_s_s Homepage
AHC027 参加記
競技プログラミング
AHC

153位、パフォーマンスは1828でした。レート1968 -> 1975(+7)しました。

問題: https://atcoder.jp/contests/ahc027/tasks/ahc027_a

GitHub: https://github.com/Kyo-s-s/AHC027

時系列でどんなことをしたのかを書きます。

1日目(金)

問題を読んで環境を整えたりしました。

今までmain.rsに全てを書いていたのですがさすがにつらくなったので、今回から複数ファイルに分けて書くことにしました。 とはいえ、Rustのモジュールシステムは分かっていないので、とりあえずsrc直下にファイルを置いて読み込むことにしました。

提出するときには1つのファイルにまとめる必要があるのですが、今回はとても雑にPythonでコードを展開するスクリプトを書いてしまいました。 main.rsで、

main.rs
// --- bandle on ---
// path: hoge.rs
mod hoge;
use hoge::*;
// --- bandle off ---

と書くと、hoge.rsの中身をそのまま展開して貼り付けるようにしました(bandle on内で // path: ではじまる行はそれを展開し、それ以外は無視する具合です)。

本当はこんなことをせず、cargo-equipなどを使えればよかったのですが、今回は時間がなかったのでこのような方法になってしまいました。普通にバグりそうです。 また、Pythonで雑に展開部分をDFSしたのですが、よくわからないエラーが出てキレてしまいました。よくわからない記法をしたら直り、気分が悪いです。Python、あまり好きではないです。

Pythonによるサンプルコードが公開されていたので、とりあえずそれをRustに移植します。複数ファイルに分けて書けるようになったので、だいぶ書きやすいです。提出し、スタートラインに立ちました。

また、得点計算を実装します。 たぶん O(L)O(L) とかで得点計算できてる気がします。

2日目(土)

第2回緑以下コンでした。運営としての参加で、来場者のチェックなどをしたりしていました。 Writer記はこちら。

3日目(日)

AHCやるぞ！と思っていたのですが目が覚めたら13時でした。 しかもジョイポリスに遊びに行くことになり殆ど手つかずでした。

ジョイポリスではなんかすごいのに乗りました。これに乗ることで何かひらめくかなと思ったのですが何も思い浮かばず。 そんなに甘くありません。

4日目(月)

焼きたいです。とりあえず山登りを書きます。 遷移ですが、雑な初期解に対して、

とします。

サンプルのDFS解を初期解とすると、

// DFSのみ
total: 837268911
max: (59495516, '0042')
ave: 16745378.22
min: (907197, '0037')
// Add操作のみ山登り
50/50
total: 669651195
max: (54132432, '0019')
ave: 13393023.9
min: (796813, '0037')
// Add, Del操作で山登り
total: 619593739
max: (52160677, '0019')
ave: 12391874.78
min: (703914, '0037')

初期解より良くなっています(それはそう)

いま、Addでの適当にうねうねやDelの削除がだいぶ適当に書いてあるため、意味のないAddやDelで訪れないマスが出てしまうことがあったりします。 このあたりを改善するとよくなりそうです。

Add/Delの遷移を盛大にバグらせていました　笑

// バグ修正版
50/50
total: 516005490
max: (40791748, '0019')
ave: 10320109.8
min: (691713, '0037')

どんだけバグらせてるんだよ！

修正したら90位まで上がってびっくりです。Addのうねうねを超雑に書いているのですが…。

5日目(火)

validな解は(長さ制限に引っかからなければ)繰り返してもvalidです。 これにより、

を近傍にして色々するのが実装が楽そうです (決して新たなルートをいい感じに追加するのが面倒になったとかではありません)。

実際提出したら少し改善したのと、この2つの近傍のみを考えると高速化が効きそうで良さげかもしれません。

6日目(水)

現状の解を見ると、ddが低いのにもかかわらず複数回訪れているマスがいくつかありました。 部分削除は隣接するマスを繋げる操作しかしていないため、初期解によってはこのようなマスが出てきてしまいます。 とりあえずランダムなパスを消して最短距離でつなぎなおす近傍を追加してみます。 また、焼きなましをするようにしました。

ちょっと改善したのですが、あまりです。うーむ。

また、TLを伸ばして手元実行してみたのですが、スコアはほぼ変わらずでした。高速化よりも近傍や初期値を工夫する方が良さそうです。

7日目(木)

ビジュアライザを見ると、近くまで行ってるのに訪れていないマスがあったりしていてもったいなさがあります。 Addクエリを近傍3つ程度のみまで出張するようにするとよいかもの気持ちになったので実装しましたが、あんまりスコアが伸びません。

8日目(金)

インターンをしたりしていたら一日が終わっていました。うーむ。

9日目(土)/10日目(日)

大阪に行っていました。何も実装できませんでした…。

たこやき！ pic.twitter.com/1Dq3k0al6T

— きょ 参加証大学に提出する (@Kyo_s_s) December 10, 2023

たこ焼きおいしかったです。

© 2025 Kyo_s_s