AtCoder Beginner Contest 215

A. Your First Judge

입력 S가 “Hello,World!”와 같은지 판단하는 문제

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF=1e10+1;
const ll MOD=1e9+7;

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  //freopen("input.txt","r",stdin);
  string s;
  cin>>s;
  if(s=="Hello,World!") cout<<"AC";
  else cout<<"WA";
  return 0;
}

---

B. log2(N)

어떤 정수 $N$이 주어졌을 때, $2^k≤N$를 만족하는 $k$중 가장 큰 수를 구하는 문제

N의 범위가 $1≤N≤10^{18}$이므로 unsigned long long으로 선언한 뒤에 bit shift하고 완전탐색해주면 된다.

$N=10^{18}$인 경우 $2^{59}$이 최대 숫자이므로 59부터 탐색을 시작하면 된다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF=1e10+1;
const ll MOD=1e9+7;

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  //freopen("input.txt","r",stdin);
  ull n;
  cin>>n;
  if(n==1) {
    cout<<0; return 0;
  }
  for(int i=59;i>=0;i--) {
    ull a=2;
    if((a<<i)<=n) {
      cout<<i+1; return 0;
    }
  }
  return 0;
}

---

C. One More aab aba baa

입력 문자열 S에 대해 k번째 lexicographically smallest string을 찾는 문제이다.

간단하게 S를 정렬하고 permutataion을 돌면서 k번째 문자열을 찾으면 된다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <map>
#define endl '\n'
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF=1e10+1;
const ll MOD=1e9+7;

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  //freopen("input.txt","r",stdin);
  string s; int n;
  cin>>s>>n;
  int count=0;
  if(n==0) {
    cout<<s; return 0;
  }
  sort(s.begin(),s.end());
  do{
    count++;
    if(count==n) {
      cout<<s; return 0;
    }
  }while(next_permutation(s.begin(),s.end()));
  return 0;
}

---

D. Coprime 2

어떤 배열 $A={A_1, A_2, …, A_N}$이 있을 때 $A$의 모든 원소와의 최대공약수(GCD)가 1이 되게 하는 1과 $M$사이의 $k$를 모두 찾는 문제이다.

$N$과 $M$의 범위는 $1 ≤ N,M ≤ 10^5$이므로 $O(NM)$의 시간복잡도를 가져서는 안된다.

이 문제는 $A_i$의 모든 약수를 $O(\sqrt{A_i})$로 찾게되면 문제를 $O(N\sqrt{maxA})$로 해결할 수 있다. ($1≤A_i≤10^5$)

모든 약수를 구하고 에라토스테네스의 체(Eratosthenes’ sieve)를 이용해 GCD가 1이 되지 않게 하는 약수의 배수를 모두 제거한다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF=1e10+1;
const ll MOD=1e9+7;

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  //freopen("input.txt","r",stdin);
  int n,m;
  cin>>n>>m;
  vector<int> a, v(100001,1);
  v[0]=0;
  for(int i=0;i<n;i++) {
    int x; cin>>x;
    for(int j=2;j*j<=x;j++) { // 약수를 sqrt(x)에 구해야한다
      while(x%j==0) {
        x/=j;
        a.push_back(j);
      }
    }
    if(x!=1) a.push_back(x); // GCD(x,x)=x
  }
    
  for(auto it : a) {
    if(v[it]) {
      for(int j=it;j<=100000;j+=it) v[j]=0;
    }
  }
    
  vector<int> ans;
  for(int i=1;i<=m;i++) {
    if(v[i]) ans.push_back(i);
  }

  cout<<ans.size()<<endl;
  for(auto it : ans) cout<<it<<endl;
  return 0;
}