AtCoder Beginner Contest 263

2022年8月12日 15:24

結果

A - Full House:AC(30:20)(3ペナ)
B - Ancestor:AC(64:00)(1ペナ)
C - Monotonically Increasing:WA

A - Full House

1~13の整数が5つ与えられ、それがフルハウスかを判定する問題

自分の回答

int main() {
  int n;
  map<int, int> cou;
  set<int> type;

  for(int i = 0; i < 5; i++){
    cin >> n;
    type.insert(n);
    if(cou.count(n)){
      cou[n]++;
    }
    else{
      cou[n] = 1;
    }
  }

    if(cou[*begin(type)] == 2 && cou[*rbegin(type)] == 3){
      printf("Yes\n");
    }
    else if(cou[*begin(type)] == 3 && cou[*rbegin(type)] == 2){
      printf("Yes\n");
    }
    else{
      printf("No\n");
    }
  }

シンプルに同じ数字が出てきた回数が2回と3回ならばYesを出力して違うならNoと出力する
しかしsetとmap両方使ったせいで割と入り組んでる・・・
もっと簡単にできたはず
あとコンテスト開始直前にバタバタしてて大慌てで書いたためシンプルなコードミスでWA3回とCE3回出した、落ち着いてコードテストは通そう

公式解説

int main(){
    vector<int> a(5);
    for(int i = 0; i < 5; i++) cin >> a[i];
    sort(a.begin(), a.end());
    if((a[0] == a[2] and a[3] == a[4]) or (a[0] == a[1] and a[2] == a[4])) cout << "Yes" << endl;
    else cout << "No" << endl;
}

https://atcoder.jp/contests/abc263/editorial/4548より

そうかソートしちゃえば(a[0]=a[2]かつa[3]=a[4])か(a[0]=a[1]かつa[2]=a[4])でよかったのか
なるほど

B - Ancestor

$${N}$$人の人とその人の親$${P_{i}}$$が与えられ、人1が人$${N}$$の何代前かを求める問題

自分の回答

int main() {
  int n;
  cin >> n;
  int now = n - 1;
  vector<int> h(n, 0);

  for(int i = 1; i < n; i++){
    int p;
    cin >> p;
    p--;
    h[i] = p;
  }
 
  int count = 0;
  while(true){
    if(now == 0){
      break;
    }
    else{
      now = h[now];
      count++;
    }
  }
  printf("%d\n", count);
}

$${P_{i} < i}$$が保証されていて無限ループになるようなことがないためシンプルに人$${N}$$から遡っていく
vectorの順番に対応させるため親番号をデクリメントしておいてh[n-1]、つまり人$${N}$$から遡って親番号が0になるまでの回数をカウント
コードの出来はともかくやり方はこれが最適解のはず
なお、1回whileの脱出をnow=1にしたために人$${N}$$の親が1の時h[n-1]=0、h[0]=0となって無限ループしてしまいTLEを出した

公式解説

int main() {
  int n;
  cin>>n;
  vector<int> a(n);
  for(int i=1;i<n;i++){
    cin>>a[i];
    a[i]--;
  }
  vector<int> dp(n);
  for(int i=1;i<n;i++){
    dp[i]=dp[a[i]]+1;
  }
  cout<<dp[n-1]<<endl;
}

https://atcoder.jp/contests/abc263/editorial/4540より

動的計画法で人2から$${N}$$までを全員求めてるのか
このやり方なら似たような他の問題にも応用できそう
なるほど

C - Monotonically Increasing

1から$${M}$$までの整数を使った長さ$${N}$$の数列のうち
$${A_{1} < A_{2} < …… < A_{N}}$$となるものを辞書順で全て出力する問題

自分の回答

いい方法は思いつかなかったため愚直にカウントアップしていく方向で書いてみるが処理の条件などを詰め切れず時間切れ
コンテスト終了後にACを出せたのがこれ

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> seq(N);
  for(int i = 0; i < N; i++){
    seq[i] = i + 1;
  }
 
  while(seq[0] != M - N + 2){
    for(int x : seq){
      printf("%d ", x);
    }
    printf("\n");
 
    seq[N - 1]++;
    for(int i = N - 1; i > 0; i--){
      if(seq[i] == M - N + i + 2){
        seq[i] = 0;
        seq[i - 1]++;
      }
    }
    for(int i = 0; i < N - 1; i++){
      if(seq[i] >= seq[i + 1]){
        seq[i + 1] = seq[i] + 1;
      }
    }
  }
}

まず[1,2,……,N]の配列seqを作り
whileで{
・配列を出力
・seq[N-1]をインクリメント
・数列の条件からseq[i]は$${M-N+i+1}$$以下のため、それを超えていたらseq[i-1]をインクリメント、つまり繰り上がりの処理をseq[N-1]からseq[1]までする
・seq[i]$${\geqq}$$seq[i+1]ならばseq[i+1]=seq[i]+1をして条件に合わない数列をスキップ
}
条件に合う数列の最大値が[M-N+1,M-N,……,M-2,M-1,M]なため、その次の数列はwhileの処理を通すと[M-N+2,M-N+1,……,M+1]
よってwhileの終了条件をseq[0]が$${M-N+2}$$となった時に設定

配列の辞書順並び替えと言えばnext_permutationで行けそうな感じがするけど、これはあくまで配列にある要素のみでやるから一工夫必要そうでそこが思いつかなかった

公式解説

int main() {
  int n,m;
  cin>>n>>m;
  vector<int> a;
  for(int i=0;i<n;i++) a.push_back(0);
  for(int i=0;i<m-n;i++) a.push_back(1);
  do{
    for(int i=0;i<m;i++){
      if(a[i]==0) cout<<i+1<<" ";
    }
    cout<<endl;
  }while(next_permutation(a.begin(),a.end()));
}

https://atcoder.jp/contests/abc263/editorial/4541より

0が$${N}$$個、1が$${M}$$個の配列を作って0の位置を読めばnext_permutationで行けるのか！
いやーその方法は思いつかない

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