Introduction to Heuristics Contest 参加記

昨日 AtCoder で行われた Introduction to Heuristics Contest のコンテスト中に自分が考えたこと,やったことを書きます。A問題の提出者が1795人中65位だったので水色コーダにしては健闘したほうかなとか思ってます(水色でももっと高い順位の人はいっぱいいますが)。

問題概要

問題文はこれを見てください。D日(D=365)分のコンテスト日程を決める問題でそれぞれの日に26種類のコンテストのどれかを割り当てます。コンテストを開催すると満足度が増加し,コンテストの種類,開催日によって満足度の増加量が変わります。また,特定の種類のコンテストが開催されないと満足度が下がっていきます。D日後の満足度を最大化する問題です。

正の得点をとるまで

マラソンマッチの醍醐味?であるところの多くの参加者が同じ点で横並びになるパートです。まあ,ランダムにコンテストを出力しとけばいいでしょと1〜26をランダムに出力するコードを提出します。卍0点卍。

おかしいなーと思いながら満足度を最大化する問題なので満足度の増加量が1番高いコンテストを出力してみます。卍0点卍。

ジャッジ壊れてる?とか思ってました。しかし,他の参加者は13639点をかなりの人数がとっています。かなり焦りつつ,冷静に少し考えてみます(矛盾してない?)。コンテストの開催間隔が長くなれば長くなるほど損なことがわかります。全てのコンテストの開催間隔ができるだけ短くなるように1〜26をぐるぐる回す解法にします(i日目のコンテストがi%26+1)。無事13639点ゲット。

山登り法

13639点解をより良くすることを考えます。マラソンでは解を少し変えてスコアが良くなったら解を更新するという手法が初心者向け記事とかで紹介されてます(C問題もそういう感じですね)。この解を少し変える方法ですが,ぱっと思いついたのは1点変更(i日目のコンテストの種類を変更)と2点スワップ(i日目とj日目のコンテストを交換)です。13639点解は同じコンテストの開催間隔が26日になっています。ここで1点更新をすると更新間隔が52日になってスコアが上がりづらくない?と考え2点スワップを実装して制限時間いっぱいスワップしてスコアが上がれば解を更新,下がればそのままを繰り返します。いわゆる山登り法ですね。79141700点!桁が3つ増え,びびります。

初期解を改善できないか考え貪欲法(B問題の次のステップに書いてあるやつ)で初期解を作ってみます。89124679点。

ビームサーチに

さあ,ここからどうするか。一般的には山登り法の上位互換であるところの焼きなまし法を試したり,試行回数が増えるようにscore計算の計算量を落とす,軽い嘘評価関数を作るとかがあります(僕調べ)。ただ焼きなまし法はわかりませんし,計算量の落とし方も思いつきませんでした。また,上位の得点との差が大きかったので根本的な方針が違うのかなと思い始めます。そこでこの日のために勉強しておいたビームサーチをやってみます(全ての問題が覚えたてのアルゴリズム使う問題に見えるあれです)。

ビーム幅100のビームサーチをバグらせながらもなんとか書き上げサブミット。114127223点。 上位陣もビームサーチ使ってたんだなー,ふむふむとか思ってました。全然違うんですが。 結構順位がよくなってテンション上がりました(何位だったかは忘れた)。

時間が200msほど余っていたので残り時間いっぱい山登り法でがんばります。116536986点。 コンテスト時間が30分を切っていて最後にできることを考えます。評価関数変えてscore上がればお手軽だなーと考え,いじってみます。ビームサーチの弱いところは先読みが入ってないとこかなーと考え,翌日の満足度の減少も考慮した形にしてファイナルサブミット117723646点。

コンテスト後

焼きなましで高得点とっている人が多かったみたいです。あと,1点更新を切り捨てるのは良くなくてうまく2点スワップと混ぜるといいらしい。 とりあえず楽しかったので今後もマラソンやっていきたいですね。

想定解

<@nuxt/content で数式を表示する  |