AtCoder Beginner Contest 205

A. kcal

100 밀리리터마다 A킬로칼로리를 섭취하게 된다. B밀리리터를 먹었을 때 섭취한 칼로리의 양을 구하는 문제이다.

#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;

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  //freopen("input.txt","r",stdin);
  double a,b;
  cin>>a>>b;
  cout<<fixed;
  cout.precision(6);
  cout<<a*b/100;
  return 0;
}

B. Permutation Check

주어진 배열 A에 대해 (1,2,...,N)의 수열인지 확인하는 문제이다. 배열에 대해 중복된 것이 있는지만 확인하면 된다.

처음에는 전체 합이 N*(N+1)/2 공식을 이용해 체크하려고 했지만 반례가 존재했다.
N=5, 1 2 4 4 4 -> 합이 15로 둘이 같기 때문에 "Yes"가 출력된다.

#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;

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  //freopen("input.txt","r",stdin);
  int n;
  cin>>n;
  vector<int> v(n+1);
  for(int i=0;i<n;i++) {
    int a;
    cin>>a;
    v[a]=1;
  }
  for(int i=1;i<=n;i++) {
    if(!v[i]) {
      cout<<"No";
      return 0;
    }
  }
  cout<<"Yes";
  return 0;
}

C. POW

$A^C$와 $B^C$의 값을 비교하는 문제이다.

$C$가 짝수인 경우, $|A|$, $|B|$를 비교하면 되고 $C$가 홀수인 경우, 그대로 $A$, $B$를 비교하면 된다.

#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;

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  //freopen("input.txt","r",stdin);
  ll a,b,c;
  cin>>a>>b>>c;
  if(c==0) {
    cout<<"=";
    return 0;
  }
  if(c%2==0)  a=abs(a), b=abs(b);
  if(a>b) cout<<">";
  else if(a<b) cout<<"<";
  else cout<<"=";
  return 0;
}

D. Kth Excluded

1부터 $N$까지 수 중에서 주어진 배열 $A$의 원소만 빠져있는 수열이 있을때, 쿼리로 들어온 $k$에 대해 $k$번째 작은 수를 출력하는 문제이다.

먼저, $A_i$ 전에 있는 수의 개수를 $C_i$라 한다. 예를들어, 1 2 3 5에서 4앞에 있는 수는 3개(1, 2, 3)이다. $C_i=A_i-(i+1)$로 계산할 수 있다.

이제 쿼리로 $k$가 들어올 때마다 배열 $C$에 대해 lower_bound를 통해 인덱스를 구한다.

만약, 인덱스가 0이라면 $k$번째 작은 수보다 $A$배열의 원소들보다 작은 것이므로 그대로 $k$를 출력한다.

그러나, $k$의 인덱스가 0이 아니라면 $C_i$는 $A_i$ 앞의 수의 개수를 의미하므로 $A_i+(k-C_i)$로 $k$번째 작은 수를 찾을 수 있다.

예를들어, A={4,6}이고 k가 5인 경우로 가정하자. 1 2 3 5 7 8 ... 이므로 C={3,4}로 나타낼 수 있다.

$C_i<k$이므로 lower_bound로 $i$는 2를 가리키게 된다. $k$번째 작은 수는 $A_2+(5-C_2)=6+(5-4)=7$임을 알 수 있다.

왜냐하면, $C_2-k$는 $A_2$ 앞의 수 중에서 빠진 수의 개수이기 때문이다. (1 2 3 4 5 6에서 빠진 수는 4로 1개이다.)

그래서 $A_2$보다 앞의 수에서 빠진 수의 개수를 $A_2$에 더해주면 $k$번째 작은 수를 찾을 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;

typedef long long ll;

int main() {
  int n,q;
  cin>>n>>q;
  vector<ll> a(n);
  for(int i=0;i<n;i++) cin>>a[i];
  vector<ll> c(n);
  for(int i=0;i<n;i++) c[i]=a[i]-(i+1);
  while(q--) {
    ll k;
    cin>>k;
    int idx=lower_bound(c.begin(),c.end(),k)-c.begin();
    if(idx==0) {
      cout<<k<<endl;
    }
    else {
      cout<<a[idx-1]+(k-c[idx-1])<<endl;
    }
  }
  return 0;
}