【AHC始めました】AHC024参加レポート

こんにちは、そろそろAHCの色も欲しいなーって思ったので参加してきました。

基本的に答えがある方が好きなのでAtCoderではこれまでアルゴリズムの方をやってました。

今回は参加レポートということで時系列で思ってたこと考えてたことをつらつらと

問題の理解

隣接関係を崩さないようになるべく少ないマス数で表現する

明らかに削っていいマスはわかるけどどうやってプログラムでやればいいかわわからない
ダウンロードしたツールもよくわからない
- 昨日Introduction to Heuristics Contestで少し予習したときはtester.pyがあったけどそれがない
  - →「あーこれ自分で評価関数的なやつを作らなきゃいけないのか、隣接情報とかよくわからないし作るの無理やな！」

行を間引いてみる

上から一行ずつ見て、下の行と全く同じ行は削除する。[code]

え？？？

ビジュアライザを見てみたらエラーが出てました。よく見たら出力行が1行足りなかったみたいです。

直して提出してみる

まだだめ

行単位で消すなら下の行が同じなら消していいは間違いで、上下の行が同じなら消していいが正しいです。

直して提出[code]

150点になりました！

ただこれはぬか喜びで、ルールに"作成した地図に含まれる色 0 のマスの総数を E としたとき、E+1 の得点が得られる。"とあるので、つまり0点です。

ならば、初見で感じた明らかに消して良いマスを消す実装をするしか無いです。

凸を消してみる

といっても、腰が重いので、凸部分を消せば、行単位の削除できるんじゃね？

この真中部分を青に揃えるコードを実装してみる→150点から変わらず

消していい場所を消す実装をする

code

外周に0の番兵を置く
自信含む周囲9マスの色の数が2色以下かつ0があれば消していい

(´・ω・`)

手元のサンプルでダメなやつを探してみる

左下が途切れてます。

さてどうしよう？

BFSを使う

code

組み込むのに40分くらいかかりました
事前にdefaultdictで色番号ごとの連結数を記録
消した後、周囲の消した色のマスの座標を取得し、連結数をBFSで数える
- bfsは計算量高々50**4（ほんと？）なので動くと判断
非連結になってたら戻す

良さそう

スコアが出た！

これに凸を消すロジックを入れたら微改善しました。

地図の形状ごと変えに行く

後なにできるかを考えると、もう中の方の色を圧縮するしか無いんですよね・・・・
でも何らかのプログラムでできる気がしない
とりあえず色をできるでけ右に伸ばせば、これまでの手法で削れるマスが増えるかも知れない

# 右に進撃するコード
for _ in range(2):
    for i in range(1,N+1):
        for j in (range(1, N)):
            color1, color2 = C[i][j], C[i][j+1]
            if color1 == color2:
                continue
            _, s1 = bfs(C,(i,j))
            _, s2 = bfs(C,(i,j+1))
            C[i][j+1] = color1
            d[color1] += 1
            d[color2] -= 1
            _, s1_2 = bfs(C,(i,j))
            i2, j2 = get_around_color(C,i,j+1,color2)
            n, s2_2= bfs(C,(i2,j2))
            if (s1 != s1_2) or (s2 != s2_2) or (n != d[color2]):
                C[i][j+1] = color2
                d[color1] -= 1
                d[color2] += 1