💭

「解いたメモ」C - Shapes #Dlang

2 min read

問題

図形をぐるぐる回したり平行移動したりして2つの図形が一致するかをチェックする問題でした。
問題の単純さに比べて、実装が大変。
解くのにかかった時間は計測していませんがコンテスト中に解き切ることはできたのでしょうか。わかりません。
ABC C - Shapes 問題文

実装方針

2次元グリッドの幅Nは制約より最大でも200。図形は90度回転を3回行えば全パターンを試せるため、制約は特に気にしなくてもよさそうだと判断しました。

同じ図形かどうかを確認する処理は図形Sと図形Tの最上左の座標の差分から平行移動量を算出して実際に一致するかみてみる感じです。公式解説と同じですね。

コード

D言語での実装です。

int n;
char[][] s, t;
struct P {int x, y;}

// 2つの図形の面積が同じかどうか
bool firstCheck() {
  int cnt_s, cnt_t;
  foreach(y; 0..n) {
    foreach(x; 0..n) {
      if (s[y][x] == '#') cnt_s++;
      if (t[y][x] == '#') cnt_t++;
    }
  }
  return cnt_s == cnt_t;
}

// (0, 0)点から最初のブロックの位置を返す
P findFirst (ref char[][] board) {
  foreach(y; 0..n) {
    foreach(x; 0..n) {
      if (board[y][x] == '#') {
        return P(x, y);
      } 
    }
  }
  return P(0, 0);
}

// 図形の90度回転処理
char[][] rotate (ref char[][] board) {
  char[][] new_board = new char[][](n, n);
  foreach(y; 0..n) {
    foreach(x; 0..n) {
      new_board[y][x] = board[n - 1 - x][y];
    }
  }
  return new_board;
}

// 同じ図形かどうか
bool isSame (P offset) 
{
  foreach (y; 0..n) {
    foreach (x; 0..n) {
      // 図形s->図形t へ平行移動した座標
      auto next = new P(x + offset.x, y + offset.y);
      if (s[y][x] == '#') {
        if (0 > next.x || 0 > next.y|| next.x >= n || next.y >= n) return false;
        // 図形の不一致
        if (t[next.y][next.x] != '#') return false;
      }
    }
  }
  return true;
}

// 図形t を回転しながら図形が一致するか確認
bool solve() {
  if ( !firstCheck() ) return false;
  int i;

  do {
    auto fst_s = s.findFirst();
    auto fst_t = t.findFirst();
    // 図形s->図形t への変換用ベクトル
    auto offset = P(fst_t.x - fst_s.x, fst_t.y - fst_s.y);

    if ( isSame(offset) ) return true;

    // 図形が一致しなければ回転
    t = rotate(t);
  } while (3 > i++);
  
  return false;
}

void main() 
{
  // 入力
  n = inone();
  foreach(i; 0..n) s ~= instr().dup();
  foreach(i; 0..n) t ~= instr().dup();
  
  // 出力
  writeln( solve() ? "Yes" : "No" );
}

import std;

string instr() { return readln.chomp; }
T inone(T=int)(){return readln.chomp.to!T;}

提出結果

所感

制約がゆるいので、事前にデータ構造やアルゴリズムを知っていなくてもシミュレーションで解ける問題だろうという感じはしました。

コンテストでもこのような問題は定期的に出ますが、僕はまともに解けた記憶がありません。苦手なんだと思います。

Discussion

ログインするとコメントできます