# AHC013 2022/08/09 21:00 ～ 2022/08/16 21:00

https://atcoder.jp/contests/ahc013
A- Server Room

## 1日目
### 所感
PCを動かして直線上に連結できるようにする問題。
全てを接続する事は不可能な場合が多そうなので、上手く諦めるのが重要そう。

直線上に配置する問題なので、以前の「ハイパーお掃除ロボット」に近そう。
https://atcoder.jp/contests/rcl-contest-2020-final/tasks/rcl_contest_2020_final_b

(visualizer)
https://twitter.com/kusano_k/status/1236223937119277057

Kは2～5、5種類だと相当混雑する。
PC数と手数が同じなので、あまり込み入った移動はできないはず。
空きマスはかなり少ない印象。seed=7
かなり広めでこれ。seed=20

各PCから十字に評価を伸ばして、PCにぶつかるたびにペナルティをかける暫定評価が有用そう。
疎なマップでは、手順はあまり重要でないので、PCの配置状態を焼いて移動分をコストと見れば良さそう。
密なマップでは、手順が影響するので、そこの判定は上手くやる必要がありそう。
というか実質スライドパズルみたくなる。

別種類のPCを繋げるのは？
→利点はある。
スコアは接続数をnとした時、n * n / 2 になる。
乗算で増えていくので、別種PCを接続しても十分大きなクラスタが
形成されるなら、接続をする手はある。
混ざったスコアは接続数をnとした時、(n-1) * (n-4) / 2
→1種のPCでできるだけ大きなクラスタを形成するのが重要そう。
疎なケースは1種を上限の100個接続は必須そう。

スコア感
1種類100個接続で 4950
別1個混じり101個接続で 4850 その差100。
1種類15個接続で 105点。

盤面の最大はK=5のN=48
48 * 48 = 2304
bit配列で複数グループ持っても、そこまででかくないか。
初めから1次元配列で構えるか。

接続の表現。gridに上下左右の方向データだけ持っていればいいのでは？
右か下だけでいい。左右の接続と上下の接続を別々にbitで持ってもいい。
盤面が0じゃなくなるまでパスを伸ばすだけ。
bitの数だけ手数がかかることもわかる。

順位表は、wanuiさんの199,460(199K)。

**TODO**
- データ構造の検討(なにで盤面と接続を持つか)
- 適当に近場で繋げる
- 正確なスコアを評価する(フルスキャン)
- 疎な状態を前提に山登りで移動を考える

## 2日目

- データ構造の検討(なにで盤面と接続を持つか)
- 適当に近場で繋げる

これやっていく。
クラスタとして過剰な接続を判定したい。
未接続マスを見つけたら、そのクラスタのみで全盤面を走査仕切る。
接続用のケーブルは盤面に別の文字として置く。'+'

できた。seed=0
やはり疎なケースはmoveが必要。seed=1
こういうのは、スライドパズルしてほじくり返す必要がある。seed=7。

まずはPCの種類を決め打ちして、貪欲的に100個繋げる動きをするか。

ローカルでまとめて処理するのは作った。

順位表は、simanさんの267,599(267K)。
100個のクラスタ4950 * 50ケース = 247,500(247K)
なので、方向は妥当。

**TODO**
~~データ構造の検討(なにで盤面と接続を持つか)~~
~~適当に近場で繋げる~~
~~ローカルのまとめて処理~~
- 貪欲的にスライドパズルして100個のクラスタを目指す
- 正確なスコアを評価する(フルスキャン)
- 疎な状態を前提に山登りで移動を考える

## 3日目 山の日

短い夏休みに入ったが、ちょっと疲れ気味。ぼちぼちやる。

- 貪欲的にスライドパズルして100個のクラスタを目指す

まずはひとつのPC種のみでクラスタを形成できるようにする。した。
あるクラスタから同種のPCの距離を算出する(暫定評価関数)。
→PCから十字走査は距離0、空きマスは距離10、別種PCマスは距離25とか。
→十字走査が別種PCで止められているなら、距離12を足す。

