Coder's Brunch: 풀이쓸예정

레이블이 풀이쓸예정인 게시물을 표시합니다. 모든 게시물 표시

5386번: Doubloon Game

https://www.acmicpc.net/problem/5386

#include<cstdio>
int s, k, t;
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d%d", &s, &k);
        if (k & 1) printf("%d\n", s & 1);
        else {
            s %= k + 1;
            printf("%d\n", s / k*k + s % 2);
        }
    }
    return 0;
}

5888번: Haybale Restacking

https://www.acmicpc.net/problem/5888

#include<cstdio>
#include<cstdlib>
int s[100001], n;
long long f(int x) {
    long long ret = 0;
    for (int i = 1; i <= n; i++) ret += abs(s[i] - x);
    return ret;
}
int main() {
    scanf("%d", &n);
    for (int i = 1, x, y; i <= n; i++) {
        scanf("%d%d", &x, &y);
        s[i] = s[i - 1] + y - x;
    }
    int low = 0, up = 2e8, mid;
    while (low < up) {
        mid = low + up >> 1;
        f(mid - 1e8) < f(mid - 1e8 + 1) ? up = mid : low = mid + 1;
    }
    printf("%lld", f(up - 1e8));
    return 0;
}

8885번: Pirate Chest

https://www.acmicpc.net/problem/8885

시간복잡도는 $O(n^2m)$

#include<cstdio>
#include<algorithm>
using namespace std;
int a, b, n, m, d[501][501], sz[501];
pair<int, int> stk[501][501];
long long res;
void update(int x, int y, int h) {
    x = min(x, a);
    y = min(y, b);
    int s = x*y;
    res = max(res, s*(h + (1LL * h*s - 1) / (n*m - s)));
}
void push(int i, int x, int y, int h) {
    while (stk[i][sz[i]].first > h) {
        update(x, y - stk[i][sz[i] - 1].second - 1, stk[i][sz[i]].first);
        update(y - stk[i][sz[i] - 1].second - 1, x, stk[i][sz[i]].first);
        sz[i]--;
    }
    stk[i][++sz[i]] = { h,y };
}
int main() {
    scanf("%d%d%d%d", &a, &b, &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", d[i] + j);
            int x = 1e9;
            for (int k = i; k; k--) push(k, i - k + 1, j, x = min(x, d[k][j]));
        }
        for (int j = i; j; j--) push(j, i - j + 1, m + 1, 0), sz[j] = 0;
    }
    printf("%lld", res);
    return 0;
}

4223번: Mummy Madness

https://www.acmicpc.net/problem/4223

시간복잡도는 테스트 케이스마다 $O(n\lg L * (\lg L+\lg n))$

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MX = 1e6;
struct st {
    int x, l, r, c;
}line[200000];
int n, x[100000], y[100000], len[MX * 8], cnt[MX * 8];
void update(int h, int l, int r, int gl, int gr, int x) {
    if (gr < l || r < gl) return;
    if (gl <= l&&r <= gr) cnt[h] += x;
    else update(h * 2 + 1, l, (l + r) / 2, gl, gr, x), update(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr, x);
    len[h] = cnt[h] ? r - l + 1 : l^r ? len[h * 2 + 1] + len[h * 2 + 2] : 0;
}
bool f(int t) {
    int sz = 0;
    for (int i = 0; i < n; i++) {
        int sx = max(x[i] - t, MX - t), ex = min(x[i] + t, MX + t),
            sy = max(y[i] - t, MX - t), ey = min(y[i] + t, MX + t);
        if (sx > ex || sy > ey) continue;
        line[sz++] = { sx,sy,ey,1 };
        line[sz++] = { ex + 1,sy,ey,-1 };
    }
    sort(line, line + sz, [](st i, st j) {return i.x < j.x; });
    long long area = 0;
    for (int i = 0; i < sz; i++) {
        if (i) area += 1LL * len[0] * (line[i].x - line[i - 1].x);
        update(0, 0, MX * 2 + 1, line[i].l, line[i].r, line[i].c);
    }
    return area < 4LL * t*t + 4 * t + 1;
}
int main() {
    for (int t = 1; scanf("%d", &n), ~n; t++) {
        for (int i = 0; i < n; i++) {
            scanf("%d%d", x + i, y + i);
            x[i] += MX;
            y[i] += MX;
        }
        int low = 0, up = MX, mid;
        while (low <= up) {
            mid = (low + up) / 2;
            f(mid) ? low = mid + 1 : up = mid - 1;
        }
        printf("Case %d: ", t);
        low > MX ? puts("never") : printf("%d\n", low);
    }
    return 0;
}

