2022년 4월 PS 일지 ★

LCM

문제 링크

개인적으로 오랫동안 고민했던 문제이다.

거의 4번? 정도에 거쳐서 풀다 미뤘다를 반복했다.

풀이

$\mathrm{lcm}(x,y)=xy/\gcd(x,y)$인데, 분모가 유동적이니까 $\gcd(x,y)$를 결정했을 때 $xy$의 최솟값을 각각 구해주는 방식으로 접근하면 된다. 손으로는 자연스러운 접근인데, 이상하게 코드로 짤 생각을 못했다.

$\gcd(a+n,b+n)|(b-a)(\mathrm{wlog}\ a\le b)$이라는 사실을 이용해 $b-a$의 약수들만 훑어주면 된다.

코드

$x|(b-a)$ 검사를 빼먹었는데 예제가 돌아가서 눈치를 못 채고 있었다.

그리고 $a=b$인 경우도 빼먹고 있었다.

점점 실력이 떨어지는 느낌이다 ㅋㅋㅋ 이런건 좀 그만 실수해!!

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

ll a, b, M = 9e18, N = 9e18;

void f(ll k) {
    ll n = min(-a%k+k,-b%k+k), m = lcm(a+n,b+n);
    if (M > m or (M == m and N > n))
        M = m, N = n;
}

int main() {
    cin >> a >> b;
    if (a > b) swap(a,b);
    if (a == b) cout << 1;
    else {
        for (ll x = 1; x*x <= b-a; ++x)
            if ((b-a)%x == 0) f(x), f((b-a)/x);
        cout << N;
    }
}

MEX

문제 링크

잘 만든 문제인 듯.

풀이.

Harmonic Lemma를 이용하면 된다.

들어온 $a_n$을 erase-unique 해주면, 순증가 수열이 된다.

그런 상태에서 각 $a_i$의 배수를 훑는 방식으로 진행하면,

$\displaystyle \mathcal O\left (\sum_{i=1}^n \left \lfloor \frac X {a_i}\right \rfloor \right )\le \mathcal O\left (\sum_{i=1}^n \left \lfloor \frac X {i}\right \rfloor \right )= \mathcal O(n\log n)$

코드.

$\mathrm{exists}[y]$로 존재성을 확인되면 $s[x\times y]$에 색칠해주는 식으로 풀면 된다.

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for (auto i = (a); i <= (b); ++i)
#define ZIP(x) (x).erase(unique((x).begin(),(x).end()),(x).end())

const int N = 2e6+4, X = 2e6+4;
int n;
vector<int> a;
bool exists[X], s[X];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n, a.resize(n);
    for (int &e : a) {
        cin >> e, exists[e] = true;
        if (e == 0) s[0] = 1;
    }
    sort(begin(a),end(a)), ZIP(a);
    for (int e : a) if (e) {
        for (int x = e, y = 1; x < X; x += e, y++) {
            if (exists[y]) s[x] = 1;
        }
    }
    REP(i,0,X) if (!s[i]) {
        cout << i;
        break;
    }
}

Endless Knight

문제 링크

미친듯이 디버깅이 오래 걸렸다. cherub8128님 덕분에 디버깅에 성공할 수 있었다...!

문제는 get_val 함수에 있었는데, 도착점에 도달할 수 없는 점들 중 h, w 보다 커서 가지 못하는 경우들이 제외되지 않았던 것이 문제였다.

사소한 문제인데 보이지 않았던 만큼 중요한 디버깅 사안이다.

1. 모듈화된 각각의 함수에 대해 들어오는 인자들을 검사하자. 즉, 정의역에 해당하는지 assert문으로 확인하자는 것이다. 그랬다면 이 문제에서 calc(x,y)에서 x >= 0 and y >= 0라는 조건에 의해 일찍 디버깅을 성공할 수 있었을 것이다.
2. 함수가 아니더라도 습관적으로 범위를 확인해주자.

풀이..

나이트의 이동경로를 따내면 평행사변형 모양이 되는걸 알 수 있다.

이 평행사변형을 잘 찌그러뜨리면 직사각형 모양이 되어서, 결국 고등학교 확통 시간에 배우는 장애물이 있는 격자상의 최단경로 문제로 바뀐다.

장애물이 적으므로 직관적으로 포함배제를 사용하면 된다는 것을 알 수 있고,

큰 수의 조합을 사용해야 된다는 점에서 이항 계수 4 코드가 필요하다는 것을 알 수 있다.

