Codeforces Round #716 (Div. 2)

https://codeforces.com/contest/1514

Dashboard - Codeforces Round #716 (Div. 2) - Codeforces

오랜만에 버춸 돌았다. 퍼포먼스가 1980쯤 나와서 기분이 좋다.

---

A. perfectly Implerfect Array

Tag : math

 

풀이

길이가 3이상인 답안에서 제곱수가 되는 것들을 모두 제외해서 그 길이를 1 또는 2로 만들 수 있다.

 

전체코드

#include "bits/stdc++.h"
#define endl '\n'
 
using namespace std;
using ll = long long;
 
 
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt", "r", stdin);
 
    int tc = 1;
    cin >> tc;
    while(tc--) {
        int n; cin >> n;
        vector<int> v(n);
        int f = 0;
        for(auto &i : v) {
            cin >> i;
            int sq = sqrt(i);
            if(sq * sq != i) f = 1;
        }
        for(int i=0; i<n; i++) for(int j=i+1; j<n; j++) {
            int x = v[i] * v[j];
            int sq = sqrt(x);
            if(sq * sq != x) f = 1;
        }
        if(f) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

---

B. AND 0, Sum Big

Tag : math

 

풀이

최대가 되려면 모든 비트가 한번씩만 제외돼야한다. 

제외되는 것을 비트마다 고르면 답은 \( N^K \)다.

 

전체코드

#include "bits/stdc++.h"
#define endl '\n'
 
using namespace std;
using ll = long long;
 
void solve() {
    int n, k; cin >> n >> k;
    const ll MOD = 1e9 + 7;
    ll ans = 1;
    for(int i=0; i<k; i++) ans = ans * n % MOD;
    cout << ans << endl;
}
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt", "r", stdin);
 
    int tc = 1;
    cin >> tc;
    while(tc--) {
        solve();
    }
}

---

C. Product 1 Modulo N

Tag : number theory

 

풀이

product % N = 1이면 gcd(product % N, N) = 1이라는 것과 같다.

gcd(product % N, N) = 1이면 gcd(product, N) = 1이다. (gcd(a,b) = gcd(b, a % b))

서로소여야한다는 것이다. 그래서 서로소를 모두 곱해보고 그것이 1이 아니라면 그거 하나를 제외하면 된다.

꽤 어려웠던 것 같다.

 

전체코드

#include "bits/stdc++.h"
#define endl '\n'
 
using namespace std;
using ll = long long;
 
ll power(ll a, ll b, ll m) {
    if(b == 0) return 1;
    ll t = power(a, b / 2, m);
    t = t * t % m;
    if(b % 2) return t * a % m;
    else return t;
}
 
ll n;
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt", "r", stdin);
 
    cin >> n;
    vector<int> ans;
    ll p = 1;
    for(int i=1; i<n; i++) {
        if(gcd(i, n) == 1) ans.push_back(i), p = p * i % n;
    }
    if(p > 1 and find(ans.begin(), ans.end(), p) != ans.end()) ans.erase(find(ans.begin(), ans.end(), p));
    cout << ans.size() << endl;
    for(auto &i : ans) cout << i << ' ';
}

---

D. Cut and Stick

Tag : random

 

풀이

반절을 넘기는 것은 랜덤을 통해 고를 수 있다. 

반절을 넘기는 것이 있다면 랜덤으로 골랐을 때 그것이 틀릴 확률이 1/2보다 작다.

그래서 이것을 적당히 50번정도 돌리면 틀릴 확률이 (1/2)^50정도로 매우 작다.

(결정론적인 풀이로는 mo's가 있다)

반절을 넘는 것을 x, 아닌 것을 y라하면 일단 y와 x개 중 y + 1를 한 그룹으로 묶는다.

그리고 남은 것은 하나씩만 묶는다. 이보다 좋은 전략은 없을 것 같다.

 

전체코드

#include "bits/stdc++.h"
#define endl '\n'
 
using namespace std;
using ll = long long;
 
struct RAND {
    random_device rg;
    mt19937 rd;
    RAND() { rd.seed(rg()); }
    int nxt(int l = 0, int r = 32767) { return uniform_int_distribution<int>(l, r)(rd); }
} rnd;
 
int n, q;
int a[303030];
vector<vector<int>> v(303030);
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt", "r", stdin);
 
    cin >> n >> q;
    for(int i=1; i<=n; i++) {
        cin >> a[i];
        v[a[i]].push_back(i);
    }
    while(q--) {
        int l, r; cin >> l >> r;
        int qry = 1;
        for(int t=0; t<50; t++) {
            int x = a[rnd.nxt(l, r)];
            int y = upper_bound(v[x].begin(), v[x].end(), r) - lower_bound(v[x].begin(), v[x].end(), l);
            qry = max({qry, 2 * y - (r - l + 1)});
        }
        cout << qry << endl;
    }
}