9240번: Robert Hood

https://www.acmicpc.net/problem/9240

$O(n\lg n)$

#include<cstdio>
#include<algorithm>
#define x first
#define y second
#define dis(a,b) hypot(a.x-b.x,a.y-b.y)
using namespace std;
const int MXN = 1e5;
int t, n;
typedef struct pair<int, int> point;
point p[MXN], ch[MXN];
int ccw(point a, point b, point c) {
    return (b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y);
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d %d", &p[i].x, &p[i].y);
    swap(p[0], *min_element(p, p + n));
    sort(p + 1, p + n, [](point l, point r) {
        int c = ccw(p[0], l, r);
        return c > 0 || !c && l < r;
    });
    int sz = 0;
    for (int i = 0; i < n; i++) {
        while (sz > 1 && ccw(ch[sz - 2], ch[sz - 1], p[i]) <= 0) sz--;
        ch[sz++] = p[i];
    }
    double maxi = 0;
    for (int i = 0, j = 1; i < sz; i++) {
        while (ccw(ch[i], ch[(i + 1) % sz], { ch[i].x + ch[(j + 1) % sz].x - ch[j].x, ch[i].y + ch[(j + 1) % sz].y - ch[j].y }) > 0) j = (j + 1) % sz;
        if (maxi < dis(ch[i], ch[j])) maxi = dis(ch[i], ch[j]);
    }
    printf("%lf", maxi);
    return 0;
}

10254번: Highway

https://www.acmicpc.net/problem/10254

$O(tn\lg n)$

#include<cstdio>
#include<algorithm>
#define x first
#define y second
#define dis(a,b) 1LL*(a.x-b.x)*(a.x-b.x)+1LL*(a.y-b.y)*(a.y-b.y)
using namespace std;
const int MXN = 2e5;
int t, n;
typedef struct pair<int, int> point;
point p[MXN], ch[MXN], ra, rb;
long long ccw(point a, point b, point c) {
    return 1LL * (b.x - a.x)*(c.y - a.y) - 1LL * (c.x - a.x)*(b.y - a.y);
}
void f() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d %d", &p[i].x, &p[i].y);
    swap(p[0], *min_element(p, p + n));
    sort(p + 1, p + n, [](point l, point r) {
        long long c = ccw(p[0], l, r);
        return c > 0 || !c && l<r;
    });
    int sz = 0;
    for (int i = 0; i < n; i++) {
        while (sz > 1 && ccw(ch[sz - 2], ch[sz - 1], p[i]) <= 0) sz--;
        ch[sz++] = p[i];
    }
    long long maxi = 0;
    for (int i = 0, j = 1; i < sz; i++) {
        while (ccw(ch[i], ch[(i + 1) % sz], { ch[i].x + ch[(j + 1) % sz].x - ch[j].x, ch[i].y + ch[(j + 1) % sz].y - ch[j].y }) > 0) j = (j + 1) % sz;
        if (maxi < dis(ch[i], ch[j])) {
            maxi = dis(ch[i], ch[j]);
            ra = ch[i];
            rb = ch[j];
        }
    }
    printf("%d %d %d %d\n", ra.x, ra.y, rb.x, rb.y);
}
int main() {
    for (scanf("%d", &t); t--;) f();
    return 0;
}

