みなさん、AHC017お疲れさまでした!
いつもはTwitterでAHCに参加した感想などを投稿しているのですが、今回初めてブログという形で書いてみました。
理由は「今回は書きたいことが多すぎてTwitterでは文字数が足りないから」です。それだけです。
いつもの私のつぶやきの延長なので気楽に読んでいただけたらと思います。
◯今回やったこと、というかうまくいかなかったこと
不満度の計算方法を「ダイクストラ法で全ての頂点間の最短経路を出す」 しか思いつかない
→もちろん時間不足
→代わりの評価方法を複数考えるも、ことごとく得点と相関せず
→そんな状態のまま見切り発車で山登り
→そのまま終了
という有様でした。システムテストを震えて待ちます。
◯不満度計算の代わりの評価方法
効果がなかった評価方法たちですが、いつか役に立つかもしれないので書いておきます。
・各々の道について「工事を全くしていない状態」で、反対側の端まで「その道路を使わずに」最短経路で行く場合の時間増加分と、各頂点間の最短経路でその道が使われる回数を数えておき、その道の工事をする場合は上記ふたつの積を評価マイナスとする
→複数の道を同時に工事していたら別の経路が最短になる可能性がある
・上記の「道が使われる回数」を使って利便性が高いと思われる道を判断し、それらを「同日に多数工事する」もしくは「なるべく別の日に分ける」
・工事する道を「なるべく近くに集める」「なるべくばらけさせる」
等々でした。
この辺りは人生50年の経験で、「高速道路集中工事」の例や、「近所の道路工事が〇〇だった時は不便だったな」などと思い出しながらアイデアを出しましたが、効果は薄かったです。
ただ、浮かんでくるアイデアを実装することは楽しかったし、書いたことで勉強になり今後に繋げられたと思います。
◯今回の収穫
上記の他にも、収穫はたくさんありました。
①優先度付きキューを使うダイクストラ法を覚えたこと
②DFSを使う連結成分のカウント方法を覚えたこと
③データの散らばりを使ったこと
心理統計学で覚えたばかりで、使ってみたくて使いました。効果があったのかは疑問です。
④焼きなましを使ったこと
こちらも使ってみたくて使いました。ただ評価の仕方が正しくないため効果が出るはずもなく、提出時はお蔵入りにしました。書き方の練習にはなりました。と思いたいです。
⑤手元で連続100ケース回して分析したこと
コンテスト前にシェルスクリプトを使う方法を勉強して、連続実行と分析のプログラムのひな型を書いておきました。(分析といってもスコア平均を取る程度です)
こちらも評価の仕方があれだったため、ほとんど役に立ちませんでした。次回は、できればRustのローカルテスタも入れてバージョンアップし、分析の役に立てたいと思います。
◯最後に
いつもの長期AHCならば水曜日あたりにはアイデアを書き切っているのですが、今回は効果のあるアイデアが浮かばずに苦しみ、最終日の昼まであがき続けました。自分でもよくこんなに熱中できるなと呆れますが、それ以上に楽しい一週間でした。
AtCoder様、今回も楽しませていただいてありがとうございました。そして皆さん、対戦ありがとうございました。50歳過ぎても人生楽しい。
rinrion
2023.2.5.22:06追記
最終提出の内容を全く書いていないことに後から気づきました。書きます。
1.ダイクストラ+経路復元で「頂点の全組合せの最短経路を通った場合の各道路の使用回数」を調べる
2.市内を100区画に分け、番号が小さい方の頂点を基準に道路を各区画に分ける
3.各区画の道路を使用回数が多い順に各工事日に割り振り初期解とする
4.ランダムに道路と日にちを選び、2割の確率で工事日を移動・残り8割を交換する
5.連結成分が2以上なら次のターンへ
6.山登り
評価の内容:「よく使われる道路の工事日を分けているか」「工事中の道路が多すぎる区画がないか」
順位は暫定524位でした。システムテストでどこまで上がるか下がるか。
2023.2.7 8:10 追記
システムテストの結果が出ました。
レート+7は諦めなかった自分へのご褒美だと思います。
お読みいただいてありがとうございました!