seed=1。全部つながっていると判定しているが、自身のケーブルで接続を切っている。
ケーブルを前提に移動するようにした。seed=5
わーい、全部つながった。
まだ他PCを動かさないので、全部つながらないものがある。
1マスだけ動かす。2マス動かさないとダメなものが残る。seed=3
それよりも、こういうスライドパズルしないとダメなやつをどうにかする。seed=2
単純に開通させるより、対象PCを近づけた方が、他クラスタ生成時に楽。

簡易なスライドパズルをする。
→行きたい方向にPCがある場合、押しのけるようにした。
seed=2、解けた。

100ケースやって、79ケースで100個のクラスタができた。約80%。
100個つなげたら247Kなので、80%で200K代は乗る。順位表40位代。

順位表は、wanuiさんの319,757(319K)。

**TODO**
~~データ構造の検討(なにで盤面と接続を持つか)~~
~~適当に近場で繋げる~~
~~ローカルのまとめて処理~~
~~- 貪欲的にスライドパズルして100個のクラスタを目指す~~
- 正確なスコアを評価する(フルスキャン)
- 2種類目のクラスタ形成を考える
- 疎な状態を前提に山登りで移動を考える

## 4日目 有給

- 正確なスコアを評価する(フルスキャン)

これやる。
他PCが混ざった時のスコア計算にうまい方法が無いかジャッジ側見たけどforループでひとつひとつ調べてた。無念。
→できた。混ぜたクラスタが無いが一応ジャッジと同じスコア。
→現状100ケースでSum=457,790

seed=90、現状、距離0ラインへのスライドパズルを禁止しているので解けない。
距離0を解禁しつつ、望んだ方向へ押しのけるのを禁止したい。

levelの概念を入れる。
ある方向を軸とした時、そのラインから+/-に押しのけると考えられる。
±0、level一致の時にライン上に戻ってくるので、それを禁止する。
→した。Sum=456,315、85%が100個形成できた。

別PCと空きマスを挟んで停止するやつがいる。
→走査があっても近づくようにする。→空きマスを後方に確保。
→Sum=462,827、84%が100個形成

- 2種類目のクラスタ形成を考える

すでにある処理を使いまわして、手数だけ調整。
まずは単純に1種類100個形成の上で、2種類でクラスタを形成。
Sum=480,149

大体の場合で、最大2個の塊が限界な気がする。
内側で#上に100個のクラスタを作って周囲を別のクラスタで覆う形？