3038번: JOGURT

https://www.acmicpc.net/problem/3038

$O(2^n)$

#include<cstdio>
int n;
void f(int x, int y) {
    if (y == 1 << n - 1) {
        printf("%d ", y * 3 - 1 - x);
        return;
    }
    printf("%d ", x);
    f(x + y, y * 2);
    f(x + y * 2, y * 2);
}
int main() {
    scanf("%d", &n);
    f(1, 1);
    return 0;
}

14557번: Memory

https://www.acmicpc.net/problem/14557

$O(1)$

매 시도마다 짝을 맞추는 경우 rc / 2 번만에 승리할 수 있고, 이 횟수가 최소이다.
최대는 rc - 1

#include<cstdio>
int r, c;
int main() {
    scanf("%d%d", &r, &c);
    printf("%d %d", r*c / 2, r*c - 1);
    return 0;
}

https://www.acmicpc.net/problem/5922

$O(n)$

간단히 x 이상인 수가 절반이상인 구간의 수를 구하면 된다.
a[i] = h[i]가 x이상이면 1, x미만이면 -1이라 하면
임의의 [i,j]에 대해 a[i...j] 합이 0이상인 경우 [i,j]는 x이상인 수가 절반이상이다.
따라서 누적합 s[i]=sum(a[1...i])을 이용하여 증가하는 j마다 i<j인 임의의 i에 대해 s[i]<=s[j]인 i의 수를 빠르게 찾으면 된다.

여기서부터는 펜윅트리 같은 자료구조를 이용해서 풀 수도 있지만,
i가 증가함에 따라 s[i]의 변화량이 최대 1 밖에 되지 않는다는 점을 착안하여 prefix sum을 이용하여 O(n)에 해결할 수 있다.

#include<cstdio>
int n, x, a[200001], p, t;
long long r, s = 1;
int main() {
    scanf("%d%d", &n, &x);
    a[p = n] = 1;
    while (n--) {
        scanf("%d", &t);
        t < x ? s -= a[p--] : s += a[++p];
        a[p]++; r += s++;
    }
    printf("%lld", r);
    return 0;
}

2534번: 카드 배열

https://www.acmicpc.net/problem/2534

$O(n\lg n)$

#include<cstdio>
#include<queue>
#include<vector>
#define mod 1000000007
using namespace std;
const int MXN = 3e5;
int n, k, p, ind[2][MXN], r[2][MXN], s, od[MXN];
vector<int> adj[2][MXN];
priority_queue<int> pq;
void f(int t) {
    for (int i = 0; i < k; i++) if (!ind[t][i]) pq.push(-i);
    int i = 0;
    while (!pq.empty()) {
        int h = -pq.top();
        pq.pop();
        r[t][h] = od[i++];
        for (auto it : adj[t][h]) if (!--ind[t][it]) pq.push(-it);
    }
}
int main() {
    scanf("%d%d%d", &n, &k, &p);
    for (int i = 0, x, y; i < p; i++) {
        scanf("%d%d", &x, &y);
        adj[0][x].push_back(y);
        adj[1][y].push_back(x);
        ind[0][y]++;
        ind[1][x]++;
    }
    for (int i = 0; i < k; i++) od[i] = k - 1 - i;
    f(0);
    for (int i = 0; i < k; i++) od[i] = n - k + i;
    f(1);
    for (int i = k; i--;) s = ((long long)s*n + r[1][i] - r[0][i] + mod) % mod;
    printf("%d", s);
    return 0;
}

3350번: Candy Machine

https://www.acmicpc.net/problem/3350

$O(nlgn)$

