はじめに
こんばんは。ももはらです。
今回AtCoder Heuristic Contest 019でAHCに初参加してみたので、記録の意味で参加記を書こうと思います。
高度な知識とかをお求めの方はブラウザバックでお願いします。
環境構築
Rustの勉強もついでにしちゃおうかな？と思ってたので最初にRustをインストールしました
インストールはここから：はじめに - Rustプログラミング言語
AHCは問題文と一緒にツールも置いてあってすごい
ローカル版にテストケースも入ってたので実行してみたりしておお！ってするのをやってました
atcoder.jp
ちなみに結局Web版の方がVisualizeされてわかりやすかったので手元はほとんど使ってません！
問題文を読んでみる
長いです。困りました。
どう取りかかっていいか全くわからないです。
(あと最初めちゃくちゃに誤読していて、ブロックで作る図形が2個じゃなくてN個だと思ってました)
とりあえず困ったのでマラソン自体を勉強するべく記事を漁ったところ、terryさんの記事がひっかかりました。
AHC001についての記事で、記事に沿って自分も実装してみることにしました。
AHC001の問題概要：いろんな企業が(xi,yi)を含む位置に大きさriの広告を出したい
なんだかAHC019より簡単そうに見えます（２次元ですし）
さっそくブログに沿って次の流れで実装しました
①1*1の豆粒広告をたくさんおく
②ランダムに大きくしてみる
③ランダムにシフトしてみる
あとは、マラソンだと「秒数制限が来たら処理を切る」みたいなのが必要だったのでライブラリ化したりしました。
焼きなましパートは力尽きたのでやれてません（やらなくば）
とりあえず正の得点を得て、貪欲してみて、話はそれからでいいんだなというふんわりした理解を得ました。
いざAHC019に
問題概要：正面のからみた絵と真横から見た絵が２組渡されるので、それぞれについてブロックを組み合わせて立体を作りたい。ブロックはできるだけ大きくて少ないほど嬉しい。それぞれでブロックを共有してもいい。
1×1×1配る
ランダムな2つをペアにする
ペアにするときに貪欲で大きくする
提出3
今度はペアにするときに大きくしてみようとしました
６方向みて、ペアのどちらも大きくできそうだったら大きくします
52個であまり小さくならないです
強い気持ち出だすとスコア的にはよさそう？ってなります
今も必要なブロックにだけおくようにする
提出6
最初に正面から見ても横から見ても1のところに全て置いていたのですが、もう置かれてる列や行かどうかを管理して、
ペア作りでどちらも置かなくていい場合は無視するようにしたり、最後の穴埋めでも置かないようにしました
17個です
一気に減りました
数ケース回して、一番いいやつをとる
提出7
リファクタでだいぶ綺麗になったので、１手戻しもできそうなみためになったので、
５ケース回して、一番スコアがいいものを採用する実装もしてみました
13個です
いい感じです
でもプレテストの合計得点的には下がります（謎）
回転してあわせてみる
１個のものを減らしたい
Nが大きいケースについて考察できてなかったのでseed=97のケースなどでビジュアライズしてみます
いいかんじに22個までは絞ってくれるんですが、1*1*1のやつがめだったりしています
体積2以上の塊になるときしかペアを作れないようにする
→ヒット率が下がるので、処理が周りきらず逆効果
最後に1同士となりあっていたらくっつける候補にして２ずつのペアにできないかを探索する
→ペアの入れ替えがうまくいかずに実装で敗北
という感じでタイムアップしました
結果
システスで321位から311位になりました。
初参加で水パフォでて最初の問題文を見たときの絶望感を考えると思ったより高くて嬉しいです。
感想
AHC初参加でしたが、提出するたびにスコアや順位が上がったり下がったりするのでハラハラして楽しかったです。
アイデアが出なくなるよりも先に時間の限界がきてしまったので、次はより時間をとって取り組めるようにしたいですね。
AHCはたくさん出るほどレートが高くなるみたいなので、たくさん参加してレートあげていきたいです！
ここまでお読みいただきありがとうございました。