順位表は、wanuiさんの356,296(356

**TODO**
~~- 正確なスコアを評価する(フルスキャン)~~
~~- 2種類目のクラスタ形成を考える~~
- 次に1種類目の結果を固定して2種類目のクラスタを形成
- 疎な状態を前提に山登りで移動を考える

## 5日目

- 次に1種類目の結果を固定して2種類目のクラスタを形成

これやる。

seed=1。もともとつながっていたものが、
他のPCの移動で繋ぎ順が変わってつながらなくなる。

本来は繋げ方を上手くしたい。
が、とりあえずクラスタを保存して再現することにする。
した。バグりまくった。。。
Sum=520,754。思ったより伸びない。

seed=2、手数が足りてない。1手動かせば繋がるところもまだある。
lockが過剰にかかってた。
Sum=520,781。対して伸びない。

クラスタ形成の手数を削ることを考える。
→現状クラスタに属したPCは固定されちゃうので、そこを動かせるようにする。
→まずは各step毎のクラスタ状況も出力する。できた。

どうもdistを最小化しようとして、目の前のクラスタ化を後回しにしてるっぽい。
クラスタ化ができる手を優先して、Sum=577,698。
スライドパズルして複数手消費する場合のコストを増やして、Sum=583,129。
1000ケース回してみて、Sum=5851,385。

改善ポイント例
↑クラスタ済の右上の4を伸ばすのがベストだが、
↓動かせないので、未クラスタのPCを動かしてずれてしまう。

クラスタ済PCの移動を入れたが、点数は下がった。
Sum=583,084、使わないとSum=583,502。
ちゃんと全体のdist低下を計算してあげないと、これ以上はだめそう。
600Kは遠い。
Sum=586,963
Sum=5,899,337

バグを取って点数が下がるやつをやった。
582K

複数条件でそれぞれ貪欲してベストを出す。
Sum=587,439

スライドパズルの時、同時に動かす数に応じたペナルティを変えながら、ベストを出す。
Sum=601,227。お、乗った！

ただ、時間が厳しい。ジャッジ上だと手元の最大3倍かかるっぽい。
でかいケースの複数条件実行を削る。(これ不毛だな)
提出、300K乗らなかった。。。
手元、1000ケースでSum=6,009,786なので、ジャッジケースがしぶめ？

諦めて本質改善をしよう。

貪欲にもとめる時にちゃんと差分で距離を出す。
今回は条件をブラしながら、貪欲を何度も流すのがいい気がする。
→うーん、差分更新は難しいかも。
→でかい盤面に苦労しているので、でかい盤面だけ別で解く。

でかい盤面の解き方を考える。
→ぼんやりと筋は見える。(他PCが無く直線上に集められそうなライン)
→とはいえ、それをベースにするのは難しい。
→結局目の前の1手で繋げていくのが多い。
　→ある程度の距離で打ち切るか。
→十分早くなったが、点数はガタ落ち。Sum=571,555

打ち切りラインの調整。
ライン無限でSum=599,558。
300でSum=599,358 ←まだ時間over
200でSum=593,139

順位表は、wanuiさんの356,296(356K)※昨日同様
ただし、300K超えが増えてきた。現在15位。

**TODO**
~~- 次に1種類目の結果を固定して2種類目のクラスタを形成~~
- 差分評価をする☓
- 貪欲時に変化後の状態で評価
- 疎な状態を前提に山登りで移動を考える

## 6日目

今日が事実上のラスト。

貪欲時に対象の接続判定をしているけど、そこでケーブルを残すと点数が上がる。押し出し時とか、接続を切る動きの抑制になっている？

やはり距離の差分評価を真面目にやらないとダメかも。
→下がる方向の更新はわりと楽かも。
→たとえば、対象PCが1マス移動してクラスタ化した時、
updateはそのPCからの十字走査だけでいい。
→別PCを移動してクラスタ化した時も、正確にやると大変だけど、
単純に下がった分だけやって良さそう。(誤差を許容)
→動かしたものによって更新の考え方は変えられそう。

元の距離がどこの影響で決まっているかを保持して、
変更箇所から連鎖する部分をやり直す手はある。
update箇所は周囲と十字走査で、新たな影響元を探す。
→めちゃ大変。
→頑張ってやってみているけど、微妙にずれる。
→もういいや、暫定評価として使おう。
→だめだ、部分的に使っても時間かかりすぎる。
→遅延評価はいいかも。

メイン処理は変えてないが、バグが取れて点数が上がった。Sum=608,643。

距離の近いやつからやる。
N > 19 の場合に先頭5個をやる。高速化にも寄与。点数も上がった。
Sum=603,571　ブラしなし
Sum=613,045　ブラあり

クラスタの再生成をそろそろまともにしたい。

…点数変わらないはずの変更なのに、点数がコロコロ変わる。。。怖い。。。

バグを丁寧に直した。下がった。
Sum=607,129

繋げる時のパスの長さにペナルティをかける。
→いくつか重みを変えて、Sum=625,129。
→中央の場合にペナルティを増やす？
→クラスタ形成であまりながいやつは結ばないようにするとか。

あとはこういうやつをちゃんとやる。seed=4。
初期クラスタがでかすぎる。やはり最初から全部は結ばない方がいい。

提出、元の順位に戻った。

順位表は、wanuiさんの387,038 (387K)。圧倒的。

## 7日目

今日はお仕事。明日の21時まで。
1000ケース、Sum=6,297,484。

クラスタ、出力メモをもとに構築順を復元することにする。
したらかなり下がってしまった。Sum=603,321
元がこれ。Sum=622,616。
少しバグがあって、復元でSum=606,444。
両方やると、Sum=627,767
順番変えると、スコアが変わる。。Sum=626,876。
メイン以外のクラスタにしてはちょっと点数変化が大きいのが不安。
もろもろバグってた。
復元でSum=624,033。
以前のでSum=625434
両方でSum=626,229。

復元メインでいけそう。

バグ対応でつらくなったので、簡単に点数があがる工夫やる。

- ケーブルを飛び越える移動

こういうやつ。

流石に上がった。Sum=645,207。
条件整えて、Sum=650,544。
1000ケース、Sum=6,608,100。

提出、また元の位置に。

距離計算の判定をなるべく軽くする。
→した。

動きの確認
seed=0、最後の1マスがなんかのこる？
→levelが一緒のスライドパズルを禁止しているからだった。
→解除して、もう少し確かな条件にしたら下がった。Sum=649,411。

少しまともな条件にした。
ブラして、Sum=653,185。

dfsでベストのルートを選ぶ。
した。Sum=659,140。

順位表は、bowwowforeachさんの387,912 (387K)。熱い。

**TODO**
~~- 差分評価をする☓~~
~~- 貪欲時に変化後の状態で評価☓~~
- 接続のペナルティを考える
- クラスタの生成を賢くする
- 疎な状態を前提に山登りで移動を考える

## 8日目
ラスト

せまいケースで、クラスタ間の間を詰める。
だいたい空白率が30%以下がきつい。
→まずは直接移動を優先、Sum=660,990。
→実際にクラスタ済のPCを動かすのは、うーん。

2個目のクラスタで到達可能PCが多いところからスタートする。
した。Sum=664,378。

外枠に近いPCからクラスタ化を考える。
→盤面の下地として、コストboadを作る。
→外周キワはそれはそれでシャットアウトしちゃうのでよく無さそう。
→まずは単純に選ぶ際の足切りに、Sum=667,882。
→各貪欲時のペナルティとして使う、Sum=680,906。天才か？

盤面の下地、外周キワから何マス目を最小値とするか？
→2マスが良いと思ったが、0マスが一番良さそう。Sum=682,574。
→別seed100ケースでも、同じ傾向だった。
→0マスを初期値として、2マスもブラしに加える。Sum=683,002。
→1個目の初期クラスタの選定に活用、Sum=683,731。

スライドパズルがバグってた。
修正、深さを6まで読む。Sum=698,569。
別ケースでSum=692,733。
1000ケースで、Sum=7,031,777。7M！！！！

毎ターン時間checkしても点数下がらなかったからもっと攻める。
Sum=699,008。
初回実行とそれ以降とで点数がかわる。

提出。357K。もう少し上ブレるかと思ったけど、案外渋い。
実行時間は、2929 ms なので余裕はあるかな。

これやる。「せまいケースで、クラスタ間の間を詰める。」
→実際にクラスタ済のPCを動かす。
→だめだ、ブラしの調整だけで終わろう。
→調整した。Sum=699,419

→Sum=698441
別Sum=696377
別Sum=699361
別Sum=699468
別Sum=699179

別2Sum=709229
別2Sum=709898

最終提出
1Kだけ上げて、暫定13位でfinish。

## 反省会
賢い方法が取れず、貪欲を評価関数変えて何本もやる力技になった。
上位は山登り？

1位のbowwowさんが焼きなましだったっぽい。
2,3位は多点貪欲で、やりたいことは似てそう。
iwahiさんが乱択山登りとして、多点スタートで各貪欲の選択肢に乱数を加えてブラしてやってみたい。
これは使えるようにならねば。
https://iwashi31.hatenablog.com/entry/2022/08/17/000241

**できなかったこと**
- 接続のペナルティを考える
- クラスタの生成を賢くする
- 疎な状態を前提に山登りで移動を考える

**考えてたこと**
俯瞰して、真ん中のスペースが広いほどいい。
コの時型で繋げることを意識
中央になるにつれ距離ペナルティをかけるとか

埋まったPCをほじくり返す必要がある。
→空白マスに注目。接続マスの使用・対象PCへの最短経路上の空白マスは除外。
→なるべく外周の空白マスを利用。

距離の差分計算
→接続とそこからの距離は別持ちした方がいい。
→距離0を起点にdistBoadを構成する。