#include<cstdio>
#include<algorithm>
using namespace std;
int n, r[100000], dp[100000], sz;
pair<int, int> p[100000];
int main() {
    scanf("%d", &n);
    for (int i = 0, s, t; i < n; i++) {
        scanf("%d%d", &s, &t);
        p[i] = { t - s,s + t };
    }
    sort(p, p + n);
    for (int i = n; i--;) {
        int t = lower_bound(dp, dp + sz, p[i].second) - dp;
        dp[t] = p[i].second;
        r[i] = t;
        if (t == sz) sz++;
    }
    printf("%d", sz);
    for (int i = 0; i < n; i++) printf("\n%d %d %d", (p[i].second - p[i].first) / 2, (p[i].first + p[i].second) / 2, r[i] + 1);
    return 0;
}

11278번: 2-SAT - 2

https://www.acmicpc.net/problem/11278

#include<stdio.h>
int n, m, a[100], b[100];
int f(int x, int y) {
    return x < 0 ? 1 - (y >> -x - 1) % 2 : (y >> x - 1) % 2;
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++)
        scanf("%d %d", &a[i], &b[i]);
    int res = -1;
    for (int i = 0; i < 1 << n; i++) {
        bool flag = true;
        for (int j = 0; j < m; j++)
            flag &= f(a[j], i) | f(b[j], i);
        if (flag) {
            res = i;
            break;
        }
    }
    if (res == -1) puts("0");
    else {
        puts("1");
        for (int i = 0; i < n; i++)
            printf("%d ", (res >> i) % 2);
    }
    return 0;
}

11280번: 2-SAT - 3

https://www.acmicpc.net/problem/11280

#include<stdio.h>
#include<vector>
#define pb(x) push_back(x);
using namespace std;
const int MAX_N = 10000;
int n, m, c[MAX_N * 2 + 1];
vector<int> adj[2][MAX_N * 2 + 1];
bool ck[MAX_N * 2 + 1];
vector<int> vis, tvis;
void dfs(int h, bool type) {
    if (ck[h] != type) return;
    ck[h] = !type;
    for (auto t : adj[type][h])
        dfs(t, type);
    vis.pb(h);
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        adj[0][n - a].pb(n + b);
        adj[0][n - b].pb(n + a);
        adj[1][n + b].pb(n - a);
        adj[1][n + a].pb(n - b);
    }
    for (int i = 0; i < n; i++)
        dfs(i, false), dfs(i + n + 1, false);
    tvis = vis;
    for (int i = tvis.size() - 1; i >= 0; i--) {
        if (!ck[tvis[i]]) continue;
        vis.clear();
        dfs(tvis[i], true);
        for (auto it : vis) c[it] = i;
    }
    bool res = true;
    for (int i = 0; i < n; i++)
        res &= c[i] != c[2 * n - i];
    printf("%d", res);
    return 0;
}

5941번: Cow Calisthenics

https://www.acmicpc.net/problem/5941

$O(n{\lg n}^2)$

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int v, s, d[100001];
vector<int> adj[100001];
int f(int h, int p, int l) {
    int c = 0, i;
    vector<int> v;
    for (auto it : adj[h]) if (it^p) {
        c += f(it, h, l);
        v.push_back(d[it] + 1);
    }
    if (v.empty()) return 0;
    sort(v.begin(), v.end());
    for (i = v.size(); --i&&v[i - 1] + v[i] > l;) c++;
    d[h] = v[i] % (l + 1);
    return c + (v[i] > l);
}
int main() {
    scanf("%d%d", &v, &s);
    for (int i = 0, x, y; i < v - 1; i++) {
        scanf("%d%d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    int low = 0, up = v - 1, mid;
    while (low <= up) {
        mid = (low + up) / 2;
        f(1, 0, mid) <= s ? up = mid - 1 : low = mid + 1;
    }
    printf("%d", low);
    return 0;
}

2611번: 자동차경주

https://www.acmicpc.net/problem/2611

$O(n+m)$

DAG 그래프이므로 dp로 해결할 수 있다.

#include<cstdio>
#include<vector>
using namespace std;
const int MXN = 1000;
int n, m, dp[MXN + 1], go[MXN + 1];
vector<pair<int, int> > adj[MXN + 1];
int f(int h) {
    if (!dp[h] && h != 1) for (auto it : adj[h]) {
        int t = f(it.first) + it.second;
        if (t > dp[h]) dp[h] = t, go[h] = it.first;
    }
    return dp[h];
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0, x, y, z; i < m; i++)
        scanf("%d %d %d", &x, &y, &z), adj[x].push_back({ y,z });
    int r = 0, idx = 1, t;
    for (auto it : adj[1]) {
        t = f(it.first) + it.second;
        if (t > r) r = t, idx = it.first;
    }
    printf("%d\n1", r);
    for (int i = idx; i; i = go[i]) printf(" %d", i);
    return 0;
}

2670번: 연속부분최대곱

https://www.acmicpc.net/problem/2670

#include<cstdio>
int n;
double r, t, x;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%lf", &x);
        t = t < 1 ? x : x*t;
        if (t > r) r = t;
    }
    printf("%.3lf", r);
    return 0;
}

