naoya_t@hatenablog

いわゆるチラシノウラであります

ARC006-D アルファベット探し

AtCoder Programming Contest 過去問

みょんみょんがツイートしてたやつ

7x7ピクセルで定義されたA,B,Cの文字（正の整数で等倍拡大したもの、90度刻みで回転したものを含む）の出現回数を数える問題。
f:id:n4_t:20170702234607p:plain

CNN（畳み込みニューラルネットワーク）の出番？
いや
そういう問題ではないな

縦横にスキャンしてエッジ検出してみたりとか思ったけど
逐一パターンマッチしないといけない手間は変わらない

そこで
UnionFindで縦横斜めに隣接した黒色ピクセルをunionして
1文字を1つの島にしてみる
島の総黒色ピクセル数＝UnionFindだしすぐ分かる

元の黒色ピクセル数（A=12, B=16, C=11）で割り切れるかどうかで良いのでは？と思ったんだけど、例えば48とか、AでもBでも割り切れるじゃん（※実際は自乗数でしか割らないからそういうことにはならない。後述）
、それだと困るから島の寸法を見てそれで割ったやつを分類しよう

島の寸法＝共通のrootを持つピクセル集合で座標の範囲を調べるだけ
7x7ピクセルだけど外側の1ピクセルは使われていないので実質5x5
5×5を正の整数nで拡大した5n×5nピクセルのboxに収まる島しかないはずなので
n=島の寸法÷5
5n×5nピクセル（元のn倍の寸法）の文字の黒色ピクセル数は、元のやつのn^2倍のはず
島に属する黒色ピクセル数をn^2で割るとどれかになるのでそれをインクリメント
回転については考慮する必要がなかった

高々H*W=1000^2=10^6ピクセルで、黒ピクセル率は"B"を最密に充填した場合でも1/3未満、なのでunionSet()の呼び出し回数は高々HW×8/3^2回＜89万、1回の処理は（一番黒色ピクセル数の多い島になる全画面BでもHW/3未満なので）log(HW/3) のオーダー、としたら時間的にも余裕。島の寸法を調べるのも全ピクセル走査するだけなのでO(HW)

→AC
Submission #1390140 - AtCoder Regular Contest 006 | AtCoder

バリエーション

縦横の倍率が異なるものでも

    assert(w == h);
    int mag = w / 5;
    assert(area % (mag*mag) == 0);
    area /= (mag*mag);

のところを

    int magW = w / 5, magH = h / 5;
    assert(area % (magW*magH) == 0);
    area /= (magW*magH);

にするだけで多分行ける。

まあこれは A,B,C が３つとも1つの島で成り立っていて、かつ使われている黒色ピクセル数が互いに異なるお陰で。
黒色ピクセル数が同じになる文字が来たらどうしますかね。

****
*   *
*   *
*   *
****

*****
*
****
*
*****

Dは14ピクセルだから良いけど、EがBと同じ16ピクセルのデザインだったらひと工夫必要になる。
小文字の i, j みたいなやつが来たら1つ飛んだ先もUnionFindするか、ドットを無視するかするのかな。少し面倒。

追記

模範解答。


http://arc006.contest.atcoder.jp/submissions/1389415

みょんみょんの模範実装見たらDFSで（スマートに）島サイズを見てて。というか塗りつぶし。
そして

int calc(int a) {
    for (int i = 2; i * i <= a; i++){
        while (a % (i * i) == 0) a /= (i * i);
    }
    return a;
}

という謎の関数があって、これを通した値が3,1,11のいずれかになるもの、って感じで解いてる。12k^2, 16k^2, 11k^2 から自乗数な約数を抜いていくと3,1,11になるってことね。

12,16,11で割り切れるかどうかだと48の時困るから島の寸法を見ようとか思ってたわけだけど、これならその必要もない。（縦横の倍率が違ってもいいことになるとこれでは対応できないけれど、制約からの必要最小限の実装がさらっと出来るのはやっぱり凄いなあと）

勉強になりました！