2021 NYPC 예선 후기

파이썬이 정말 안 좋은 언어라는 것을 다시 한 번 깨닫게 해줬던 대회였다.

 

1301.6점이라는 뭔가 애매한? 점수를 받았다.

 

할 수 있는건 다 한듯하다. 작년에는 2000점 만점에 무려 400점(!)을 기록하였지만, 그래도 발전해서 기분이 좋음

 

def ip(): return int(input())
def sp(): return str(input().rstrip())
 
def mip(): return map(int, input().split())
def msp(): return map(str, input().split().rstrip())
 
def lmip(): return list(map(int, input().split()))
def lmsp(): return list(map(str, input().split().rstrip()))

코드를 볼 때 헷갈릴 수 있기에 일단 올려둔다.

 

 

 

 

1, 2는 연습문제라 패스. 1번은 쉬운 dp였고, 2번은 안 했다.

 

3 - 계단

 F의 값과는 관계없이,

 \( N / (M - 1) + (N\) \(mod\) \((M - 1) != 0) \) 이 답이 된다.

m, f, n = mip()
print(n // (m - 1) + (n % (m - 1) != 0))

 

 

 

4 - 레이스 기록 검증

 문제가 요구하는 대로 구현하면 끝이다. 나는 주행 중 여부와 시간에 대한 정보를 담는 배열을 활용했다.

n, q = mip()
c = [True] * (n + 1)
ti = [0] * (n + 1)
for i in range(q):
    m, p, t = mip()
    if t == 1:
        if c[p] == True:
            print("No")
            exit()
        if m - ti[p] < 60:
            print("No")
            exit()
        ti[p] = 0
        c[p] = True
    else:
        if c[p] == False:
            print("No")
            exit()
        ti[p] = m
        c[p] = False
 
for i in range(1, n + 1):
    if c[i] == False:
        print("No")
        exit()
print("Yes")

 

 

 

5 - 근무표 짜기

 근무 가능 개발자의 수가 가장 많은 날짜부터, 근무 가능일이 많은 사람부터 채워 넣으면 된다. 

n, m = mip()
ax = lmip()
bx = lmip()
 
a = [[ax[i], i] for i in range(n)]
b = [[bx[i], i] for i in range(m)]
 
a.sort(reverse=True)
ans = [[] for _ in range(m)]
for i in range(n):
    b.sort(reverse=True)
    for j in range(a[i][0]):
        b[j][0] -= 1
        ans[b[j][1]].append(a[i][1] + 1)
for i in ans:
    print(len(i), *i)

 

 

 

6 - 파티

 배열 [6, 3]이 있다고 할 때, [4, 5]로 만드는 것과, [5, 4]로 만드는 것 중 당연히 [5, 4]로 만드는 것이 이득이다.

 나머지를 배분할 때, 평균보다 큰 수는 (평균) + 1로 만들고, 작은 수는 평균에 맞춰주는 방식으로 짜면 된다.

n = ip()
a = lmip()
a.sort(reverse=True)
 
g = sum(a) // n
m = sum(a) % n
ans = 0
 
for i in range(m):
    ans += max(0, a[i] - (g + 1))
 
for i in range(m, n):
    ans += max(0, a[i] - g)
 
print(ans)

 

 

 

7 - 페인트 칠하기

 거꾸로 푸는 방식으로 풀 수 있다.

 

 1. 가장 마지막에 칠한 곳들을 찾기: 마지막에 칠해진 행 또는 열은 0과 어떤 색상 a로만 이루어져 있다. O(HW)로 찾는다.

 2. 0으로 만들기: 1번 과정에서 찾은 곳을 쭉 0으로 만든다. 그리고 그 행(혹은 열)과 색에 대한 정보를 답에 추가한다.

 

 위 과정을 (H+W) 번 반복하여 답을 얻을 수 있다. 시간복잡도는 \(O(HW(H+W))\)이다.

 파일에 출력하는 코드이다.

ans = []
fx = open("D:/새파일.txt", 'w')
 
def inui(v, c):
    for i in range(n):
        a[i][v] = 0
    tmp = "V " + str(v + 1) + " " + str(c)
    ans.append(tmp)
 
def toko(h, c):
    for i in range(m):
        a[h][i] = 0
    tmp = "H " + str(h + 1) + " " + str(c)
    ans.append(tmp)
 
 
n, m = mip()
a = [lmip() for _ in range(n)]
 
for name in range(n * m):
    for i in range(n):  # h
        q = 0
        for j in range(m):
            if a[i][j] != 0:
                q = a[i][j]
                break
        if q == 0:
            continue
        f = True
        for j in range(m):
            if a[i][j] != q and a[i][j] != 0:
                f = False
                print()
                break
        if f:
            toko(i, q)
 
    for j in range(m):  # v
        q = 0
        for i in range(n):
            if a[i][j] != 0:
                q = a[i][j]
                break
        if q == 0:
            continue
        f = True
        for i in range(n):
            if a[i][j] != q and a[i][j] != 0:
                f = False
                break
        if f:
            inui(j, q)
 
ans.reverse()
fx.write(str(len(ans))+'\n')
for i in ans:
    fx.write(i+'\n')

왜 느리나 했더니 저기 반복문에 (n + m)이 아니라 (n * m)으로 써놓았다. 이미 건드린 행 혹은 열은 다시 건드릴 필요가 없기 때문에 최대 (n + m) 번만 반복해도 충분하다.

 

 

 

8 - 폭탄 터트리기

 왼쪽부터 (최댓값) - (최솟값)과 k를 비교하며 O(N)으로 해결할 수 있다.

n, k = mip()
a = lmip()
 
f = a[0]
g = a[0]
 
ans = 0
for i in range(n):
    f = max(f, a[i])
    g = min(g, a[i])
    if f - g > k:
        ans += 1
        f = a[i]
        g = a[i]
 
print(ans + 1)

 

 

 

9 - 루트가 많은 트리?

 Union-Find로 무방향으로 연결된 곳을 합쳐주고, indegree가 0인 곳에서 모든 곳으로 갈 수 있다면 답은 0 이상이다.

 탐색 과정 중 방문한 곳은 불가능하다고 마킹해주고, 탐색이 끝나면 가능한 정점의 개수를 출력하면 된다.

sys.setrecursionlimit(10**6)
p = [i for i in range(303030)]
g = [[] for _ in range(303030)]
v = [False for _ in range(303030)]
ind = [0 for _ in range(303030)]
def dfs(x, f):
    v[x] = True
    for i, r in g[x]:
        if f and r == 0:
            continue
        liz[i] = 0
        if not v[i]:
            dfs(i, False)
 
n = ip()
liz = [1 for _ in range(n + 1)]
liz[0] = 0
 
lita = []
co = []
for i in range(n - 1):
    a, b, c = mip()
    if c == 0:
        union(a, b)
        g[a].append([b, 0])
        g[b].append([a, 0])
    else:
        g[a].append([b, 1])
        co.append(b)
        lita.append(a)
 
for i in co:
    ind[find(i)] += 1
 
for i in range(1, n + 1):
    if ind[i] > 1:
        print(0)
        exit()
 
for go in lita:
    if not v[go]:
        if ind[find(go)] == 0:
            dfs(go, True)
 
print(sum(liz))

 

 

 

10 - 영역 나누기

 두 수 사이에 처음 나오는 수(두번 나오면 카운트 x)의 개수를 세는 짓을 반복한 다음, 여기에 n+1을 더하면 답이 된다. 세그트리를 쓸 수 있다.

 

#include <iostream>
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
 
#define all(v) v.begin(), v.end()
#define fi first
#define se second
 
int seg[4040404];
int a[1010101];
int c[505050];
bool sx[1010101];
 
void update(int x, int idx, int s, int e, int d){
    if (e < idx || idx < s) return;
    seg[x] += d;
    if (s == e) return;
    int m = (s + e) >> 1;
    update(x * 2, idx, s, m, d);
    update(x * 2 + 1, idx, m + 1, e, d);
}
 
int getSum(int x, int l, int r, int s, int e){
    if (e < l || r < s) return 0;
    if (l <= s && e <= r) return seg[x];
    int m = (s + e) >> 1;
    return getSum(x * 2, l, r, s, m) + getSum(x * 2 + 1, l, r, m + 1, e);
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
 
    for (int i = 0; i < n * 2; i++) {
        cin >> a[i];
    }
 
    fill(c, c + n + 3, -1);
    fill(sx, sx + n * 2 + 3, false);
 
    for (int i=0;i<n*2;i++){
        if (c[a[i]] != -1){
            sx[i] = true;
        }
        else{
            c[a[i]] = i;
        }
    }
 
 
    ll ans = n + 1;
    for (int i=0;i<n*2;i++){
        if (sx[i]){
            update(1, c[a[i]] + 1, 1, n * 2, -1);
            ans += getSum(1, c[a[i]] + 1, n * 2, 1, n * 2);
        }
        else{
            update(1, i + 1, 1, n * 2, 1);
        }
    }
    cout << ans;
 
    return 0;
}

 

 

 

11 - K-좀비

 열심히 하면 된다.

fx = open("D:/새파일.txt", 'w')
 
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
 
n, m = mip()
a = [['#' for _ in range(m + 2)]] + [['#'] + list(input().rstrip()) + ['#'] for _ in range(n)] + [['#' for _ in range(m + 2)]]
 
g = [[1 for _ in range(m + 2)] for _ in range(n + 2)]
 
for i in range(1, n + 1):
    for j in range(1, m + 1):
        if a[i][j] != '.' and a[i][j] != '#':
            for k in range(4):
                nx = i + dx[k]
                ny = j + dy[k]
                g[nx][ny] = lcm(int(a[i][j]), g[nx][ny])
 
for i in range(n + 2):
    for j in range(m + 2):
        if a[i][j] != '.':
            g[i][j] = 0
 
q = deque()
q.append([1, 1, 0])
 
t = [[[[-1, -1] for _ in range(m + 2)] for _ in range(n + 2)] for _ in range(100001)]
v = [[[False for _ in range(m + 2)] for _ in range(n + 2)] for _ in range(100001)]
minT = 100000
while q:
    x, y, c = q.popleft()
    if x == n and y == m:
        minT = c
        break
 
    if c == 100000:
        continue
 
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
 
        if g[nx][ny] != 0 and (c + 1) % g[nx][ny] == 0 and not v[c][nx][ny]:
            v[c][nx][ny] = True
            t[c + 1][nx][ny][0] = x
            t[c + 1][nx][ny][1] = y
            q.append([nx, ny, c + 1])
 
nxt = [n, m]
bef = [t[minT][n][m][0], t[minT][n][m][1]]
ans = []
while minT:
    if nxt[0] == bef[0]:
        ans.append('R' if bef[1] < nxt[1] else 'L')
    else:
        ans.append('D' if bef[0] < nxt[0] else 'U')
    nxt = [bef[0], bef[1]]
    minT -= 1
    bef = [t[minT][nxt[0]][nxt[1]][0], t[minT][nxt[0]][nxt[1]][1]]
 
ans.reverse()
strAns = ""
for i in ans:
    strAns += i
fx.write(strAns)
# print(strAns)

 

 

 

12 - 다양성이 힘이다

 어느 구간에서 다음으로 넘어갈때, 3가지 경우로 나눠서 볼 수 있다.

[2, 1, 3, 4, 6, 8, 10]에서 왼쪽의 2가 빠지고 7이 생겼다고 하자. 아래 그림과 같이 된다.

 

편의상 어떤 구간의 검은 점들의 개수를 (구간에서 빠지는 점과 새로 들어오는 점은 세지 않아도 된다.) m이라고 하자.

이동하는 점이 l에서 r로 이동한다고 할 때,

 

구간 A에서는 \((r - l)m\),

구간 B에서는 \(-sum(a[l+1:r]) \times 2 + (l + r)m \), (저 사이 검은 점의 합이다.)

구간 C에서는 \((l - r)m\) 만큼 증가한다.

 

구간 B에서 필요한 sum의 값과, 각 구간의 길이는 점들의 좌표가 정렬되어야 구할 수 있고(다른 방법이 있는지는 모르겠다), 머지 소트 트리를 쓸 수 있다. O(Nlg^2N)에 풀린다.

#include <iostream>
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
 
#define all(v) v.begin(), v.end()
 
vector<int> a;
int n;
ll k;
 
vector<int> seg[808080];
vector<ll> p[808080];
 
 
void update(int i, int nod, int s, int e, int x){
    if(nod<s || e<nod) return;
    seg[i].push_back(x);
    if(s != e){
        update(i*2, nod, s, (s+e)/2, x);
        update(i*2+1, nod, (s+e)/2+1, e, x);
    }
}
 
pair<ll, ll> get(int i, int s, int e, int l, int r, ll x){
    if(l > e || r < s || r < l) return {0ll, 0ll};
    if(l <= s && e <= r){
        ll idx = upper_bound(all(seg[i]), x) - seg[i].begin();
        return {seg[i].size() - idx, p[i][seg[i].size() - 1] - p[i][idx]};
    }
    int m = (s + e) / 2;
    pair<ll, ll> L, R;
    L = get(i*2, s, m, l, r, x);
    R = get(i*2+1, m+1, e, l, r, x);
    return {L.first + R.first, L.second + R.second};
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    a.resize(n + 3);
    for (int i=1;i<=n;i++){
        cin >> a[i];
        update(1, i, 1, n, a[i]);
    }
 
    for (auto & i : seg) sort(i.begin(), i.end());
 
    for (int i=0;i<808080;i++){
        if (seg[i].empty()) continue;
        p[i].resize(seg[i].size() + 1);
        p[i].assign(seg[i].size() + 1, 0);
        for (int j=0;j<seg[i].size();j++){
            p[i][j + 1] = p[i][j] + seg[i][j];
        }
    }
 
    vector<int> tmp;
    for (int i=1;i<=k;i++){
        tmp.push_back(a[i]);
    }
 
    sort(tmp.begin(), tmp.end());
 
    ll ans = 0;
    for (int i=1;i<k;i++){
        ans += (tmp[i] - tmp[i - 1]) * (k - i) * i;
    }
    ll now = ans;
    for (int i=k+1;i<=n;i++){
        ll l = a[i - k];
        ll r = a[i];
        ll mult = 1;
        if (l > r){
            mult = -1;
            swap(l, r);
        }
        else if (l == r){
            continue;
        }
        pair<ll, ll> L, R;
        L = get(1, 1, n, i - k + 1, i - 1, l - 1);
        R = get(1, 1, n, i - k + 1, i - 1, r - 1);
 
        ll left = (k - 1) - L.first;
        ll right = R.first;
        ll mid = k - (left + right) - 1;
 
        ll pl = L.second;
        ll pr = R.second;
 
        now += left * (r - l) * mult;
        now += right * (l - r) * mult;
        now += (mid * (l + r) - 2 * (pl - pr)) * mult;
 
        ans = max(ans, now);
 
    }
    cout << ans;
 
    return 0;
}

 

 

 

13 - 원룸 구하기

 먼저, k종류의 가게를 포함하는 구간들을 투 포인터를 이용해 쭉 구해준다. 그러면 이제 원룸을 기준으로,

구간에 포함되는 경우, 구간 왼쪽 밖에 있는 경우, 오른쪽 밖에 있는 경우가 있다. 이 세 경우를 나누어 풀면 된다.

 (왼쪽부터) 구간 [L, R]에 대해, 최소 생활 거리는 L - X, R - L, X - R이 된다.

 이걸 써먹기 위해, L의 최댓값, R의 최솟값, (R - L)의 최솟값을 찾는 세그트리를 만든다.

 구간은 항상 L, R 기준으로 정렬된 상태이므로 L과 R 각각에 대한 이분 탐색을 통해 저 세 구간들의 인덱스를 O(lgN)에 찾을 수 있다. O(NlgN)에 풀린다.

 

 이거 푸는데 거리의 합을 구하는거로 잘못보고 코드를 잘못짰다. 어떤 가게 p의 좌표들을 a, b, c ... 라 하고, 함수 \(f_{p}(x)\)를 x에 원룸이 있을 때 가게 p와의 최소 거리라고 하자.

\(f_{p}(x) = min(|x - a|, |x - b|, |x - c| ... ) \)가 나온다. k종류의 가게들 각각에 대해 이 그래프를 만든 후, 이걸 다 더해주면 된다. 첫 번째 코드는 그렇게 짠 오답코드이고, 언젠가 비슷한 문제를 볼때 써먹을수 있을것 같아 올려둠

from bisect import bisect_right
 
 
n, k, m = mip()
l = [[] for _ in range(k + 1)]
 
t = []
for i in range(n):
    t.append(tuple(map(int, input().split())))
 
t.sort(key=lambda x:x[0])
 
p = [[] for _ in range(k + 1)]
for i in range(n):
    p[t[i][1]].append(t[i][0])
 
last = 0
a = []
for i in range(1, k + 1):
    last = -p[i][0]
    for j in range(len(p[i])):
        L = [[-1, p[i][j]], (last + p[i][j] + 1) // 2, i, j * 2]
        R = [[1, -p[i][j]], p[i][j], i, j * 2 + 1]
        l[i].append(L)
        l[i].append(R)
        a.append(L)
        a.append(R)
        last = p[i][j]
 
a.sort(key=lambda x:x[1])
slope = []
inc = -k
y = 0
for i in range(1, k + 1):
    y += l[i][0][0][1]
slope.append([0, [inc, y]])
# Line[ K번째 종류 ][ K 내부 인덱스 (직선) ][ 직선 정보 / x좌표 / K번쨰 종류 / K 내부 인덱스 ][ (직선 정보라면) 기울기/y절편 ]
 
for i in range(k, len(a)):
    now = a[i]
    nx = now[0][0]
    ny = now[0][1]
    xk = now[1]
    kdx = now[2]
    inkdx = now[3]
 
    bef = l[kdx][inkdx - 1][0]
 
    inc -= bef[0]
    y -= bef[1]
 
    inc += nx
    y += ny
 
    if i != len(a) - 1 and a[i + 1][1] == xk:
        continue
 
    slope.append([xk, [inc, y]])
 
print(slope)
 
xs = [i[0] for i in slope]
for i in range(m):
    f = ip()
    idx = bisect_right(xs, f) - 1
    print(f * slope[idx][1][0] + slope[idx][1][1])

이 아래가 정답코드이다.

#include <iostream>
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
 
#define all(v) v.begin(), v.end()
#define fi first
#define se second
 
const ll INF = 10000000000;
 
vector<pair<ll, ll> > a;
ll segL[2020202];
ll segM[2020202];
ll segR[2020202];
 
ll initR(ll x, ll s, ll e){
    if (s == e){
        return segR[x] = a[s - 1].se;
    }
    ll mid = (s + e) >> 1;
    return segR[x] = min(initR(x * 2, s, mid), initR(x * 2 + 1, mid + 1, e));
}
 
ll initM(ll x, ll s, ll e){
    if (s == e){
        return segM[x] = a[s - 1].se - a[s - 1].fi;
    }
    ll mid = (s + e) >> 1;
    return segM[x] = min(initM(x * 2, s, mid), initM(x * 2 + 1, mid + 1, e));
}
 
ll initL(ll x, ll s, ll e){
    if (s == e){
        return segL[x] = a[s - 1].fi;
    }
    ll mid = (s + e) >> 1;
    return segL[x] = max(initL(x * 2, s, mid), initL(x * 2 + 1, mid + 1, e));
}
 
ll getR(ll x, ll l, ll r, ll s, ll e){
    if (e < l || r < s) return INF;
    if (l <= s and e <= r) return segR[x];
 
    ll mid = (s + e) >> 1;
    return min(getR(x * 2, l, r, s, mid), getR(x * 2 + 1, l, r, mid + 1, e));
}
 
ll getM(ll x, ll l, ll r, ll s, ll e){
    if (e < l || r < s) return INF;
    if (l <= s and e <= r) return segM[x];
 
    ll mid = (s + e) >> 1;
    return min(getM(x * 2, l, r, s, mid), getM(x * 2 + 1, l, r, mid + 1, e));
}
 
ll getL(ll x, ll l, ll r, ll s, ll e){
    if (e < l || r < s) return -INF;
    if (l <= s and e <= r) return segL[x];
 
    ll mid = (s + e) >> 1;
    return max(getL(x * 2, l, r, s, mid), getL(x * 2 + 1, l, r, mid + 1, e));
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
 
    ll n, k, m;
    cin >> n >> k >> m;
 
    int cnt[505050];
    fill(cnt, cnt + k + 1, 0);
 
    vector<pair<ll, ll> > p;
    for (int i=0; i<n; i++){
        ll le, ri;
        cin >> le >> ri;
        p.emplace_back(make_pair(le, ri));
    }
 
    sort(all(p));
 
    int l = 0;
    int r = 0;
    int c = 0;
    while (r < n){
        cnt[p[r].se] += 1;
        if (cnt[p[r].se] == 1) c += 1;
        if (c == k){
            while (cnt[p[l].se] > 1){
                cnt[p[l].se] -= 1;
                l += 1;
            }
            if (cnt[p[l].se] == 1){
                cnt[p[l].se] -= 1;
                l += 1;
            }
            c -= 1;
            a.emplace_back(make_pair(p[l - 1].fi, p[r].fi));
        }
        r += 1;
    }
 
    n = a.size();
 
    initL(1, 1, n);
    initM(1, 1, n);
    initR(1, 1, n);
 
    vector<ll> ax, ay;
 
    for (int i=0; i<n; i++){
        ax.emplace_back(a[i].fi);
        ay.emplace_back(a[i].se);
    }
 
    for (int i=0; i<m; i++){
        ll x;
        cin >> x;
        ll L = upper_bound(all(ay), x - 1) - ay.begin();
        ll R = upper_bound(all(ax), x) - ax.begin();
 
        ll ans = INF;
 
        if (R < n) ans = min(ans, getR(1, R + 1, n, 1, n) - x);
        if (L > 0) ans = min(ans, x - getL(1, 1, L, 1, n));
        if (R - L > 0) ans = min(ans, getM(1, L + 1, R, 1, n));
 
        cout << ans << endl;
    }
 
 
    return 0;
}

 

 

 

14 - 생존 신호(87.6/100)

손으로 긁음

 

 

 

15 - 선물 상자

 문제가 정말 착하다. M % N칸 간격으로 가는 칸들 중, 사탕의 최솟값 k를 가지는 칸(k가 여러 개라면 먼저 방문하는 칸)을 기준으로 앞으로는 k개, 뒤로는 (k - 1)개를 빼준다. 이걸 하나 남을 때까지 반복하면 O(N^2)에 풀린다.

n, m = mip()
t = lmip()
a = [[t[i], i, i] for i in range(n)]
 
for i in range(n, 1, -1):
    d = m % i
    if d == 0:
        d = i
    mi = [10000000000, 0]
    v = [False for _ in range(i)]
    for j in range(d, i * d + 1, d):
        if v[j % i - 1]: break
        v[j % i - 1] = True
        if a[j % i - 1][0] < mi[0]:
            mi[0] = a[j % i - 1][0]
            mi[1] = a[j % i - 1][2]
 
    f = 0
    v = [False for _ in range(i)]
    for j in range(d, i * d + 1, d):
        if v[j % i - 1]: break
        v[j % i - 1] = True
        a[j % i - 1][0] -= mi[0] - f
        if a[j % i - 1][2] == mi[1]:
            f = 1
 
    tmp = []
    for j in range(mi[1] + 1, i):
        tmp.append(a[j])
    for j in range(mi[1]):
        tmp.append(a[j])
 
    a = [[tmp[j][0], tmp[j][1], j] for j in range(len(tmp))]
 
print(a[0][1] + 1)

 

 

 

16 - 파스칼 삼각형 (0/100)

모름

 

 

 

17 - 낙하 데미지 (17/100)

O(N^2) DP로 N<=2000만 긁음