코드..

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define REP(i,a,b) for (auto i = (a); i <= (b); ++i)
#define size(x) int((x).size())
const ll MOD = 1e4+7, P = MOD;
template <typename...Ts> ll add(Ts... xs) {ll x = (ll(xs)+...); return x >= MOD ? x-MOD : x;}
template <typename...Ts> ll mul(Ts... xs) {return (ll(xs)*...)%MOD;}
void Add(ll &x, ll y) {x = add(x,y);}
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[P] = {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 calc(ll x, ll y) {
    assert(x >= 0 and y >= 0);
    ll F = 1, E = 0, f, e;
    tie(f,e) = fact(x+y); Mul(F,f), E += e;
    tie(f,e) = fact(x); Mul(F,inv(f)), E -= e;
    tie(f,e) = fact(y); Mul(F,inv(f)), E -= e;
    if (E) return 0;
    return F;
}

int h, w;
vector<ii> rock;

bool can_go(int a, int b) {return (2*a-b+2)%3 == 0 and (2*b-a+2)%3 == 0 and (2*a-b+2)/3 >= 1 and (2*b-a+2)/3 >= 1;}
ii change(int a, int b) {return {(2*a-b+2)/3,(2*b-a+2)/3};}

ll get_val(int mask) {
    int pf = 1, ps = 1;
    ll ret = 1;
    REP(i,0,size(rock)-1) if (mask>>i&1) {
        if (ps > rock[i].second) return 0;
        Mul(ret,calc(rock[i].first-pf,rock[i].second-ps));
        tie(pf,ps) = rock[i];
    }
    if (pf > h or ps > w) return 0;
    return mul(ret,calc(h-pf,w-ps));
}

ll solve() {
    ll ret = 0;
    REP(i,0,(1<<size(rock))-1) {
        ll v = get_val(i);
        if (__builtin_popcount(i)%2) {
            if (v) Add(ret,P-v);
        } else Add(ret,v);
    }
    return ret;
}

void solution(int tc) {
    rock.clear();
    int r; cin >> h >> w >> r;
    REP(i,1,r) {
        int a, b; cin >> a >> b;
        if (can_go(a,b)) rock.push_back(change(a,b));
    }
    if (can_go(h,w)) {
        tie(h,w) = change(h,w);
        sort(rock.begin(),rock.end());
        cout << "Case #" << tc << ": " << solve() << '\n';
    } else cout << "Case #" << tc << ": 0\n";
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int tc; cin >> tc;
    REP(i,1,P-1) fac[i] = mul(fac[i-1],i);
    REP(t,1,tc) solution(t);
}

하늘에서 떨어지는 1, 2, ..., R-L+1개의 별

문제 링크

코포 D 풀다 이거 쓰는 것 같길래 급하게 검색해가지고, 직접 아이디어를 떠올리는 경험은 못 해서 아쉽다.

풀이...

누적합을 잘 응용하면 된다.

그보다... 다른 풀이들이 탐스러워서 그쪽 방향으로도 접근해보려 한다.

따로 글을 파도록 하겠다.

코드...

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>;
using ll = long long; using ld = long double;
#define _(x) const x&
#define REP(i,a,b) for (auto i = (a); i <= (b); ++i)
#define ZIP(x) (x).erase(unique((x).begin(),(x).end()),(x).end())
#define MP make_pair
#define mup(x,y) x = min(x,y)
#define Mup(x,y) x = max(x,y)
#define size(x) int((x).size())

template <typename T, const int n>
struct RURQ {
    T t[4*n], l[4*n]; function<T(_(T),_(T))> op;
    RURQ(T e, function<T(_(T),_(T))> f): op(f) {fill(t,t+4*n,e), fill(l,l+4*n,e);}
    #define U(x,y) x = op(x,y)
    void propagate(int k, int s, int e) {
        U(t[k],l[k]*(e-s+1));
        if (s != e) U(l[2*k],l[k]), U(l[2*k+1],l[k]);
        l[k] = t[0];
    }
    void update(int a, int b, const T &v, int k = 1, int s = 0, int e = n-1) {
        if (a <= s and e <= b) {U(l[k],v), propagate(k,s,e); return;}
        propagate(k,s,e);
        if (b < s or e < a) return;
        update(a,b,v,2*k,s,(s+e)/2), update(a,b,v,2*k+1,(s+e)/2+1,e);
        t[k] = op(t[2*k],t[2*k+1]);
    }
    T query(int a, int b, int k = 1, int s = 0, int e = n-1) {
        propagate(k,s,e);
        if (a <= s and e <= b) return t[k];
        if (b < s or e < a) return t[0];
        return op(query(a,b,2*k,s,(s+e)/2),query(a,b,2*k+1,(s+e)/2+1,e));
    }
    #undef U
};

const int N = 1e5+3;
RURQ<ll,N> seg(0,[](ll x, ll y){return x+y;});

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n; cin >> n;
    int p = 0;
    REP(i,1,n) {
        int a; cin >> a;
        seg.update(i,i,a-p);
        p = a;
    }
    int q; cin >> q;
    REP(i,1,q) {
        int c; cin >> c;
        if (c == 1) {
            int l, r; cin >> l >> r;
            seg.update(l,r,+1);
            seg.update(r+1,r+1,-(r-l+1));
        } else {
            int x; cin >> x;
            cout << seg.query(1,x) << '\n';
        }
    }
}

탈옥

문제 링크

구현 연습에 도움이 된다. 더불어 깔끔한 구현을 익히는데에도 도움이 될 것 같다.

풀이....

두 죄수의 경로가 겹치는 경우를 어떻게 처리해야 할까?

