概要

ほぼ何もできなかったといってもいい。

最初の方針

連結成分をノード、「隣接する」というのを辺と考えるとグラフができるので、そのグラフからグリッドを作ろうと思いましたが、実装が大変で2時間経過。スジが悪いと思い直してビジュアライザをいじっていると、与えられたグリッドを白に塗っていくのほうが実装が簡単なことに気づきました。

かなりバグ散らかしつつ終了10分前くらいにかなりナイーブな貪欲ができたのでそれを提出。終了です。

白に塗れるところは貪欲に白に塗っていく。

真ん中あたりのエリアが大きいですね。これらを隣接条件等を崩さないように圧縮していければなあと思いつつ終了しました。あと4時間ほしい。

#AHC024
seed=0 で 1996 点
中心に向かって縮める感じで pic.twitter.com/eQTnDwj8wW
— ゴジラ＠競プロ (@gojira_kyopro) 2023年9月24日

中心に寄せる貪欲らしいです。貪欲でもここまでいけるらしい。

左上に寄せていき、最後にぎゅっと圧縮する手法。おお、と思いました。AHC系は「はしっこに寄せる」という発想はよく見る気がします。

アニメーション機能を使って可視化してみました #AHC024 #丸紅 https://t.co/ACJ86sOuHc pic.twitter.com/8ysGQfQg0O
— ymatsux (@ymatsux_ac) 2023年9月24日

消せる行や列を消すという発想。「隣接条件を崩さずにどう圧縮するか」というのを考えたとき、たしかに「1行ごっそり消せるなら消す」というのは実装ラクそう。天才や……

AHCやることメモに「まずビジュアライザをいじる」って書いてあるだろ。なぜそれをしないんだ。

短時間コンテストは実装のしやすさ・速さがかなり重要だと感じました。

あと最近、C++でクラスを書くときはメンバ変数にm_のプレフィックスをつけているのだがいい感じ。メンバにアクセスするときは通常this->を使うと思うのだが、長いのがやだ。