えんじにあ備忘録

脱よわよわエンジニアを目指すブログ

AtCoder Beginner Contest 292 に参加しました＆反省会

競技プログラミング

AtCoder Beginner Contest 292 の振り返り

  • A、B問題を解くことができた
  • A問題：transform関数を使ったが、エラーの解消に時間がかかった
  • B問題：イエローカード、レッドカードを提示された選手を管理するsetを用意しイベントを実装する
  • C問題：愚直に問題文に沿って実装するとTLEとなった。計算量を減らす方法がわからず。
  • D問題：グラフ問題。連結と頂点・辺を結び付けられなかった

A問題

atcoder.jp

方針

  • 大文字化する方法を検索したところtransform関数を見つけた
  • サンプルに沿って引数を設定した

実装

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

int main () {
  
  std::string s;
  std::cin >> s;
  
  std::transform (s.begin(), s.end(), s.begin(), toupper);
  std::cout << s << std::endl;

  return 0;
}

当初、using namespace std;を利用してstd::を省いて実装したが、エラーとなった。
エラーの原因は、以下の記事のコメント*1によると型推論できなかったためのようだ。using namespace std;によってstd名前空間内のstd::toupperがtoupperと認識されている。
C headerのtoupperは通常の関数に対し、C++ headerのstd::toupper関数は関数テンプレートだ。関数テンプレートは型を明示的に指定しないと型推論できない。
using namespace std;と併用するならtransform (s.begin(), s.end(), s.begin(), ::toupper);と記述する必要がある。
using namespace std;を使わないことを推奨する理由に名前空間での衝突が挙げられていたが、それを痛感した。

参考

std::transform で怒られる

解説*2から

  • toupper()関数を使う

実装例

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

int main() {
    
    string S;
    cin>>S;
    
    string T = "";
    
    for(int i=0;i<S.size();i++)T += toupper(S[i]);
    
    cout<<T<<endl;
    
    return 0;
}

B問題

atcoder.jp

方針

  • イエローカード、レッドカードを提示された選手を管理するsetを用意する
  • setのinsert()とcount()を利用する

実装

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

int main () {
  
  int n, q;
  cin >> n >> q;
  set<int> yellow;
  set<int> red;

  for (int i = 0; i < q; i++) {
    int e, x;
    cin >> e >> x;

    if (e == 1) {
      if (yellow.count(x)) {
        red.insert(x);
      } else {
        yellow.insert(x);
      }
    } else if (e == 2) {
      red.insert(x);
    } else {
      if (red.count(x)) cout << "Yes" << endl;
      else cout << "No" << endl;
    }
  }
  return 0;
}

C問題

atcoder.jp

方針

  • A, B, C, D で全探索すると O(N^{4}) であり、実行時間制限に引っかかる
  • AB = X, CD = Y とし、 X を満たす A, B の個数、 Y を満たす C, D の個数を求める

解説*3から

  • AB の値を X と仮定すると、 CD の値は N - X と定まる。 A　の値を仮定すると B の値が、 C の値を仮定すると D の値が定まる
  • X, A, C の値を全探索すると O(N^{3}) になるが、 X を満たす A, B の個数、 Y を満たす C, D の個数は独立に求められるため、 O(N^{2}) となる
  • A \leq B と仮定すると、 X = AB を満たす A は A \leq \sqrt{X} を満たすため、（ C, D も同様に調べることで） O(N\sqrt{N}) で答えを求められる

実装例

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

int main() {
    
    int N;
    cin>>N;
    
    long long ans = 0;
    
    for(int i=1;i<N;i++){
        int X = i,Y = N-i;
        long long x = 0,y = 0;
        for(int j=1;j*j<=X;j++){
            if(X%j==0){
                x++;
                if(X!=j*j)x++;
            }
        }
        for(int j=1;j*j<=Y;j++){
            if(Y%j==0){
                y++;
                if(Y!=j*j)y++;
            }
        }
        ans += x * y;
    }
    
    cout<<ans<<endl;
    
    return 0;
}

*1:https://zenn.dev/log5/scraps/c3975a0f48baaa

*2:https://atcoder.jp/contests/abc292/editorial/5871

*3:https://atcoder.jp/contests/abc292/editorial/5872