2023/1/28〜2023/2/5に開催されたTHIRD プログラミングコンテスト 2022(AtCoder Heuristic Contest 017)に参加しました。
アルゴリズムのレーティングは、ほぼ１年にわたって停滞ムードが続いておりますが、ヒューリスティックのレーティングは一応上昇中。
今回の結果によっては、一気に入水を決められるかもしれないという状況なので、しっかりと腰を据えて頑張ろうかという感じで挑みました。
参加します。Heuristicのほうも入水に近づけるように頑張ります。
— devgenjin77 (@devgenjin77) 2023年1月28日
THIRD プログラミングコンテスト 2022 （AtCoder Heuristic Contest 017） - AtCoder https://t.co/JiOJEX4Ni1
今回の結果
確定464位。。前回よりは大きく順位を落としているので、ちょっぴり残念な感じです。
パフォーマンスは、なんとか水色を達成というところ。レートも上昇したので、この分だと、次か、その次にはなんとか入水できそうな感じです。
もうちょいで入水😃
— devgenjin77 (@devgenjin77) 2023年2月7日
devgenjin77さんのTHIRD プログラミングコンテスト 2022 （AtCoder Heuristic Contest 017）での成績：464位
パフォーマンス：1228相当
レーティング：1103→1148 (+45) :)#AtCoder #THIRDプログラミングコンテスト2022（AtCoderHeuristicContest017） https://t.co/9PnG9GMMPD
振り返り
今回も提出は遅め。上手い方針を立てることはできませんでした。
A問題
これって本当に焼きなましとか、山登りとかで取り組むような問題なのかな、というのが問題を一読した時の印象。
全点間の最短距離は、ワーシャル–フロイド法を用いて計算することはできるかと。。しかし、これを何回も繰り返し計算して山登り法をすることは不可能という感じ。
じゃあ、工事した差分だけ高速に求める方法があるのかと思ったが、これはてんで全く思いつかず。
ということで、スコア計算を諦めて、他の方法でなんとかならないかと考えてみることに。
とはいえ、工事する道路の場所は、日毎にある程度ばらけさせた方が良いのか、それとも日毎に一定のエリア内で集中させた方が良いのかもよく分からず。。。
そんなこんなで色々検討した挙句、平日は終わってしまい、気付いてみれば、もうコンテスト終了１日前の土曜を迎えましたという状況でした（笑）
ここま出来たらもう開き直るしかない。とりあえず、なんか提出しないかんという感じで、即興で解法を考えてみました。
解法１：適当に引いた経路の道をまとめて工事する
下手に細かく道を区切って選ぶよりは、ある程度経路を決めてみて、まとめて工事するのがいいんじゃねという感じの発想。根拠はない。
実装としては、適当な頂点を選んでDFS的な探索を行いある程度の長さの経路を作成。これを同日に工事するという感じ。
こうすると、どうしても余りの道ができてしまうので、余りの道を工事するための日を別途作り、選ばれなかった分を適当に割り振ってみました。
で、いざ初提出してみると、
とまあ、下から数えた方が早いという最悪解法の模様。これじゃいかんということで、方針をイチから見直してみました。
解法２：とりあえず連結を維持する
先ほどの解法で出した結果をビジュアライザに入れてみると、どうもグラフが連結でなくなると大分スコアが落ちるという感じ。
ということで、とりあえずグラフの連結は維持するという実装を書いてみる。
日毎にグラフの次数を管理しておき、各辺毎に、辺の両端の頂点の次数が２以上である場合だけ工事日として設定し、両端の次数をデクリメントするようにする。
このロジックでどうしても選択できない辺などあるかという不安はありましたが、とりあえず提出。
こんな単純な実装で、なんとか人並の数字を取ることができましたとさ。
解法３：道の両端の次数をなるべく多く残す
「同じ頂点につながっている道同士は、同じ日に工事しない方がいいのでは？」という仮説を思いついたので、実装してみる。
やり方としては、解法２で両端の次数を見る際、両端の次数の和が最も残っている日を工事日とする方法。
これで提出してみたら、気持ち少しほどスコアが改善されました。
この後は、有効そうなアイデアも思い浮かばすで、終了です。
最終提出コード
https://atcoder.jp/contests/ahc017/submissions/38655792
これまでの実績
一応、レートは上がりましたが、そろそろ頭打ちかなあという感じもします。
総括
他の方の解法解説などを見ると、今回は評価用スコアの計算に工夫が必要だったかというところでしたね。結局、ある程度の試行回数が稼げないといい結果は出ないようです。
あと、今回に限ったことではないですが、やはり焼きなましがちゃんと使えないと今後のAHCではキツいかという感じもします。とりあえず次回のAHCまでには焼きなましの実装について勉強しておこうと思います。
ということで、また次回も頑張ります。
