2022/10/30に開催されたトヨタ自動車 プログラミングコンテスト2022(AtCoder Heuristic Contest 015)に参加しました。
前回のAHC014は、参加登録はしたもののまともに考察せずの提出せずで終了でした。考察の入り口で躓き、結局なにをしたらいいのかわからずで実装するモチベーションも上がらなかったというのが実態です。
しかし、今回も提出せずで終わると、今後もAHCは参加しないままでズルズルと来てしまうような気がするので、今回は、時間中は集中して取り組み、なんらかの提出はするぞという気持ちで臨むこととしました。
久々にAHC参加します。短期コンなので、とりあえず提出めざして頑張ります。
— devgenjin77 (@devgenjin77) 2022年10月30日
トヨタ自動車 プログラミングコンテスト2022（AtCoder Heuristic Contest 015） 告知 https://t.co/Z9xQg2sCdb
今回の結果
どんぐらいの順位良いとかいう基準がまだわからんですが、そこそこいい点数は取れたんじゃないかという印象です。
で、なんと今回は水色上位パフォという結果。レーティングは爆上がりして、一気に緑コーダーになれましたとさ。
久々にAHC参加します。短期コンなので、とりあえず提出めざして頑張ります。
— devgenjin77 (@devgenjin77) 2022年10月30日
トヨタ自動車 プログラミングコンテスト2022（AtCoder Heuristic Contest 015） 告知 https://t.co/Z9xQg2sCdb
振り返り
初回の提出から、いろいろ試行錯誤はしましたが、点数的にはあまり改善されませんでした。
A問題
まずは大まかな方針を決めたいところだが、どうすればいいのかよくわからん。
ということでとりあえず、とっかかりとして実装できるところから手を付けていく。まず入力部スコアを計算する関数、次に箱を傾けた時に中の飴が一方向に寄せて行く処理を実装していく。
大体1時間程度で実装し、あとは適当に方向を決めたアウトプットを元に、Webビジュアライザーの結果と比較してみる。最初、これが全然合わなくて、デバッグに苦心するが、大体2時間程度でちゃんと動くものができた。
次に、方向を決める際の方針を考えてみる。まずは箱の中の飴をなるべく同じ種類で隣接させる必要があるとのことなので、一番多いアメを前方に、二番目に多いアメを後方に寄せるため、次にもらえるアメが何かを先に見て、一番多いアメなら後方に倒す、二番目なら前方に倒すということを考えてみる。
次に、三番目ならどうするかだが、箱の左側と右側それぞれに今存在するアメの個数をカウントして、数の少ない方向に倒していくといい感じにいくんじゃないかと推察。まあ、根拠はありませんが。。
あとは、後半にかけていくと、箱を傾けたときのスコアが最大化できればいいんではということで、後半のターンでは、アメをもらってから4方向の傾きを試し、一番スコアが大きかった傾け方で決めることとする。
という感じで、一通りの実装とビジュアライザーでのデバッグが終わったので、ローカルでテスト。あとは微調整していろいろスコアの変化を見ていくこととする。
動かしてみた結果としては、ターン数で処理を分けてもスコアの改善にはあまり寄与しない感じというところ。ということで、一回目の提出としては、以下の実装で出してみる。
次に来るのが一番多いアメなら後方に倒す。二番目なら前方に倒す。三番目なら、左右どちらにアメが多いかをカウントして多い方に傾ける。
10ターン目以降で、次に三番目に多いアメがくる場合は、4方向傾きを試してみて、スコアの一番大きい傾きを結果とする。
初回提出が6時ぐらいで、残りはあと1時間程度。ここでスコアを改善できないかということでいろいろ試してみると、結局三番目に多いアメの時に左右どちらが多いかという処理がイマイチという感じ。
この処理を消した提出でスコアが少し改善できたところで終了としました。
最終提出コード
https://atcoder.jp/contests/ahc015/submissions/36096647
これまでの実績
レーティングは一気に200以上上がり、色変しました。
総括
今回の問題については、最初の考察が結構いいところを突いていたようで、いい得点が出てくれました。
反省点としては、ローカルでのテストの効率があまり上がらずで、結局いろんなパターンを試し切れていない感じがあるというところ。
AHCでスコアを伸ばすには、いろんな解法を一通り試行して結果を比較するプロセスが必要という感じなので、その辺を効率的に実施できる仕組みを次回までに作ってみたいと思います。
ということで、また次回も頑張ります。