두 경로 상에서 만나는 지점을 찾겠다고 하면 문제가 산으로 간다...

분명히 이 방향이 맞기는 하다.

 

만나는 지점을 찾는 것이 아니라, 만나는 지점을 설정해서

밖→교점, 죄수1→교점, 죄수2→교점 3개 경로 합을 고려해주면 된다.

코드....

0-1 BFS를 사용하는 것이 제일 깔끔하다.

필자는 처음에 BFS를 하다가 가중치 0인 구간에서는 flood-fill을 하는 식으로 풀었는데, 그게 사실 0-1 BFS라서, 그냥 0-1 BFS로 고쳤다.

디버깅도 한 번 했는데, bfs라서 간과하고 dist를 초기화하지 않았다.

연결 그래프가 아닌 경우에 에러를 뱉어내는 것을 알아내고, 고쳐서 AC를 받았다.

#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 H = 103, W = 103;
int h, w, d[3][H][W];
char b[H][W];
deque<ii> dq;

const ii d4[] {{0,1},{1,0},{0,-1},{-1,0}};
bool out(int x, int y) {return 0 > x or x > h+1 or 0 > y or y > w+1;}

void _01bfs(ii x, int dist[H][W]) {
    fill(dist[0],dist[H],1e7), dist[x.first][x.second] = 0;
    bool vis[H][W] {0,};
    dq.push_back(x);
    while (not empty(dq)) {
        auto [sr,sc] = dq.front(); dq.pop_front();
        for (auto [dr,dc] : d4) {
            int ur = sr+dr, uc = sc+dc;
            if (out(ur,uc) or vis[ur][uc]) continue;
            vis[ur][uc] = true;
            if (b[ur][uc] == '.') {
                dist[ur][uc] = dist[sr][sc];
                dq.push_front({ur,uc});
            } else if (b[ur][uc] == '#') {
                dist[ur][uc] = dist[sr][sc]+1;
                dq.push_back({ur,uc});
            }
        }
    }
}

void input(ii &x, ii &y) {
    cin >> h >> w;
    fill(b[0],b[H],'.');
    bool first = true;
    REP(i,1,h) REP(j,1,w) {
        cin >> b[i][j];
        if (b[i][j] == '$') {
            if (first) x = {i,j};
            else y = {i,j};
            first = false;
            b[i][j] = '.';
        }
    }
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t; cin >> t; REP(_,1,t)
    {
        ii j1, j2; input(j1,j2);
        _01bfs({0,0},d[0]), _01bfs(j1,d[1]), _01bfs(j2,d[2]);
        int ans = 1e9;
        REP(i,1,h) REP(j,1,w) {
            if (b[i][j] == '.') ans = min(ans,d[0][i][j]+d[1][i][j]+d[2][i][j]);
            if (b[i][j] == '#') ans = min(ans,d[0][i][j]+d[1][i][j]+d[2][i][j]-2);
        }
        cout << ans << '\n';
    }
}

박성원

문제 링크

김도훈은 이 문제를 풀었다.

풀이.....

$dp(S,m):=S$를 사용해서 만든 수들 중 $k$로 나눈 나머지가 $m$인 경우의 수

$\displaystyle dp(S,m)=\sum_{i\in S}dp(S\setminus \{i\},m-a_i\times 10^{\text{len}(S\setminus \{i\})}\text{ mod } k)$

코드.....

null 문자가 들어갈 공간을 남겨둬야 된다는 것을 간과했다.

std::string에서 char*로 갈아탄 뒤 처음 낸 실수인데, 다행히 거의 6-7년 전쯤? 옛날에 배운 실수였어서 바로 디버깅할 수 있었고, 앞으로 내지 말아야겠다.

#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 = 15, L = 52, K = 100;
int n, k, ten[L*N] {1};
int len[1<<N];
ll dp[1<<N][K], mod[N];

ll fac(ll n) {
    if (n <= 1) return 1;
    return n*fac(n-1);
}
void input() {
    char num[N][L] {0,};
    cin >> n;
    REP(i,0,n-1) cin >> num[i];
    cin >> k;
    REP(x,0,(1<<n)-1) REP(i,0,n-1) if (x>>i&1)
        len[x] += strlen(num[i]);
    int l = len[(1<<n)-1];
    REP(i,1,l-1) ten[i] = (ten[i-1]*10)%k;
    REP(i,0,n-1) {
        l = len[1<<i];
        REP(j,0,l-1)
            mod[i] += (num[i][j]-'0')*ten[l-1-j],
            mod[i] %= k;
    }
}
void output() {
    ll x = dp[(1<<n)-1][0], y = fac(n);
    ll g = gcd(x,y);
    x /= g, y /= g;
    cout << x << "/" << y;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    input();
    dp[0][0] = 1;
    REP(s,0,(1<<n)-1) {
        REP(i,0,n-1) if (s>>i&1) {
            int l = len[s^(1<<i)];
            REP(m,0,k-1)
                dp[s][(m+mod[i]*ten[l])%k] += dp[s^(1<<i)][m];
        }
    }
    output();
}