perogram

AOJ Paint Color ペンキの色

Quiz

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

AC code

// 座標圧縮
// 変換テーブルを返す
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)

要素

  • 座標圧縮
  • imos
  • BFS

考察

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

f:id:peroon:20200201101335p:plain

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

imos

  • テープを貼る時、その情報を2次元配列に愚直に書き込むとO(WH)かかり、n枚貼るとTLEする
  • 愚直に書かずに「いもす法」をする

感想

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

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

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

  • 発売日: 2017/07/21
  • メディア: Video Game