2.17 PS: 세종정보올림피아드 밀기

세종정보올림피아드를 개인 사정으로 불참하고 나서, 언젠가는 풀어야겠다는 생각을 하고 있었다.

그런데, 요즘 푸는 문제들이 하나같이 귀찮다. 재밌긴 한데, 구현까지 가지를 못 한다.

PS에 대한 즐거움을 살리기 위해 오늘 한번 날을 잡고 풀어 보았다. 학원 수업은 안 들었지만 어떠한가.

체감 난이도는 실5-실1-플5-플4?

 

되게 쉽게 풀고 끝낼 줄 알았는데, 난 내 생각보다 더 못한다.;;

 

code.sasa.hs.kr/problemset.php

SASA OJ

함께 풀어볼 분들은 이 사이트를 권합니다.

 

2690 세종이와 레이저(L)(고등부 A번)

ABC C번에 나올것처럼 생겼다.

 

풀이>>

주요 아이디어: 구현, map

 

원점을 레이저로 잡고 기울기들을 세면 된다. 이건 std::map으로 쉽게 할 수 있다. 0으로 나눔에 주의하자.

그런데, 같은 기울기더라도 레이저가 반직선이기 때문에 y좌표의 범위/x좌표의 범위에 따라서 나눠줘야 한다.

그 다음에는 +x/-x/+y/-y에 위치하는 쓰레기들을 다 세준다. 참고로 레이저와 쓰레기는 겹치지 않는다.

 

코드는 다음과 같다.

 

#pragma warning(disable:4996)
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#define fastio ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ln endl
#define rp ' '
typedef long long ll;
typedef long double lf;
using namespace std;
map<lf, int> mpu;
map<lf, int> mpd;
int u;
int d;
int l;
int r;
int main()
{
    lf x, y;
    ll n;
    cin >> x >> y >> n;
    for (ll i = 1; i <= n; i++)
    {
        lf p, q;
        cin >> p >> q;
        p -= x, q -= y;
        if (p == 0)
        {
            if (q > 0) u++;
            else if (q < 0) d++;
        }
        else if (q == 0)
        {
            if (p > 0) r++;
            else if (p < 0) l++;
        }
        else if (q > 0)
        {
            mpu[q / p]++;
        }
        else if (q < 0)
        {
            mpd[q / p]++;
        }
    }
    int ans = 0;
    ans = max(ans, u);
    ans = max(ans, d);
    ans = max(ans, l);
    ans = max(ans, r);
    for (auto i : mpu)
    {
        ans = max(ans, i.second);
    }
    for (auto i : mpd)
    {
        ans = max(ans, i.second);
    }
    cout << ans;
 
}

 

2686 SJOI 찾기(2) (고등부 B번)

못 풀었다. 레전드 ㅋㅋ

디버깅이 귀찮아서 남겨뒀다. 

 

2688 소수 찾기(L) (고등부 C번)

꿀잼인가..노잼인가? 그 중간점에 있는 문제

 

풀이>>

주요 아이디어: 중위 순회, 세그먼트(펜윅) 트리

 

트리의 높이와 너비 + 세그(펜윅)트리

 

결합하는게 은근 귀찮다.

그냥 트높너(중위 순회)를 일단 푼 다음에, 그 답으로 나온 인덱스들을 몽땅 세그에 대응시킨다.

그러고 나서 쿼리들을 대응되는 인덱스에 맞춰서 풀어주면 된다.

 

정풀인데 TLE나길래 fastio(@myungwoo)로 추하게 비볐다. 결과는 1초 이상 감소.;;

 

코드입니다.

 

#pragma warning(disable:4996)
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <assert.h>
#define fastio ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ln endl
#define rp ' '
template<typename T> inline void read(T& x) {
    char c = getchar_unlocked(); bool f = 0; x = 0;
    while (!isdigit(c)) f |= c == '-', c = getchar_unlocked();
    while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar_unlocked();
    if (f) x = -x;
}
template<typename T, typename... Args> inline void read(T& x, Args& ...args) {
    read(x); read(args...);
}
template<typename T> inline void write(T x) {
    if (x < 0) putchar_unlocked('-'), write(-x);
    else { if (x > 9) write(x / 10); putchar('0' + x % 10); }
}
typedef long long ll;
typedef long double lf;
using namespace std;
typedef struct Node
{
    int left;
    int right;
    int num;
    int idx;
    int lridx;
};
int prime[100100];
void sieve()
{
    for (int i = 2; i <= 100001; i++)
    {
        if (prime[i]) continue;
        for (int j = 2; i * j <= 100000; j++)
        {
            prime[i * j] = 1;
        }
    }
}
Node t[100100];
int n;
int cnt = 1;
int st[200100];
int nw[100100];
void trav(int now)
{
    if(t[now].left) trav(t[now].left);
    t[now].lridx = cnt++;
    nw[t[now].lridx] = !prime[t[now].num];
    if (t[now].right) trav(t[now].right);
}
int sz;
void update(int k, int v)
{
    k += sz;
    for (st[k] = v; k > 1; k >>= 1) st[k >> 1] = st[k] + st[k ^ 1];
}
int query(int s, int e)
{
    int res = 0;
    for (s += sz, e += sz; s <= e; s >>= 1, e >>= 1)
    {
        if (s & 1) res += st[s++];
        if (!(e & 1)) res += st[e--];
    }
    return res;
}
int main()
{
    read(n);
    sz = n + 5;
    sieve();
    prime[1] = 1;
    for (int i = 1; i <= n; i++)
    {
        cin >> t[i].num;
        t[i].idx = i;
    }
    for (int i = 1; i < n; i++)
    {
        int p, s;
        char a;
        read(p);
        read(s);
        a = getchar_unlocked();
        if (a == 'L')
        {
            t[p].left = s;
        }
        else t[p].right = s;
    }
    trav(1);
    int Q;
    cin >> Q;
    for (int i = 1; i <= n; i++) update(i, nw[i]);
    while (Q--)
    {
        int c, p, q;
        read(c);
        if (c == 1)
        {
            read(p);
            read(q);
            int lrp = t[p].lridx;
            int lrq = t[q].lridx;
            if (lrp > lrq) swap(lrp, lrq);
            write(query(lrp, lrq));
            putchar_unlocked('\n');
        }
        else
        {
            read(p);
            read(q);
            update(t[p].lridx, !prime[q]);
        }
    }
}

