AtCoder Beginner Contest 285

AtCoder Beginner Contest 285 - AtCoder

結果

A - Edge Checker 2:AC(2:32)
B - Longest Uncommon Prefix:AC(12:15)
C - abc285_brutmhyhiizp:AC(96:53)(2ペナ)
D - Change Usernames:AC(81:24)

A - Edge Checker 2

示された木(画像略)において$${a}$$番と$${b}$$番の点が直接結ばれているかを判断する問題

自分の回答

int main(){
  int A, B;
  cin >> A >> B;
  if(B == 2 * A || B == 2 * A + 1){
    printf("Yes\n");
  }
  else{
    printf("No\n");
  }
}

全列挙はめんどくさいから法則無いかなと見てたら$${a}$$と直接繋がる$${b}$$の番号は$${2a}$$と$${2a+1}$$だったためそれにして終わり

公式解説

省略

B - Longest Uncommon Prefix

英小文字からなる$${N}$$文字の文字列$${S}$$が与えられ、1文字目から順にその文字とそこから$${i}$$文字後ろの文字が同じでないなら次の文字へ行くことを繰り返し、何文字目まで行けるかを1から$${N-1}$$までの$${i}$$全てについて求める問題

自分の回答

int main(){
  int N;
  string S;
  cin >> N >> S;

  for(int i = 1; i < N; i++){
    int ans = 0;
    for(int j = 0; j < N - i; j++){
      if(S[j] == S[j+i]){
        break;
      }
      else{
        ans++;
      }
    }
    printf("%d\n", ans);
  }
}

そのまま

公式解説

省略

C - abc285_brutmhyhiizp

別世界のABCでは$${10^{16}}$$問の問題が出題され、各問題は1問目から順にA,B,…,Z,AA,AB,…ZZ,AAA,…のIDが付けられている
問題のIDである$${S}$$が与えられ、それが何問目かを求める問題

自分の回答

int main(){
  string S;
  cin >> S;

  int64_t ans = 0, i = 0;
  while(S.size() != 0){
    char c = S.back();
    int64_t pn = pow(26, i);
    ans += (c - 'A' + 1) * pn;
    i++;
    S.pop_back();
  }
  printf("%ld\n", ans);
}

ようは文字の対応が違う26進数なためそれを変換する式を立てて終わり
後から見ればpnを1スタートでループの最後に26掛けて行けばよかったか

原因不明のWAで2ペナ
pnの位置にpowをそのまま入れてたのを一旦intの変数に入れたら通ったからpowの返り値がdoubleなのが影響して計算狂ったのかなぁ…
それにしてはサンプルにある最大値のは正しいからどんな時にそうなるんだろ
とりあえず今後powを使う時はdoubleとしたいとき以外はintに一回入れてからにしよう

公式解説

省略

D - Change Usernames

webサービスに$${N}$$人のユーザが存在し、$${i}$$番目のユーザが$${S_{i}}$$から$${T_{i}}$$へ名前の変更を希望している
名前の変更は1人1回、1人ずつ行い、変更を試みる時点で変更先の名前を使っている人がいる場合は変更できない場合、適切な順番を定めることで全てのユーザの名前を変更することができるかを求める問題

自分の回答

int main(){
  int N;
  cin >> N;

  vector<string> A(N);
  map<string, int> S;
  map<int, string> T;
  for(int i = 0; i < N; i++){
    string s, t;
    cin >> s >> t;
    A[i] = s;
    S[s] = i;
    T[i] = t;
  }

  vector<bool> check(N, false);
  for(int i = 0; i < N; i++){
    if(check[i] == true){
      continue;
    }
    vector<bool> nowcheck(N, false);
    string s = A[i];
    while(true){
      int j = S[s];
      if(nowcheck[j] == true){
        printf("No\n");
        return 0;
      }
      check[j] = true;
      nowcheck[j] = true;
      s = T[j];
      if(!S.count(s)){
        break;
      }
    }
  }
  printf("Yes\n");
}

どんな時に変更できないかを考えたら変更前と変更後でループする場合のため幅優先探索的な感じでループがあるかを調べる
データの管理はもっときれいにできる
checkは計算量省略のために置いたから無くても動きはする、時間制限に間に合うかわからないけど

公式解説

https://atcoder.jp/contests/abc285/editorial/5512より

そうか文字列を頂点とした有向グラフとして立てればよかったのか
やってることは同じだけどその方が管理楽だな

なるほど