AtCoderログ：ABC264

ABC264に参加しました

今回はA, Bの2完でした。
A：2分
B：20分

今回のコンテストでのレート変動

179→189（灰）

A問題-"atcoder".substr()

単純にsubstrを使用するのみでした。

// 提出コード
int main() {
  string s = "atcoder";
  int l, r;
  cin >> l >> r;

  cout << s.substr(l - 1, (r - l) + 1) << endl;
  return 0;
}

B問題-Nice Grid

完全に沼りました。
簡潔に解こうと思いながらも思いつくことができなかったので早めに自前で盤面を作成して判定するようにすればよかったです。
自身の解答では盤面をループで作成しましたが、このループも一工夫が必要なものなので, 公式解説のように文字列で盤面を定義してしまうのが良かったです。（チェビシェフ距離なんて知りません...）

// 提出コード
int main() {
  int r, c;
  cin >> r >> c;
  string arr[16][16];
  rep3(i, 1, 16) {
    rep3(j, i, 17 - i) {
      if (i % 2 == 1) {
        arr[i][j] = "black";
        arr[j][i] = "black";
        arr[16 - i][j] = "black";
        arr[j][16 - i] = "black";
      } else {
        arr[i][j] = "white";
        arr[j][i] = "white";
        arr[16 - i][j] = "white";
        arr[j][16 - i] = "white";
      }
    }
  }
  cout << arr[r][c] << endl;
  return 0;
}

C問題-Matrix Reducing

大半はこの問題と格闘していました。
解いている途中でbit全探索を使用して解けるであろうことは気づけたのですが最終的な実装までは辿りつきませんでした。
大体こういうのは試験時間が終わるとすっと解けたりしてしまう...

1 3 4 5
6 8 9 10
11 13 14 15
16 18 19 20

を変換して

6 8 9
16 18 19

に出来るかどうかを判定する必要がありました。
H1 * W1 の行列を H2 * W2に変換するので

• H1ある行から h行（h == H2）
• W2ある列から w列（w == W2）

抽出することを考えます。
その抽出する行, 列を選ぶ作業にbit全探索を使用しました。

// コンテスト後に提出したコード
int main() {
  int h, w, a, h2, w2, b;
  cin >> h >> w;
  vector<vector<int>> A(h);
  rep(i, h) {
    rep(j, w) {
      cin >> a;
      A[i].push_back(a);
    }
  }
  cin >> h2 >> w2;
  vector<vector<int>> B(h2);
  rep(i, h2) {
    rep(j, w2) {
      cin >> b;
      B[i].push_back(b);
    }
  }

  // bit全探索
  for (int i = 0; i < (1 << h); i++) {
    for (int j = 0; j < (1 << w); j++) {
      vector<int> H, W;
      vector<vector<int>> b(h2);
      for (int k = 0; k < h; k++) if ((i & (1 << k)) == 0) H.push_back(k);
      for (int k = 0; k < w; k++) if ((j & (1 << k)) == 0) W.push_back(k);
      if (H.size() != h2 || W.size() != w2) continue;
      else {
        bool flag = true;
        rep(k, h2) {
          rep(l, w2) {
            if (A[H[k]][W[l]] != B[k][l]) flag = false;
          }
        }
        if (flag) {
          cout << "Yes" << endl;
          return 0;
        }
      }
    }
  }

  cout << "No" << endl;

  return 0;
}

感想

やっぱり本番に練習の100%を出すのは難しいと再認識しました。
とりあえず、典型90問の★2〜3とABC-B問題埋めをやっていこうと思います。