AtCoder Beginner Contest 271

KYOCERA Programming Contest 2022（AtCoder Beginner Contest 271） - AtCoder

結果

A - 484558:AC(21:20)(1ペナ)
B - Maintain Multiple Sequences:AC(36:22)(1ペナ)
C - Manga:WA

A - 484558

0以上255以下の整数が与えられ、それを0埋め2桁の16進数に変換する問題
ただしABCDEFは大文字であること

自分の回答

int main() {
  int N;
  cin >> N;
 
  char C2, C1;

  if(N % 16 < 10){
    C1 = N % 16 + 48;
  }
  else{
    C1 = N % 16 - 10 + 'A';
  }

  N / = 16;

  if(N % 16 < 10){
    C2 = N % 16 + 48;
  }
  else{
    C2 = N % 16 - 10 + 'A';
  }
 
  printf("%c%c\n", C2, C1);
}

16進数の定義から各桁を求め出力
ASCIIコードの数字が0から始まると思い込んでいたため1ペナ
今見ればだいぶ回りくどいことしてるな

公式解説

int main() {
  int N;
  scanf("%d", &N);
  printf("%02X", N);
}

https://atcoder.jp/contests/abc271/editorial/4946より

%xだと小文字になるからダメだなって思ったけど%Xで大文字にできるのか…

B - Maintain Multiple Sequences

数列が$${N}$$個あり、$${i(1\leqq i\leqq N)}$$番目の数列は$${L_{i}}$$項からなり第$${j(1\leqq j\leqq L_{i})}$$項は$${a_{i,j}}$$である
このとき$${Q}$$個のクエリから、$${s_{k},t_{k}(1\leqq k\leqq Q)}$$が与えられ$${a_{s_{k},t_{k}}}$$を求める問題

自分の回答

int main() {
  int N, Q;
  cin >> N >> Q;
  vector<vector<int>> seq(N, vector<int>(0));
  for(int i = 0; i < N; i++){
    int L;
    cin >> L;
    for(int j = 0; j < L; j++){
      int X;
      cin >> X;
      seq[i].push_back(X);
    }
  }
  for(int i = 0; i < Q; i++){
    int s, t;
    cin >> s >> t;
    printf("%d\n", seq[s-1][t-1]);
  }
}

横の要素数が不定の二次元配列なためそのまま入れて求めるだけ

seqを定義した時に桁を1つ間違えて1ペナ
桁数を直したらCEとなったためpush_backに切り替え

公式解説

基本同じだったため省略

C - Manga

漫画を$${N}$$巻持っており$${i}$$番目は$${a_{i}}$$巻である
読み始める前に、持っている中から2冊を選んで売り好きな巻を1冊買う操作を0回以上行える
1巻から順番に読んでいき、次の巻が無くなるまで読む
この時最大で何巻まで読むことができるか求める問題

自分の回答

int main() {
  int N;
  cin >> N;
  vector<int> S(N);
  for(int i = 0; i < N; i++){
    cin >> S[i];
  }
  sort(S.begin(), S.end());
 
  deque<int> sunuke;
  for(int i = 0; i < N; i++){
    sunuke.push_back(S[i]);
  }

  int ans = 0;
  while(!sunuke.empty()){
    if(sunuke.front() < ans + 1){
      int count = 0;
      while(sunuke.front() < ans + 1){
        sunuke.push_back(sunuke.front());
        sunuke.pop_front();
        count++;
        if(count == sunuke.size()){
          ans += sunuke.size() / 2;
          goto OUT;
        }
      }
    }
    else if(sunuke.front() == ans + 1){
      ans++;
      sunuke.pop_front();
    }
    else{
      if(sunuke.size() >= 2){
        sunuke.pop_back();
        sunuke.pop_back();
        ans++;
      }
      else{
        break;
      }
    }
  }
  OUT:;
  printf("%d\n",ans);
}

買える数で考えるか操作を繰り返すかで悩んだが愚直に行ってみることにした

持っていない巻があったら巻数の大きい順で売り、必要な巻を買う
重複分は優先して売る
この操作を愚直に繰り返していく方向で書いてみたが1つだけWAが出た
何か引っかからないパターンを見逃してるんだろうけどわからなかった

公式解説

int main() {
  int N;
  cin >> N;
  vector<bool> set(N + 2);
  for (int i = 0;i < N;++ i) {
    int a;
    cin >> a;
    set[min(N + 1, a)] = true;
  }
  for (int read = 1;N >= 0;++ read) {
    N -= set[read] ? 1 : 2; // その巻を読むために使う本の冊数
    if (N < 0) cout << read - 1 << endl; // 本が無くなったら、無くなる直前の冊数を出力
  }
}

https://atcoder.jp/contests/abc271/editorial/4947より

まずどの巻を持っているかを確認、この時巻数が$${N}$$を越えている場合はどうあがいても読めないため$${N+1}$$とする
そして1巻目から順番に持っていたら$${N-1}$$、持っていなかったら$${N-2}$$をしていき$${N}$$が負となったらその時点のread-1を出力

持っている本の数で考えるのか
持っているなら1冊消費、持っていなかったら2冊消費と考えれば1度何巻を持っているかを取ったら何巻があるかはいらない情報なのか

なるほど