2098번: 외판원 순회

https://www.acmicpc.net/problem/2098

#include<cstdio>
#include<algorithm>
using namespace std;
int n, dp[1 << 16][16], w[16][16];
int f(int x, int y) {
    if (x == (1 << n) - 1) return w[y][0] ? w[y][0] : 1e9;
    if (!dp[x][y]) {
        dp[x][y] = 1e9;
        for (int i = 0; i<n; i++) if (w[y][i] && !(x & 1 << i))
            dp[x][y] = min(dp[x][y], f(x | 1 << i, i) + w[y][i]);
    }
    return dp[x][y];
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i<n; i++) for (int j = 0; j<n; j++) scanf("%d", &w[i][j]);
    printf("%d", f(1, 0));
    return 0;
}

7577번: 탐사

https://www.acmicpc.net/problem/7577

#include<stdio.h>
int l, n, w[41][41];
int main() {
    scanf("%d %d", &l, &n);
    for (int i = 0; i <= l; i++)
        for (int j = 0; j <= l; j++) if (i != j) w[i][j] = 1e9;
    for (int i = 0; i < l; i++) w[i + 1][i] = 0, w[i][i + 1] = 1;
    for (int i = 0, x, y, z; i < n; i++) {
        scanf("%d %d %d", &x, &y, &z);
        if (w[x - 1][y]>z) w[x - 1][y] = z;
        w[y][x - 1] = -z;
    }
    for (int i = 0; i <= l; i++)
        for (int j = 0; j <= l; j++)
            for (int k = 0; k <= l; k++)
                if (w[j][i] + w[i][k]<w[j][k]) w[j][k] = w[j][i] + w[i][k];
    for (int i = 0; i <= l; i++) if (w[i][i] < 0) {
        puts("NONE");
        return 0;
    }
    for (int i = 0; i < l; i++) putchar(w[0][i + 1] - w[0][i] ? '#' : '-');
    return 0;
}

1199번: 오일러 회로

https://www.acmicpc.net/problem/1199

#include<cstdio>

const int MAX_N = 1e3;
int n, adj[MAX_N][MAX_N];
void dfs(int h) {
    for (int i = 0; i<n; i++) while (adj[h][i]) {
        adj[h][i]--;
        adj[i][h]--;
        dfs(i);
    }
    printf("%d ", h + 1);
}
int main() {
    scanf("%d", &n);
    for (int i = 0, c = 0; i<n; i++) {
        for (int j = 0; j<n; j++) {
            scanf("%d", &adj[i][j]);
            c += adj[i][j];
        }
        if (c & 1) {
            puts("-1");
            return 0;
        }
    }
    dfs(0);
    return 0;
}

2671번: 잠수함식별

https://www.acmicpc.net/problem/2671

#include<cstdio>
#include<regex>
using namespace std;
char str[151];
int main() {
    while (scanf("%s", str) != -1) puts(regex_match(str, regex("(100+1+|01)+")) ? "SUBMARINE" : "NOISE");
    return 0;
}

피드 구독하기: 글 ( Atom )

Coder's Brunch

페이지