ABC307 Cなのに水色diffとなってしまった問題「Ideal Sheet」を解いてみた 

VS load(){
  ll H,W;cin>>H>>W;
  VS S(H);
  rep(i,H)cin>>S[i];
  return S;
}

// Aの上にBを描く
VS paint(VS A, VS B, ll dy, ll dx){
  ll H = B.size();
  ll W = B[0].size();
  rep(i,H){
    rep(j,W){
      if(B[i][j]=='#'){
        A[i+dy][j+dx] = B[i][j];
      }
    }
  }
  return A;
}

VS crop(VS A){
  ll H = A.size();
  ll W = A[0].size();
  ll min_y=inf;
  ll min_x=inf;
  ll max_y=-inf;
  ll max_x=-inf;
  rep(i,H){
    rep(j,W){
      if(A[i][j]=='#'){
        chmin(min_y,i);
        chmin(min_x,j);
        chmax(max_y,i);
        chmax(max_x,j);
      }
    }
  }
  VS ret;
  FOR(i,min_y, max_y+1){
    string s;
    FOR(j,min_x, max_x+1){
      s.push_back(A[i][j]);
    }
    ret.push_back(s);
  }
  return ret;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    VS A = load(); A=crop(A);
    VS B = load(); B=crop(B);
    VS X = load(); X=crop(X);

    VS plain = VS(20, string(20,'.'));

    rep(dy0,11){
      rep(dx0,11){
        rep(dy1,11){
          rep(dx1,11){
            // paint A
            VS temp = paint(plain, A, dy0, dx0);

            // paint B
            temp = paint(temp, B, dy1, dx1);

            // cut space
            VS cropped = crop(temp);

            if(cropped==X)yes();
          }
        }
      }
    }
    no();
    
    return 0;
}

コーナーケース

  • というべきなのかどうか、最初の提出ではWAになった https://atcoder.jp/contests/abc307/submissions/42956280
  • 下記の画像は実現可能 (Yes) ですが、WAの提出では取りこぼしてしまいます。A, Bにも事前にcropをしておく必要がありました

筋肉解法

  • 上記コーナーケースに気づけなかったとしても、探索範囲を雑に広げることでACできました
  • これは最後の手段でしょう
  • 透明なシートのサイズを20x20 => 40x40
  • オフセットの探索範囲を11 => 21
  • とすることで1.5秒かかりますがAC https://atcoder.jp/contests/abc307/submissions/42959034
    • (A, Bのcropなし)