20230811 업다운 랜디

s#100.. !solved_by:p_jun *P3

30분 3문제

 

P3 13504 XOR 합 패스

그리디, DP, 세그 트리 등 고민 했는데 쉽지 않다

트라이가 정해인데 모르는 알고리즘이다

공부하고 추후 작성하자

 

P4 20532 정점 간 통신 네트워크 - 6분 3초

dfs를 잘 돌리면서 개수를 세주면 된다

약수의 개수는 많지 않으니 그냥 다 세주자

중복된 수는 배수, 약수에서 공통으로 세지니 빼줘야 한다

int를 넘을 수 있다는 것에 유의하자

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <deque>
#include<set>
#include<map>
#include<cassert>
using namespace std;
using ll = long long;
#define MOD 1000000007
const ll INF = 987654321;
const int MX = 100005;

vector<int> f[MX];
vector<int> r[MX];
ll arr[MX];
ll cnt[MX];
ll b[MX];
ll ans;

void dfs(int pos) {
    ans += b[arr[pos]] - cnt[arr[pos]];
    for (auto& x : f[arr[pos]]) {
        b[x]++;
        ans += cnt[x];
    }
    cnt[arr[pos]]++;
    for (auto& x : r[pos]) dfs(x);
    for (auto& x : f[arr[pos]]) b[x]--;
    cnt[arr[pos]]--;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
    int n; cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i + 1];
    for (int i = 1; i < n; i++) {
        int k;  cin >> k;
        r[k].push_back(i + 1);
    }
    for (int i = 1; i < MX; i++) for (int j = i; j < MX; j += i) f[j].push_back(i);
    dfs(1);
    cout << ans << '\n';
}

P3 11872 님 게임 나누기 -14분 20초

딱 보니 스프라드-그런디 정리 문제다

동가스가 푸는 걸 보고 훔쳐 풀어 다행히 아는 알고리즘이다.

그런디 수를 열심히 구해보면 아래와 같다

1, 2, 4, 3, 5, 6, 8, 7...
3과 4에서 뒤집힌 수로 인해 4마다 그런디 수에 변화가 있다

xor 해주면 답을 구할 수 있다

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <deque>
#include<set>
#include<map>
#include<cassert>
using namespace std;
using ll = long long;
#define MOD 1000000007
const ll INF = 987654321;
const int MX = 100005;

map<string, int> m;

int main() {
    ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
    int n; cin >> n;
    int g = 0;
    for (int i = 0; i < n; i++) {
        int k; cin >> k;
        if (k % 4 == 3) k++;
        else if (k % 4 == 0) k--;
        g ^= k;
    }
    cout << (g ? "koosaga" : "cubelover") << '\n';
}