AHC071参加記

 

はじめに

AtCoder Heuristic Contest 071 に参加し、326位(perf 1173)でした。

参加したので参加記を残しておこうと思います。

問題

https://atcoder.jp/contests/ahc071/tasks/ahc071_a

• 縦40x横60のグリッドがある。
• グリッドにはところどころ穴が開いているマスがある。
• 下からレンガを積み上げて穴を隠すことができる。
• レンガの種類は5種類（幅1,3,5,7,9で高さはすべて1）あり値段が違う。
• レンガは回転不可。
• レンガの中央は必ず支えなくてはならない。
• なるべく安くなるようにすべての穴を防ぐのが目的。

穴の開いた障子があってその手前にレンガを積み上げて穴を隠すイメージに近いと思います（障子の格子がちょうどグリッドに相当します）。

解法

幅1のレンガを必要な分だけ積み上げたものを初期解とし、幅1のレンガをランダムに幅3～9のレンガに置き換える山登りで改善していきました。

初期解

初期解を1か所改善

最終解

改善の方針

この後の説明で使うため、まず最初にレンガの種類について説明します。レンガには

• 穴を隠すためのレンガ（隠蔽用レンガ）
• 上にあるレンガを支えるためのレンガ（支柱用レンガ）

の2種類があります。両方の用途を兼ねるレンガもありますが、この後の説明は「隠蔽用レンガ」の方に含めます。

本題に入ります。

現在の解から隠蔽用レンガを一つランダムに選んでより幅の広いレンガに置き換えます。

実装をシンプルにする目的ために、置き換えの位置はレンガの中心が変わらない位置のみとしました。

置き換えたレンガの下にあり、かつ中心列以外にある支柱用レンガを除去します。

その結果、得られた新たな解が

• 置き換えたレンガが他のレンガと衝突しない
• 置き換えたレンガがグリッドからはみ出さない
• 置き換えた後の全体コストが改善している

場合は、置き換えた解を新たな解とします。

この改善を繰り返して得られた解を最終解として提出するようにしました。

反省点

シンプルな初期解を作ってそこから改善していくというのはオーソドックスなアプローチではあるので、今回の進め方自体も悪くないように感じていたのですが、解説を読んでから改めて振り返ると、あまりよくなかったかもしれないと思います。

レンガを置き換えるという山登りを採用しましたが、下にあるレンガの除去処理の実装などが思ったより大変で、時間を取られてしまいました。

最終解を見ただけでも

• 無駄に長いレンガがある
• 置き換えるときに中心を固定したため改善の余地が小さい

のように改善できるポイントは思いつくのですが、実装が重く手が回らなかったです。

苦労の割に得られる成果が見合っていないので、そもそも立てた方針がよくなかったと思います。

とはいえ、解説にある上から置くレンガを決めていく方法は、自分の力では時間内にまとめ切る自信もないので、仕方ない結果だったようにも思います。

とりあえず上からレンガを置く方針はちゃんと復習しようと思います。

感想

あまり良い成果もなく終わってしまいましたが、反省点を振り返っても根本的に力不足な印象で、短期的に改善できそうなポイントでもなさそう。とりあえず復習して経験値を少し上げて、また次回に備えたいと思います。

ここまで読んでくださりありがとうございました。