ALGO ARTIS プログラミングコンテスト2023 冬（AtCoder Heuristic Contest 028）参加記
目次
はじめに
今回は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で働いてみたいなと思う。コンテスト開催ありがとうございました！
RECRUIT 日本橋ハーフマラソン 2024冬（AtCoder Heuristic Contest 029）参加記
目次
はじめに
競プロerのみなさんがAHC参加記を書いていて、いいな～と思ったので書いてみました！
とりあえずリアルタイムで書いていこうと思います(12/22)
ちなみに、今回レート+5すれば人生初の水色です！水色になりたい！
問題文
問題文はこちら
1日目(12/22)
2時頃に問題文を見てとりあえずサンプルコードを提出
問題を見る感じ、thunderさんのブログのモンテカルロ法が使えそう？
1手出した後にやり直しがきかないので、焼きなましとかビームサーチは難しいように感じる。なんとなくルールベースに解くだけでも高いパフォが出そう
サンプルコードを読んで改良する方針を試すが、知識浅い&他人のコードを読むのが苦手、で断念。カードやプロジェクトのクラスを作るという発想は頂きつつ自分で1から書くことに。
まずは簡単なルールベースを書いてみる。戦法としては
- 出すカードは一番労働力が高いカードを出す(全力労働カードは労働力*プロジェクト数で労働力を再定義)
- 対象プロジェクトは、もしその労働力で完了するプロジェクトがあるならその中で一番残務量が多いプロジェクト、完了するプロジェクトが存在しないなら一番価値が高いプロジェクトを進める
- 拾うカードは、w/(double)pが最も高いカードを選ぶ。なお、0枚目のカードについては、p=1とし、w/p = 1のカード最大かつ複数ある場合には0枚目を優先的に選ぶようにする
これを実装してみる。upper_boundの返り値がよくわかってなかったり、所持カード(以降"デッキ"とする)の更新に手間取って1WAを生やしたりしたが何とか完成。
提出してみると、絶対スコアで246649を取得。
現状思いついている改善点は
- 対象プロジェクトは、完了するプロジェクトの中で一番価値が高いほうがよさそう？(ビジュアライザを見る感じ)
- カードをゲットする段階で次のカードを提出するところまで進めるはずなので、その段階でのmoneyを先読みして一番いいやつを選ぶべき？(真の貪欲法)
- モンテカルロ法の実装
寝る直前に「完了するプロジェクトで一番価値が高いものを選ぶ」を実装。しかしseed1~10でスコアが下がったため却下。
健康生活をしているため、1時に寝ようとしたものの、「もう少しだけ実装しよう」が重なり、スコアの実装を完了してしまう。(午前1:53)
2日目
「対象プロジェクトを常に一番価値が高いものにする」を実装。しかし明らかにscoreが小さいため断念。seed4では最高値が出たが、今回は「いくつか戦法を試して一番いいのを採用」ができないため却下。
1日目の箇条書きの2つ目(真の貪欲法？)を実装。しかし明らかにスコアが低い(seed0=18)。
ビジュアライザを見ていると明らかに損をするムーブ(1つのタスクを終わらせるまでにそのタスクで得られる報酬以上のpayをしている)感がある。しかし何が原因でそうなっているのかはわからず。
ビジュアライザを眺めていると、残務量が高いやつに労働力を割くのは、価値が高くても時間がかかって損になる(特に序盤)場合があることに気づく。そこで完了するプロジェクトがない場合に一番残務量が少ないプロジェクトを選ぶ戦法に変更。テストすると前のやつとどっこいどっこいだったので提出してみることに。
スコアが下がってしまった。
一気にやることが無くなってしまった。とりあえず出来そうなことを整理。
- 各プロジェクトの残務量と価値から価値の密度を出してそれを選定基準にする？
- ↑の密度が一定以下なら爆弾で消す？
- 増資カード使いたい
- モンテカルロ法を試す？(貪欲がうまくかけてないのに書けるのか？)
増資カードの仕様がよくわかっていないが、サンプルコードを見る感じは各テストケース内で20回以上使えないという認識であってそう(質問したら合ってました。AtCoderさんありがとうございます！)
とりえあず、初期手札に増資カードがある場合には優先的にそれを使う戦法を実装&提出。絶対スコアは277320に伸びた。
各プロジェクトについて、残務量/価値をして密度を求める(低いほどいい)。完了するプロジェクトがない場合にこれを選定基準にするもそこまでスコアが上がらなさそうな気配をテストから感じる。
方針転換
ここで方針を、「貪欲法の設計」から「モンテカルロ法の設計」にチェンジ。ルールベースではないモンテカルロ法でどこまで行けるのか確かめる。
と思ったが使うカードとその対象先、拾うカードを全てモンテカルロ法で探索するのは実装が重すぎ&複雑すぎて断念。(実装力不足を痛感する、この実装はコンテスト後にやろうかな)
プロジェクト削除系カードの処理を加える。プロジェクトの密度が1.0以上は効率が悪いと判定する。最後のターンには必ず労働系のカードを出すようにする。
これをテストしてみると全てのseedに対してスコアが上がった。期待を膨らませながら提出するも2WA。順位は上がってるらしい。
また、カードの入手を、効率が悪い仕事の数に応じて変えればよさそうである。
電流走る
テストケースを見ていて気付いたのだが、この問題で重要なのは増資カードをどれだけ使えるかである。増資カードが最初から手元にある場合(増資1回)とそうでない場合(増資0回)はスコアが約2倍違う。残務量も2倍になるのでどこかで頭うちになるとは思うが、3,4回なら使うたびにスコアが伸びるように感じた。
そこで、序盤は増資カードをゲットするのに全力を注ぎ、どこかで現在の方針に乗り換えることを思いついた。
3日目
とりあえず、現在の方針を強化する。具体的には、
- カードを拾うときに"効率の悪い"プロジェクトの数に応じてキャンセル系のカードを取得するようにする。そのカードが複数ある場合にはその中で最安値のものを拾う。
- 増資カードが拾えるかつ今までに使った増資カードが4枚以下なら、増資カードを拾う。
これをテストケースで試したところ、テストケースの値が4倍ほど高くなってニッコリ。提出する。
h3タグ付けるととても見やすい
ビジュアライザを見ていると、増資カードの力が膨大であることがわかっため、増資カードの採用を増資カードを20回使っていない&ターン数が500未満に変更
REの原因をつぶすため、イテレータを参照している箇所は全てempty()で場合分けする。テストでスコアも上がったので提出。
WAが取れない。テストケース100個試したがWAは出ず。カード取得について書き換えたらWAになったので取得でミスしてそう。
色々バグってました。取得時にデッキ内のタイプ別の配列にちゃんとインサートできてなかったり、使った時にそこからちゃんとeraseできてなかったり。直したので提出。
4日目
なんと4日目は進捗ゼロ。他の用事が立て込んでいてAHCどころではなかった；；
5日目(最終日)
デッキが同じ系統のカードで埋まると行動宣言されるよなぁと思い、キャンセル系のカードに枚数制限を掛ける。テストするもあまりスコアが変わらず。
睡魔
19時まで寝てしまっていた。昨日今日と放置していたことにより順位は150位ほど落ちてしまっている。後2時間でどこまで取り戻せるか。
時間いっぱい探索できてないのはもったいないと思いつつ、時間いっぱい何を探索するのかが思いつかない。モンテカルロ法ははランダムの実装が難しくて実装できない。
ビジュアライザを見ていると、残務量に対して過剰に労働力を払っている場合があることに気づく。このターンで完了するプロジェクトに対して、残務量の2倍以上の労働力を掛けている場合は、完了しないプロジェクトの中で残務量が最小のものを選ぶ。
全てのテストケースで良くなるわけではないが、よくなる場合の更新量がすごいため良さそう。提出。
その後、investカードを使った後にinvest前のカードを優先的に使うようにしたり、残務量が10以下のカードを排除しないようにして見たりしたが更新するのか微妙なので見送り。final submitは↑の提出になりそう。(なりました)
終わりに
システス前260位でした。勝手にヒューリスティックコンテストの1つの目標を200位にしている(賞品の対象になったり、決勝に行けたりと嬉しいことが多い気がする)ので、なかなか到達できなくて悔しい
今回のコンテストで(恐らく)水色になりました。嬉しい。
今回のコンテストは、自分が見てきたヒューリスティックの問題の中でもかなりゲームに寄っていたと思う。ゲーム(特に対戦ゲーム)が好きなのでおもしろかった。
次回のコンテストまでにテスト環境は仕上げたいなと思った。自動で100テストやってくれるツールもあるっぽいし、それを導入しておきたい。
前回のコンテスト(AHC028)もそうだったが、「もしプログラムではなく手動でこの問題を解くときに、どれくらいのスコアが出せるか(自分の中での理論値)」がかなり低いように感じた。理想形がわかってないといいスコアは取れないと思っているので、個人的な課題は「この問題の理想的な解」を高くすることだと思っている。アルゴリズム等と違ってテンプレートがあるわけではない気がするので、どうやって伸ばすんだろうというのは気になる点である。
最終結果(システス後に更新します)
最終264位でした。４つ落ちてた；；
でも水色にはなれました！良かった！次は200位以内に入りたい！
