AtCoder Beginner Contest 167 (ABC167) ふりかえり

5月10日に開催された、ABC167のふりかえりです。今回は危なかったけど、茶色パフォーマンス安定してきました。

※かなりごちゃごちゃしたコードになっているので、真似はおすすめしません。

A - Registration

普通に一文字ずつ比べた。

#include<bits/stdc++.h>
using namespace std;

int main(){
 
  string S, T;
  cin >> S;
  cin >> T;
  
  for(int i = 0; i < S.size(); i++){
    
    if(S.at(i) != T.at(i)){
      
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}

B - Easy Linear Programming

うっかり “WA” を出してしまいました。原因がわからず、何回もミスするのが怖かったので下記のクソみたいな実装をしました。

B問題で "WA" 出してしまったときの、胸がキュンとする感じというか、冷や汗が出る感じ、健康に悪いです。

#include<bits/stdc++.h>
using namespace std;

int main(){
 
  long long A, B, C, K, i, cnt = 0;
  cin >> A >> B >> C >> K;
  
  for (long long i = 0; i < K; i++){
    
    if (i + 1 <= A){
      cnt++;
    }else if(i + 1 > A + B){
      cnt--;
    }
  }
  
  cout << cnt << endl;
  return 0;
}

計算時間...笑

C - Skill Up

N と M の大きさをちゃんと確認していなくて本番ではスルーしちゃいました。bit 全探索で普通に解けました。今回最も後悔している問題です。

#include<bits/stdc++.h>
using namespace std;

int main(){
 
  int N, M, X, i, j, bit, p_min = 1200001;
  cin >> N >> M >> X;
  vector<vector<int>> A(N, vector<int>(M, 0));
  vector<int> C(N);
  
  //入力
  for(i = 0; i < N; i++){
    cin >> C.at(i);
    for(j = 0; j < M; j++){
      
      cin >> A.at(i).at(j);
    }
  }
  
  //bit全探索
  for(bit = 0; bit < (1 << N); bit++){
    
    int p_sum = 0, flag = 0;
    vector<int> S;
    vector<int> A_sum(M);
    
    for (int i = 0; i < N; i++) {
      if (bit & (1 << i)) {
        S.push_back(i);
      }
    }
    
    for (i = 0; i < S.size(); i++) {
      for(j = 0; j < M; j++){
      
        A_sum.at(j) += A.at(S.at(i)).at(j);
      }
      p_sum += C.at(S.at(i));
    }
    
    for(i = 0; i < M; i++){
     
       if(A_sum.at(i) < X) {
         flag = 1;
       }
      
    }
    if(p_sum < p_min && flag == 0) p_min = p_sum;
  }
  
  //結果の表示
  if (p_min == 1200001){
    cout << -1 << endl;
    return 0;
  }
  cout << p_min << endl;
  return 0;
}

D - Teleporter

C問題からD問題へ逃げてきました。

テレポートの回数が 10^18 なので、普通に辿っていると間に合いません。循環しているところをうまく省略するのがミソです。

最初に一巡したときにいる町を算出し（下記コードの配列 H で管理）、最初の町からその町にたどり着くまでのループ回数 j 、一巡するまでのループ回数 i - j を求めます。

で、最初の町から (K - j) % (j - i) + j 回ループして終了。

最初、j > K の場合を考えていなくて"WA"になったのでかなり焦りました。ギリギリで気づいて "AC"。

#include<bits/stdc++.h>
using namespace std;

int main(){
 
  long long N, K, i, j, cnt = 0, a, b, _K;
  cin >> N >> K;
  vector<long long> A(N), H(N, 0);
  
  for(i = 0; i < N; i++){
    cin >> A.at(i);
    A.at(i)--;
  }
  
  i = 0;
  a = 0;
  while(H.at(a) == 0){
    
    H.at(a) = 1;
    a = A.at(a);
    i++;
  }
  
  j = 0;
  b = 0;
  while(b != a){
    
    b = A.at(b);
    j++;
  }
  
  a = 0;
  
  if(K - j < 0){
    _K = K;
  }else{
    _K = ((K - j) % (i - j)) + j;
  }
  
  for(long long k = 0; k < _K; k++){
    
    a = A.at(a);
  }
  
  cout << a + 1 << endl;
  return 0;
}

E - Colorful Blocks and F - Bracket Sequencing

たどり着きませんでした。

まとめと反省

• AB-D と解いてパフォーマンスは 798
• レート 194 → 282
• 最初の方で "AC" しても焦らない
• 問題はちゃんと読みましょう