AtCoder Beginner Contest 264

2022年8月19日 14:02

結果

A - "atcoder".substr():AC(3:47)
B - Nice Grid:AC(28:52)
C - Matrix Reducing:提出無し
D - "redocta".swap(i,i+1):AC(67:40)

A - "atcoder".substr()

atcoderの$${L}$$文字目から$${R}$$文字目を出力する問題

自分の回答

int main() {
  string at = "atcoder";
  int L, R;
  cin >> L >> R;
 
  for(int i = L - 1; i < R; i++){
    printf("%c",at[i]);
  }
  printf("\n");
}

atcoderの$${L}$$文字目から$${R}$$文字目までをforでループして出力

公式解説

int main(){
  int l,r;
  cin >> l >> r;
  string s="atcoder";
  cout << s.substr(l-1,r-l+1) << "\n";
  return 0;
}

https://atcoder.jp/contests/abc264/editorial/4581より

substr関数の存在は知らなかった
これは覚えておくと便利そう

B - Nice Grid

黒と白のグリッドが与えられ、上から$${R}$$行目、左から$${C}$$列目が黒か白かを判断する問題

自分の回答

グリッドが規則的だからいい判別式があるんだろうなと思いながらもそれを思いつかなかったためごり押し

int main() {
  bool grid[15][15]=
  {{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
   {0,1,1,1,1,1,1,1,1,1,1,1,1,1,0},
   {0,1,0,0,0,0,0,0,0,0,0,0,0,1,0},
   {0,1,0,1,1,1,1,1,1,1,1,1,0,1,0},
   {0,1,0,1,0,0,0,0,0,0,0,1,0,1,0},
   {0,1,0,1,0,1,1,1,1,1,0,1,0,1,0},
   {0,1,0,1,0,1,0,0,0,1,0,1,0,1,0},
   {0,1,0,1,0,1,0,1,0,1,0,1,0,1,0},
   {0,1,0,1,0,1,0,0,0,1,0,1,0,1,0},
   {0,1,0,1,0,1,1,1,1,1,0,1,0,1,0},
   {0,1,0,1,0,0,0,0,0,0,0,1,0,1,0},
   {0,1,0,1,1,1,1,1,1,1,1,1,0,1,0},
   {0,1,0,0,0,0,0,0,0,0,0,0,0,1,0},
   {0,1,1,1,1,1,1,1,1,1,1,1,1,1,0},
   {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}};
 
   int R, C;
   cin >> R >> C;
 
   if(grid[R - 1][C - 1] == 0){
    printf("black\n");
   }
   else{
    printf("white\n");
   }
}

$${15×15}$$くらいなら思いつかない式を考えるより手を動かした方が早い
とはいえもっと早くごり押しに切り替えるべきだった

公式解説

チェビシフ距離という中央としたマスからの距離、$${\text{max\textbraceleft}|R-8|,|C-8|\text{\textbraceright}}$$の偶奇で判断できる

int main(void)
{
  int r, c;
  cin >> r >> c;
  
  if(max(abs(r-8), abs(c-8)) % 2) cout << "black" << endl;
  else cout << "white" << endl;
  
  return 0;
}

https://atcoder.jp/contests/abc264/editorial/4578より

中心からのマス数は考えたけど層は思いつかなかった
なるほど

C - Matrix Reducing

行列$${A,B}$$が与えられ、$${A}$$の任意の行、列を1つ削除する操作を繰り返して$${B}$$と一致させられるかを判別する問題

自分の回答

行列削除はAPG4bで紹介されてた過去問でやったなとは思ったけど行列の削除のいい判断方法が思いつかなかった
最大$${10×10}$$だしごり押し気味でもなんとかなりそうではあるけどちゃんと動くものを書けるかは怪しい
それか行と列に同じ要素が同じ順番で存在するかを確認する方向でも行けるのかな

公式解説

int main(void)
{
  int h1, h2, w1, w2;
  int a[15][15], b[15][15];
  
  cin >> h1 >> w1;
  for(int i = 1; i <= h1; i++) for(int j = 1; j <= w1; j++) cin >> a[i][j];
  cin >> h2 >> w2;
  for(int i = 1; i <= h2; i++) for(int j = 1; j <= w2; j++) cin >> b[i][j];
  for(int i = 0; i < (1<<h1); i++){
    for(int j = 0; j < (1<<w1); j++){
      
      vector<int> hvec, wvec;
      for(int k = 1; k <= h1; k++) if((i & (1<<(k-1))) == 0) hvec.push_back(k);
      for(int k = 1; k <= w1; k++) if((j & (1<<(k-1))) == 0) wvec.push_back(k);
      if(hvec.size() != h2 || wvec.size() != w2) continue;
     
      bool match = true;
      for(int k = 1; k <= h2; k++){
        for(int l = 1; l <= w2; l++){
          if(a[hvec[k-1]][wvec[l-1]] != b[k][l]){
            match = false;
            break;
          }
        }
      }
      if(match){
        cout << "Yes" << endl;
        return 0;
      }
       
    }
  }
  cout << "No" << endl;
  return 0;
}

https://atcoder.jp/contests/abc264/editorial/4579より

bit全探索でどの行、列を削除するかを全パターン出し、残ったものが$${B}$$と一致するかを確認するのか

$${i,j}$$の二重forで削除する場所を1、残す場所を0で全探索
比較のために欲しいのは残る場所の位置情報なため、1を$${k-1}$$個左シフトしたものと$${i,j}$$で論理積を取った時に0となる$${k}$$が残る物の座標
$${A}$$と$${B}$$が一致するとき、行、列の数は当然共に同じなため、そうならないときcontinue
そして$${A}$$から座標の物を抜き出して$${B}$$と比較

なるほど

D - "redocta".swap(i,i+1)

atcoderの並べ替えである文字列が与えられ、隣接する2文字を入れ替える操作をしてatcoderにするには最短何回必要かを求める問題

自分の回答

int main() {
  vector<int> at(7);
  for(int i = 0; i < 7; i++){
    char S;
    cin >> S;
    if(S == 'a') at[i] = 0;
    else if(S == 't') at[i] = 1;
    else if(S == 'c') at[i] = 2;
    else if(S == 'o') at[i] = 3;
    else if(S == 'd') at[i] = 4;
    else if(S == 'e') at[i] = 5;
    else at[i] = 6;
  }
 
  int ans = 0;
  for(int i = 0; i < 6; i++){
    for(int j = 0; j < 7; j++){
      if(at[j] == i){
        ans += j;
        at.erase(at.begin() +j);
        break;
      }
    }
  }
  printf("%d\n",ans);
}

余計な移動を無くすならaから順番に探して正しい位置へ持っていくのを繰り返すのがいい感じがしたためそれで書いたら通った
正直これが最短となる理屈はわからん

公式解説

int main(){
  string s;
  cin >> s;
  
  map<string,int> mp;
  queue<string> q;
  
  mp[s]=0;
  q.push(s);
  
  while(!q.empty()){
    string current=q.front();q.pop();
    if(current=="atcoder"){
      cout << mp[current] << "\n";
      return 0;
    }
    
    for(int i=1;i<7;i++){
      string next=current;
      swap(next[i-1],next[i]);
      if(mp.find(next)==mp.end()){
        q.push(next);
        mp[next]=mp[current]+1;
      }
    }
  }
  return 0;
}

https://atcoder.jp/contests/abc264/editorial/4582より

1回の操作、2回の操作……で文字列が取りうる全てのパターンをatcoderになるまで繰り返し調べるのか
計算量すごそう、というか文字列の長さが$${x}$$ならばそれが取りうる順列は$${x!}$$だから計算量も同じか
しかしその分汎用性は高いな
なるほど

このようなやり方を幅優先探索と言うらしい
後で勉強しておこう

この記事が気に入ったらサポートをしてみませんか？