目次
はじめに
今回はAHC028に出ます！AHC028は短期(240分)なのでブログをちゃんと書く時間があるかわからないですが、参加記を継続したいので頑張ります
問題文
問題文はこちら
First Submit
問題文を読んだ。"abcde"と"cdefg"のように、重複する部分文字列が存在する場合には"abcdefg"と節約することができそうだ。文脈ありの一人ゲームなので、ビームサーチかなぁ。とりあえず貪欲法を書きたいけど、貪欲法も設定結構難しそう
そういった難しいアルゴリズムを実装する前に、とりあえず正の得点を得たい。今いる位置から一番近い文字を頭文字とする文字列をランダムに持ってきて、その文字列通りになるように、一番近い文字を訪れる。を繰り返そう。
とりあえず全部の縁起の良い文字列が含まれる文字列の作成に成功した。
サンプルを試してみるとほとんどが1001で悲しい。サンプルで気付いたが、今回のAHCはその問題の性質上、他のシードの答えを提出しても点数が得られる。エラーで0点にならないのはありがたいかと思いきやミスをしてるかどうかがわかりにくいという罠。
First Submit。ほぼ全部最低点数っぽくて悲しい。僕はヒューリスティック水色なんだぞ😭
貪欲をうまく作りたい。
とりえあず、"abcde"と"efghi"に対して"abcdeefghi"ではなく"abcdefghi"としたい。これは最終的な文字列を記録していればできる。5分間隔で出せるのでとりあえず提出。
スコアが倍近くになったのにみんなが強すぎて順位が大幅に下がる。僕はヒュ(ry)
次に、頭文字が同じ文字列&まだ未到達の文字列を全て試してみて、一番コストが低いものを採用する。どんどん貪欲法を完成させていきたい。
なぜかスコアが。下がった。
と思ったが、xとyを逆で距離計算してたことが判明、直すとだいぶスコアが上がった。
今いる地点の文字を頭文字とする文字列がすべて探索済みの場合、まだ探索していない文字列の頭文字の内、一番近い文字に移動する。今まではランダムな文字列の頭文字に飛んでいたため非効率的だった。かなり貪欲法が仕上がってきた気がする。
これを提出すると、1,000,000点を超えることに成功。
1文字だけではなく、複数文字の重複にも対応。"abcde"と"bcdef"を"abcdef"とできるように。提出してみる。
ここからコンテスト後に書いています。短期コンテストで参加記書くの難しい；；
その後、1文字の最短ではなく2文字の最短を時間いっぱい見るを提出するも点数は変わらず。どうやって改善すればいいのかわからずそのままコンテスト終了。
終わりに
短期コンは上振れを引きやすい印象があるのだが、上位層はいつもの顔ぶれが多くてすごいなと思う。
AHCの目標を200位(トヨタコンの決勝に出てみたい)としているので、400位はちょっと悲しい。今回900人近く正の得点を得ていてALGO ARTISさんのネームバリューってすごいのかなと思うなどした。
レートはまだ上がりそうだが、そろそろ頭打ちになりそうな気もしている。始めた時から水パフォはコンスタントに取れているが、そろそろ青パフォ以上を取りたい。成長したい。
今回の問題は「文字列単位で貪欲法を行う」という発想にたどり着けなかった。どういうプロセスでその発想が生まれるのかわからない。「各文字列に対して、始点と終点がわかればDPで最適が求まると気づく」→「なら文字列の中身は一意に定まるし、文字列を塊として組み合わせを考えるべきだ」って感じなのだろうか。だとしたら今取り組むべきはAlgorithmなのかも？
今回のコンテストも面白い問題設定で楽しかった。Twitterを見ていると、ALGO ARTISさんの会社に競プロ(特にヒューリスティック)強い人が多くて、ALGO ARTISで働いてみたいなと思う。コンテスト開催ありがとうございました！