2692 세종이의 블록 쌓기(L) (고등부 D번)

관찰이 중요한 문제..인것 같기도 하다. 한 번에 맞아서 기분이 진짜 좋았다.

 

풀이>>

주요 아이디어: Bit DP

타일을 못 세운다는게 내 풀이에서는 굉장히 중요하다.

타일을 못 세우는 순간, 각 층을 독립적으로 풀어야 한다.

 

한 층을 푸는 상황을 생각해 보자. 그러면, 이제 되게 익숙한 모양이 나온다. SOS DP, 두부DP 등의 이름을 가진 그것이다.

 

자신의 칸부터 시작해서 다음 행의 같은 열까지 총 m+1개 칸을 비트로 저장한다. 적절한 두부DP 논리를 통해서 상태 전이를 결정할 수 있다. YAY!

 

이제 각 칸은 독립이니까 곱사건으로 처리해주면 답이다.

 

코드입니다.

 

#pragma warning(disable:4996)
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <queue>
#define fastio ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ln endl
#define rp ' '
typedef long long ll;
typedef long double lf;
using namespace std;
ll map[12][12][3];
ll dp[11][11][1 << 11];
const ll LMOD = 1 << 11;
const ll MOD = 1000000007;
ll n, m;
ll solve(ll nowx, ll nowy, ll bit, ll mapn)
{
    ll& ret = dp[nowx][nowy][bit];
    if (nowx == n && nowy == m) return 1;
    if (ret) return ret % MOD;
    ll now = map[nowx][nowy][mapn];
    if (!now)
    {
        if (nowy == m) return ret = solve(nowx + 1, 1, (bit << 1) % LMOD, mapn)%MOD;
        else return ret = solve(nowx, nowy + 1, (bit << 1)%LMOD, mapn)%MOD;
    }
    else
    {
        if ((bit & (1LL << (n))))
        {
            if (nowy == m) return ret = solve(nowx + 1, 1, (bit << 1) % LMOD, mapn)%MOD;
            else return ret = solve(nowx, nowy + 1, (bit << 1) % LMOD, mapn)%MOD;
        }
        else
        {
            if (nowy == m) ret += solve(nowx + 1, 1, (bit << 1) % LMOD, mapn)%MOD;
            else ret += solve(nowx, nowy + 1, (bit << 1) % LMOD, mapn)%MOD;
            ret %= MOD;
            if (map[nowx + 1][nowy][mapn] && !(bit&1))
            {
                if (nowy == m) ret += solve(nowx + 1, 1, ((bit | 1) << 1) % LMOD, mapn);
                else ret += solve(nowx, nowy + 1, ((bit | 1) << 1) % LMOD, mapn);
                ret %= MOD;
            }
            if (map[nowx][nowy + 1][mapn] && !(bit & (1LL<<(n - 1))))
            {
                if (nowy == m) ret += solve(nowx + 1, 1, ((bit | (1LL << (n - 1))) << 1) % LMOD, mapn)%MOD;
                else ret += solve(nowx, nowy + 1, ((bit | (1LL << (n - 1))) << 1) % LMOD, mapn)%MOD;
                ret %= MOD;
            }
            return ret%MOD;
        }
    }
}
int main()
{
    ll max_ = 0;
    cin >> n >> m;
    for (ll i = 1; i <= n; i++)
    {
        for (ll j = 1; j <= m; j++)
        {
            cin >> map[i][j][0];
            max_ = max(max_, map[i][j][0]);
        }
    }
    for (ll i = 1; i <= n; i++)
    {
        for (ll j = 1; j <= m; j++)
        {
            for (ll k = 0; k < 2; k++)
            {
                if (map[i][j][k])
                {
                    if (map[i][j][k] > 1)
                    {
                        map[i][j][k + 1] = map[i][j][k] - 1;
                    }
                    map[i][j][k] = 1;
                }
            }
        }
    }
    ll ans = 1;
    for (int i = 0; i < max_; i++)
    {
        memset(dp, 0, sizeof(dp));
        ans *= solve(1, 1, 0, i) % MOD;
        ans %= MOD;
    }
    cout << ans;
}

 

아주 어렵진 않고 문제도 나쁘지 않다. 다만 웰노운을 섞어놔서 좀 구현량이 있고 귀찮은 느낌?

내 친구(GOD)이 1시간 40분 컷 냈다던데, 대단한 것 같다. 실수가 없는 점을 배우고 싶다.