abc269に挑んだの初心者の感想

A問題からD問題までのコードと感想です．

A - Anyway Takahashi

入出力と四則演算ができれば解ける問題です．

int a, b, c, d;
int main(){
  cin >> a >> b >> c >> d;

  cout << (a + b) * (c - d) << endl;
  cout << "Takahashi" << endl;
}

B - Rectangle Detection

長方形の角の座標を出力する問題です．縦軸と横軸でそれぞれ、#が出現する位置と終わる位置を検査すれば解けます．思った以上に、場当たり的なごちゃごちゃしたコードになってしまったのが失敗です．もっと効率的な方法を考えるべきでした．本番だと焦ってしまい、とりあえず正解すればよいやという感じになってしまうのが反省点ですね…

vector<string> s(11);

int main(){
  int a = 0, b=0, c=0, d=0;

  string s1;
  erep(i, 1, 10){
    cin >> s.at(i);
    if(s.at(i) != "..........") s1 = s.at(i);
  }

  erep(i, 1, 10){
    if(a == 0 && s.at(i) != "..........") a = i;
    if(a != 0 && s.at(i) == ".........."){
      b = i-1;
      break;
    }
    if(i==10) b=10;
  }

  erep(i, 0, 9){
    if(c==0 && s1.at(i)=='#') c = i+1;
    if(c != 0 && (s1.at(i) == '.')) {
      d = i;
      break;
    }
    if(i==9){
      d = 10;
    }
  }

  cout << a << " " << b << endl;
  cout << c << " " << d << endl;

}

より分かりやすい解法

公式の解説にある解法を簡単に述べます．

1. 全探索

2. 長方形の性質を利用

1の全探索について考えます．A, B, C, Dの組は10^4くらいで抑えらますし、一回の探索で文字列の比較は10^2です．
　　全ての(i,j)についてA≤i≤BかつC≤j≤Dならば、S[i][j]==#が成立するか
を調べればよいです．よって、計算量的に単純に全探索しても正解できます．効率は悪いですが、発想の一つ目として全探索を思いつくことは大切です．

2では、#が長方形をなしていることに着目します．すわなち、
A：長方形の一番上の行＝「S[i][j]==#」が成立する最小のi
B：長方形の一番下の行＝「S[i][j]==#」が成立する最大のi
C：長方形の一番左の列＝「S[i][j]==#」が成立する最小のj
D：長方形の一番右の列＝「S[i][j]==#」が成立する最大のj

と考えることができます．長方形の辺を最小と最大として捉え直せるかが鍵だと思います．連続的な数学ではなく、離散的なプログラミングだからこその発想ですね．私はこういう転換力がまだ弱いので、これから地道に訓練して慣れていくしかないですね．

C - Submask

DFSを使うか、bit全探索を使うか2つの方法があります．以下ではDESによる解法を示します．まず、Nの2^kの位が1のとき、値kを保持するベクトルを用意します．例えば、N=11なら2進数表記で1011なので(3, 1, 0)を保持します．再帰関数では、このベクトルの要素を一つずつ見ていき、その桁数を1に変更する方向と変更しない方向に分岐して再帰します．

ll n;
vector<ll> digits;
vector<ll> n_vec;

void dfs(ll i, ll num){
  if(i == digits.size()){
    cout << num << endl;
    return;
  }

  dfs(i+1, num);
  dfs(i+1, num|(1ll<<digits[i]));
}

int main(){
  cin >> n;

  rrep(d, 59, 0){
    if(n & (1ll<<d)) digits.push_back(d);
  }

  dfs(0, 0);
}

忘れがちなのは2進数表記でのbit演算の方法です．ある値xの2^dの位は
                                                 x & (1ll << d)
で求められます．また、ある値xの2^dの位を1に変更する場合は
　　　　　　　　　　　　　 x | (1ll << d)
でできます．

D - Do use hexagon grid

DFSを用いて、グラフを探索することで連結部をカウントします．あるある問題ですが、普段と異なる点は移動が6方向なことです．

int n;
vector<vector<int>> field(10000, vector<int>(10000, 0));
vector<int> dx = {-1, -1, 0, 0, 1, 1};
vector<int> dy = {-1, 0, -1, 1, 0, 1};

void dfs(int x, int y){
  field.at(x).at(y) = 0;

  rep(i, 0, 6){
    int new_x = x + dx.at(i);
    int new_y = y + dy.at(i);
    if(new_x <= 2000 && new_x >= 0 && new_y <= 2000 && new_y >= 0 && field.at(new_x).at(new_y) == 1 ) dfs(new_x, new_y);
  }
}

int main(){
  cin >> n;
  rep(i, 0, n){
    int x, y;
    cin >> x >> y;
    field.at(x+1000).at(y+1000) = 1;
  }

  int cnt = 0;
  erep(i, 0, 2000)erep(j, 0, 2000){
    if(field.at(i).at(j) == 1){
      dfs(i, j);
      cnt++;
    }
  }
  cout << cnt << endl;

}

無限に広いグリッドといいつつ、|X|<=1000, |Y|<=1000より外は探索する必要性がないことに注意しましょう．あと、実装時はx, yが正になるように+1000して調整しています．