2024年9月18日水曜日

RECRUIT 日本橋ハーフマラソン 2024夏（AtCoder Heuristic Contest 036）

　pretest71位→システムテストリジャッジ前100位→リジャッジ後72位でした。

　リジャッジありがとうございます！
　システムテスト結果が出たとき、ジャッジおかしいんじゃないの？　というようなことをツイートしたけど、それほど確信はなかった。リジャッジでTLEが減り、順位が上がって良かった。

　最終日まで300位前後で、最終日にAの別の作り方を試し、順位が大きく上がったのも嬉しかった。

　大体ツイートのまとめです。

コンテスト後のツイート

前半四日くらい

　Aを固定したとき、「Bの変更は全体取り換えのみ」とすれば最適解を求められそう……と思って書くが、色々バグらせた上PyPyじゃ間に合わない（あとでRUSTで書き換え、枝狩りをして一応間に合う。でもシステムテストだとTLEするかも→した）

最終日まで

　Aとしては適当な評価値で山登り/焼きなましを考えていたが、それだと300位前後にしかならない。最終日に方針転換を迫られる。

最終日

　t[i]からt[i+1]への最短距離での行き方を最初に調べ、それらを連続部分列として多くもつようにしたい。

　まず、各点から各点までのBFSを使って、t[i]からt[i+1]まで進む頂点を列挙。この集合をNEEDとする
　そのうち、長さが短いもの同士で、一番最初の文字＝一番最後の文字とかなったりするものを組み合わせていく。評価値は、「できあがったものの長さ/組み合わせた個数」のようにする。
　評価値の小さい順にAにおいていく。ただし、Aの長さ+Aに出てきていないNEEDの個数<=LAとなるギリギリまでおき、その後はNEEDに入っているものをおいていく。
　NEEDに入っているものxをおくときは、今までのAの中で、xのそばにxと隣接するものができるだけ多いような場所に置いた。

　これが最終提出でした。

気になっていたこと

　ところで、「自分のコードは、Aを与えられたら、Bを全取り換えするものだけ使うなら最善のものを出力しているつもりだったけど本当か？」が気になっていたので調べてみた。

　上位の方のコードで出力しているAを入力し、そのときのスコア（そのコードでのスコア vs 自分のスコア）を比較すると、

・B全取り換えだけでやっている人には大体ちょっと勝ち（or引き分け）
・部分取り換えも使っている人には結構負け

　という感じだった。

というわけで、自分のコードは、B全取り換えだけ使うなら多分最善だったけれど、

・厳密な最善を求める必要はない。多少スコアを犠牲にしても、計算量改善した方がメリットは大きい
・部分取り換えの使い道は少ないと思っていたけど、自分が思ったいたより大きく改善するらしい。

と分かった。

　Aを決める部分の方がスコアに影響する度合いとしては大きいけど、そっちは発想力が求められた印象。今回はたとえば、「中心を決めて木構造にする」というAの取り方が強かったようだけど、コンテスト中に思いつけたか？　と考えると結構厳しく感じる。それに対して、「Aを求めた後何を出力するか？」の部分は発想よりアルゴの力が求められた気がする。

　その部分で、（Bを全取り換えする場合の）最適解を求められていた（と思われる）という意味では、やるべきことはやっていたといえるけれど、もっと計算量を削減しなければヒューリスティックな手法は使えない。もっと考えなくてはいけなかったなぁ。
時刻:
ラベル:

0 件のコメント:

コメントを投稿

登録: コメントの投稿 (Atom)