AOJ Paint Color ペンキの色

Quiz

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0531

AC code

• http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4146310#1
• 座標圧縮（変換テーブルVER）

// 座標圧縮
// 変換テーブルを返す
VI make_compress_table(vector<ll>& A){  
  // 変換表
  auto B = A;
  sort(ALL(B));
  auto it = unique(ALL(B));
  B.erase(it, B.end());
  return B;
}

ll compress_by_table(VI& T, ll v){
  return lower_bound(ALL(T), v) - T.begin();
}

公式解説(JOI)

• https://www.ioi-jp.org/joi/2007/2008-ho-prob_and_sol/2008-ho.pdf
• これの「５」

要素

• 座標圧縮
• imos
• BFS

考察

• W, Hの範囲が広いので、BFSもできないしメモリに二次元配列も確保できない
• 一方でテープの数は1000なので座標圧縮すればいい
• 類題は蟻本p150にある
• テープの左端と右上は座標圧縮の対象とするとして、他にも必要だろうか？Yes, そこに隣接する4近傍が空白なのかの情報も残す必要がある。
• そうしないと、下記画像でいうIOIの各文字がくっついてしまい、白い領域の数が変わってしまう

• 座標圧縮された2次元領域なら空間計算量、時間計算量共にO(n²)に収まるのでBFSして答えを求められる

imos

• テープを貼る時、その情報を2次元配列に愚直に書き込むとO(WH)かかり、n枚貼るとTLEする
• 愚直に書かずに「いもす法」をする
  • 参考：https://imoz.jp/algorithms/imos_method.html

感想

• これで解くことができました
• 「やるだけ」とも言えるが、はじっこや文字間のスペースに注意して書く必要があった

Splatoon 2 (スプラトゥーン2) - Switch