Caddi Programming Contest 2021 (AtCoder Beginner Contest 193)

A. Discount

A엔에서 B엔으로 할인할 때의 할인율을 구하는 문제

#include <iostream>
#include <cmath>
#define endl '\n'
#define ll long long
using namespace std;
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    double a, b;
    cin>>a>>b;
    cout<<fixed;
    cout.precision(10);
    cout<<(a-b)*100/a;
    return 0;
}

B. Play Snuke

0.5, 1.5, 2.5, ... 분 마다 Snuke가 1씩 사라지므로 Snuke의 재고가 $A_i$보다 많으면 구매할 수 있다.

#include <iostream>
#include <algorithm>
#define endl '\n'
#define ll long long
using namespace std;
 
const ll INF=1e10;
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int N;
    cin>>N;
    ll ans=INF;
    for(int i=0;i<N;i++) {
        ll a,p,x;
        cin>>a>>p>>x;
        if(a<x) ans=min(ans,p);
    }
    ans=ans==INF ? -1 : ans;
    cout<<ans;
    return 0;
}

C. Unexpressed

$1 ≤ N ≤ 10^{10}$의 범위를 갖는 $N$에 대해 1부터 $N$까지 정수 중에서 $a^b (a,b ≥ 2)$의 형태를 갖지 않는 수의 개수를 계산하는 문제

에라토스테네스의 체를 구하는 방식을 거듭제곱을 계산하는 방식으로 변형하여 해결

메모리가 1024MB이어서 $N$만큼의 배열을 잡으면 MLE를 받게 되므로 set을 사용하여 거듭제곱의 수를 계산하도록 했다.

#include <iostream>
#include <set>
#include <cmath>
#define endl '\n'
#define ll long long
using namespace std;
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll N;
    cin>>N;
    set<ll> s;
    for(ll i=2;i<=sqrt(N);i++) {
        for(ll j=i*i;j<=N;j*=i) s.insert(j);
    }
    cout<<N-s.size();
    return 0;
}

D. Poker

문제를 풀지 못해서 editorial의 설명을 가져왔다.

먼저, 앞면이 아닌 카드의 수는 $9K-8$개이다.

Takahashi가 이길 수 있는 확률 = (Takahashi가 이길 수 있는 카드들의 조합)/(전체 카드 조합)

• 전체 카드 조합은 $(9K-8)\times (9K-9)$이다.

이제 Takahashi가 이길 수 있는 카드들만 구하면 된다. 가능한 카드 조합을 완전탐색하여 찾아낸다.

만약, i번 카드가 뒤집혀 있는 경우의 수를 $C_i$라 하자. Takahashi가 x를 가져가고, Aoki가 y를 가져갔을 때, 조합의 수는 다음과 같다.

• $C_x\times C_y \space(x ≠ y)$
• $C_x\times (C_x-1) \space(x = y)$

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric> // accumulate header
#define endl '\n';
#define ll long long // 카드 수가 많기 때문에 long long 필요
using namespace std;

ll score(string s) {
   vector<ll> cnt(10,0);
   for(ll i=1;i<=9;i++) cnt[i]=i;
   for(char i : s) cnt[i-'0']*=10;
   return accumulate(cnt.begin(),cnt.end(),0);
}

int main() {
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
   //freopen("input.txt","r",stdin);
   int K;
   cin>>K;
   string S, T;
   cin>>S>>T;
   vector<ll> cnt(10,K);
   for(char s : S+T) cnt[s-'0']--;
   ll win=0;
   for(ll x=1;x<=9;x++) {
      for(ll y=1;y<=9;y++) {
         S.back()='0'+x;
         T.back()='0'+y;
         if(score(S)<=score(T)) continue;
         win+=cnt[x]*(cnt[y]-(x==y));
      }
   }
   const ll rem=9*K-8;
   cout<<double(win)/rem/(rem-1)<<endl;
   return 0;
}