読者です 読者をやめる 読者になる 読者になる

SRM 562 Div2 Medium PastingPaintingDivTwo

問題

キャンバスに白黒のクリップボードをコピペをしていく.i回目のコピペは左上を(i, i)に合わせてコピペする. T回コピペを繰り返す時に黒色に塗られた数を答える問題

解答

T回シミュレーションしたのでは時間がかかる. クリップボードの大きさをn * mとすると,min(n, m)回コピペした後の黒色の増加量は一定なことが分かる. min(n, m)回だけシミュレーションし,後は残りの回数*最後の増加量を足しあわせて答えれば良い.

ローカルとArenaの答えが違う

ローカルでは正しい答えが返ってくるのに,Arenaだと若干小さい値が返ってくる. 原因が全くわからない.

分かる人がいたら教えて下さい.

以下は,Arenaの結果です.ローカルでは 12000000000が返ってきます.

Args: {{"B", "B", ".", ".", ".", "B", "B", "B", ".", ".", "B", ".", ".", ".", "B", "B", "B", "B", ".", ".", ".", "B", "B", "."}, 1000000000}

Expected: 12000000000

Received: 11999999997

class PastingPaintingDivTwo
{
public:
  long long countColors(vector <string> clipboard, int T)
    {
      int n = clipboard.size();
      int m = clipboard[0].size();
      vector<vector<bool> > board(n, vector<bool>(m, false));
      vector<vector<bool> > canvas(3*n, vector<bool>(3*m, false));
      int i, j, k;
      for(i = 0; i < n; i++){
        for(j = 0; j < m; j++){
          if (clipboard[i][j] == 'B') board[i][j] = true;
        }
      }
      long long num_black = 0;
      long long previous_num_black = 0;
      for(i = 0; i <= n; i++){
        previous_num_black = num_black;
        if (i == T) return num_black;
        for(j = 0; j < n; j++){
          for(k = 0; k < m; k++){
            if (board[j][k] == true && canvas[i+j][i+k] == false){
              num_black++;
              canvas[i+j][i+k] = true;
            }
          }
        }
      }
      cout << (previous_num_black + (num_black - previous_num_black) * (T-n)) << endl;
      return previous_num_black + (num_black - previous_num_black) * (T-n);
    }
};