AtCoder Beginner Contest 269

https://atcoder.jp/contests/abc269

結果

A - Anyway Takahashi:AC(2:20)
B - Rectangle Detection:AC(11:26)
C - Submask:AC(60:05)
D - Do use hexagon grid:提出無し

A - Anyway Takahashi

整数$${a,b,c,d}$$が与えられ、一行目に$${(a+b)×(c-d)}$$の結果を、二行目にTakahashiと出力する問題

自分の回答

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
 
  printf("%d\nTakahashi\n", (a + b) * (c - d));
}

問題文の通りに

公式解説

同じため省略

B - Rectangle Detection

$${10×10}$$の . で埋められた文字列の$${S_{(i,j)}(A \leqq i \leqq B,C \leqq j \leqq D)}$$を # に書き換えた文字列が与えられ、$${A,B,C,D}$$を求める問題

自分の回答

int main() {
  char board[10][10];
  for(int i = 0; i < 10; i++){
    for(int j = 0; j < 10; j++){
      cin >> board[i][j];
    }
  }
 
  set<int> tate, yoko;
  for(int i = 0; i < 10; i++){
    for(int j = 0; j < 10; j++){
      if(board[i][j] == '#'){
        tate.insert(i);
        yoko.insert(j);
      }
    }
  }
  printf("%d %d\n%d %d", *begin(tate)+1, *rbegin(tate)+1, *begin(yoko)+1, *rbegin(yoko)+1);
}

#である$${i,j}$$を全て縦と横で分けてsetに入れて、その最初と最後の値+1を出力
コード的にはもうちょっときれいにできたとは思う

公式解説

int main(){
  vector<string> s(10);
  for(int i=0;i<10;i++){cin >> s[i];}
  int a=1e9,b=-1e9;
  int c=1e9,d=-1e9;
  for(int i=0;i<10;i++){
    for(int j=0;j<10;j++){
      if(s[i][j]=='#'){
        a=min(a,i+1);
        b=max(b,i+1);
        c=min(c,j+1);
        d=max(d,j+1);
      }
    }
  }
  
  cout << a << " " << b << "\n";
  cout << c << " " << d << "\n";
  return 0;
}

https://atcoder.jp/contests/abc269/editorial/4843より

そうかminとmaxでいいのか

なるほど

C - Submask

0以上の整数$${N}$$が与えられ、$${N}$$を2進数で表したとき、1である位を任意の数だけ0に変えた値を$${x}$$とし、$${x}$$が取りうる値を10進数で全て出力する問題

自分の回答

int main() {
  int64_t N;
  cin >> N;
  bitset<60> BN(N);
  bool one_position[60];
  int A = BN.count();
  int count = 0;
  int digit;
  for(int i = 0; i < 60; i++){
    if(BN[i] == 1){
      one_position[i] = true;
      count++;
    }
    else{
      one_position[i] = false;
    }
 
    if(count == A){
      digit= i + 1;
      break;
    }
  }
 
  for(int tmp = 0; tmp < (1 << A); tmp++){
    bitset<60> ans, s(tmp);
    int j = 0;
    for(int i = 0; i < digit; i++){
      if(one_position[i] == true){
        ans.set(i, s[j]);
        j++;
      }
    }
    printf("%ld\n", ans.to_ullong());
  }
}

bit全探索を使うのはすぐにわかったが、流石に$${N}$$そのままで総当たりしたら時間足りなそう
$${N_{(2)}}$$で1である場所だけが変わるため、1の数のビット数で全探索して、その結果を$${N_{(2)}}$$で1の場所に入れて10進数に変換し出力

ACしたのはいいけど無駄な変数とかがだいぶ多い気がする
間違いなくもっときれいに書けた

公式解説

int main(){
  long long x;
  cin >> x;
  vector<long long> res={0};
  for(int d=0;d<60;d++){
    if(x&(1ll<<d)){
      int sz=res.size();
      for(int i=0;i<sz;i++){
        res.push_back(res[i]|(1ll<<d));
      }
    }
  }
  sort(res.begin(),res.end());
  for(auto &nx : res){cout << nx << "\n";}
  return 0;
}

https://atcoder.jp/contests/abc269/editorial/4844より

$${N_{(2)}}$$の$${i}$$ビット目が1ならresにある要素全ての$${i}$$ビット目に1をにした要素を追加する操作を0ビット目から繰り返していくのか
そういうやり方もあるのか

なるほど

D - Do use hexagon grid

六角形のグリッドがあり、そのうち$${N}$$個のマス$${(X_{1},Y_{1}),(X_{2},Y_{2}),…(X_{N},Y_{N})}$$を黒く塗った時、黒いマスの塊がいくつあるか求める問題

自分の回答

この手の問題はやったこと無いからとっかかりすらわからんかった
1つ黒マスを選んでそこに繋がっている黒マスを選んでの繰り返しでいいのかな…コード的にはできそうではあるけどどうなんだろ

公式解説

#include<atcoder/dsu>

int mem[2010][2010]={0};

int dx6[6]={-1,-1,0,0,1,1};
int dy6[6]={-1,0,-1,1,0,1};

int main(){
  int n;
  cin >> n;
  dsu uf(n+1);
  vector<int> x(n+1),y(n+1);
  for(int i=1;i<=n;i++){
    cin >> x[i] >> y[i];
    x[i]+=1005;y[i]+=1005;
    mem[x[i]][y[i]]=i;
  }
  for(int i=1;i<=n;i++){
    for(int k=0;k<6;k++){
      int nx=x[i]+dx6[k];
      int ny=y[i]+dy6[k];
      if(mem[nx][ny]>0){
        uf.merge(i,mem[nx][ny]);
      }
    }
  }
  int res=0;
  for(int i=1;i<=n;i++){
    if(uf.leader(i)==i){res++;}
  }
  cout << res << "\n";
  return 0;
}

https://atcoder.jp/contests/abc269/editorial/4845より

AtCoderライブラリなんてものがあるのか…
まずdsuは要素をグループとしてまとまりで管理するもの、そしてグループの値の内1つがリーダーとなる(グループ名みたいなもの)
初期化時はn個の要素全てが自身をリーダーとする要素1つのグループに属する
要素名は0からn-1で固定
d.merge(要素A,要素B); でそれぞれの要素を含むグループを1つのグループにまとめ、リーダーの値を返す、新しいリーダーは要素Aを含むグループのリーダーとなるっぽい？また、AとBがすでに同じグループにいるならそのグループのリーダーの値を返す
d.leader(要素A); で要素Aを含むグループのリーダーを返す
他にも機能はあるけどここで使われてるのはこれだけか

で、menが黒マスの位置と番号を管理するのか、0が白マスでそれ以外の番号が黒マス
そうか繋がっているかは座標で判定するから六角形グリッドも四角形グリッドみたいな感じで２次元配列で管理できるのか
そして全ての黒マスに対して周囲に黒マスがあるかを調べ、あるならばその2つの要素をグループにまとめる
最後にリーダーの数を求めれば終わり

なるほど