2022년 3월 PS일지

타일 밟기

문제 링크

좋은 문제다. 요약하자면 배열에 존재하는 각 등차수열들의 원소의 합 중 최대를 구하는 것이다.

$N\le 3000$이고 원소들은 $10^6$ 이하이다.

풀이 & 코드

Solution 1

DP + 이진탐색

#include <bits/stdc++.h>
using namespace std; using ll = long long;
#define REP(i,a,b) for (auto i = (a); i <= (b); ++i)
#define Mup(x,y) x = max(x,y)

const int N = 3003;
int n, a[N];
ll dp[N][N];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    REP(i,1,n) cin >> a[i];
    ll answer = 0;
    REP(i,1,n) REP(j,1,i-1) {
        dp[i][j] = a[i]+a[j];
        int k = lower_bound(a+1,a+j,2*a[j]-a[i])-a;
        if (a[i]+a[k] != 2*a[j]) continue;
        Mup(dp[i][j],dp[j][k]+a[i]);
        Mup(answer,dp[j][k]+a[i]);
    }
    cout << answer;
}

Solution 2

조화 수열의 합

#include <bits/stdc++.h>
using namespace std; using ll = long long;
#define REP(i,a,b) for (auto i = (a); i <= (b); ++i)

const int N = 3003, X = 1000003;
int n;
bool e[X];
ll x, a[N];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    REP(i,1,n) cin >> a[i], e[a[i]] = 1;
    REP(i,1,n) REP(j,i+1,n) {
        ll d = a[j]-a[i], v = a[i], w = 0, c = 0;
        while (v < X and e[v]) w += v, ++c, v += d;
        if (c > 2) x = max(x,w);
    }
    cout << x;
}

Perimeter

문제 링크

미루다가 4월 24일에 마저 작성중인데... 무슨 문제였는지 기억이 안 난다 ㅋㅋ

대충 전체를 감싸는 둘레를 구하는 거였던 것 같다.

특징은 Data structure를 잘 활용할 수 있어야 한다는 것이다.

풀이

hay 주변만 탐색하도록 짜면 시간 안에 돌아갈 것이므로, hay를 set에 넣고 잘 확인하면서 dfs를 해주면 된다.

코드

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>;
#define REP(i,a,b) for (auto i = (a); i <= (b); ++i)

const int N = 5e4+3;
int n, answer;
set<ii> hay;
map<ii,bool> visited;

bool alone(int r, int c) {
    REP(i,-1,+1) REP(j,-1,+1) {
        if (hay.count({r+i,c+j})) return false;
    }
    return true;
}

void dfs(int r, int c) {
    if (hay.count({r,c})) answer++;
    else {
        if (alone(r,c) or visited[{r,c}]) return;
        visited[{r,c}] = true;
        dfs(r-1,c),dfs(r+1,c),dfs(r,c-1),dfs(r,c+1);
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    REP(i,1,n) {
        int r, c; cin >> r >> c;
        hay.insert({r,c});
    }
    dfs(hay.begin()->first-1,hay.begin()->second);
    cout << answer;
}

Flowerpot

문제 링크

그냥 쉽고 왜 플래인지 납득 못하겠다. 골3 정도가 적당하다고 생각한다.

풀이 & 코드

슬라이딩 윈도우 + 멀티셋으로 풀린다.

#include <bits/stdc++.h>
using namespace std;

const int X = 1e6+3;
int n, d;
multiset<int> ms;
vector<int> drops[X];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> d;
    for (int i = 1; i <= n; ++i) {
        int x, y; cin >> x >> y;
        drops[x].push_back(y);
    }
    int a = 0, b = -1, answer = 1e9;
    while (b < X-1) {
        if (not empty(ms) and *rbegin(ms) - *begin(ms) >= d) {
            answer = min(answer,b-a);
            for (auto drop : drops[a]) ms.erase(ms.find(drop));
            a++;
        } else {
            b++;
            for (auto drop : drops[b]) ms.insert(drop);
        }
    }
    if (answer == 1e9) cout << -1;
    else cout << answer;
}

이항 계수 4

문제 링크

풀이 & 코드..

윌슨 정리를 변형하면 된다.

소수 $p$를 인수로 갖는 수들만 묶어내는 과정을 재귀적으로 하면 된다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll n, k, p;
template <typename...Ts> ll mul(Ts... xs) {return (ll(xs)*...)%p;}
void Mul(ll &x, ll y) {x = mul(x,y);}
ll my_pow(ll x, ll e) {
    ll r = 1;
    while (e > 0) {
        if (e%2) r = mul(r,x);
        e /= 2, x = mul(x,x);
    }
    return r;
}
ll inv(ll x) {return my_pow(x,p-2);}
ll fac[2000] {1};
pair<ll,ll> fact(ll n) {
    ll f = 1, e = 0;
    while (n > 0) {
        if ((n/p)%2) Mul(f,p-1);
        e += n/p;
        if (n%p) Mul(f,fac[n%p]);
        n /= p;
    }
    return {f,e};
}
ll C(ll n, ll k) {
    ll F = 1, E = 0, f, e;
    tie(f,e) = fact(n); Mul(F,f), E += e;
    tie(f,e) = fact(k); Mul(F,inv(f)), E -= e;
    tie(f,e) = fact(n-k); Mul(F,inv(f)), E -= e;
    return E > 0 ? F : 0;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> k >> p;
    for (int i = 1; i < p; ++i)
    	fac[i] = mul(fac[i-1],i);
    cout << C(n,k);
}