AtCoder ABC 256 풀이

https://atcoder.jp/contests/abc256/tasks

Tasks - Tokio Marine & Nichido Fire Insurance Programming Contest 2022（AtCoder Beginner Contest 256)

 

A.

2^n을 출력해줍니다. 1<<n으로 간단히 표현할 수 있습니다.

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

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n; cin >> n;
    cout << (1 << n);
}

 

 

B. 

0에다 놓고 a[i]씩 더해가며 인덱스에서 벗어나는 것의 개수를 출력해주는 문제입니다.

현재 배열 cur과 다음배열 nxt를 만들어놓고 인덱스 3을 벗어나지 않으면 nxt배열에 채워주고

인덱스 3을 벗어나면 답을 1 증가시켜주면 됩니다. 

#include<bits/stdc++.h>
using namespace std;
int n, a[111];
vector<bool>cur(4);

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> a[i];
    int p = 0;
    for (int i = 1; i <= n; i++) {
        vector<bool> nxt(4);
        cur[0] = 1;
        for (int j = 0; j <= 3; j++) {
            if (cur[j]) {
                if (j + a[i] <= 3) {
                    nxt[j + a[i]] = 1;
                }
                else  p++;                                  
            }
        }
        cur = nxt;
    }
    cout << p;
}

 

 

C.

교육적인 문제입니다. naive하게 a1~a9를 반복문으로 돌린다면 O(N^9) 입니다. 

그런데 양 행과 열의 합이 주어져 있습니다. 따라서 왼쪽 위부터 2*2 행렬만 결정해준다면, 

나머지 5개 값은 O(1)에 자동결정됩니다. 따라서 시간복잡도를 O(N^4)로 줄일 수 있습니다. 

나머지 값들이 모두 양수이면서 조건을 만족한다면 답을 1 증가시켜주면 됩니다. 

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,n) for(int i=1;i<=n;i++)

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int h1, h2, h3, w1, w2, w3;
    cin >> h1 >> h2 >> h3;
    cin >> w1 >> w2 >> w3;
    int ans = 0;
    FOR(a, 30)FOR(b, 30)FOR(d, 30)FOR(e, 30) {
        if (a + b >= h1) continue;
        if (a + d >= w1) continue;
        if (d + e >= h2) continue;
        if (b + e >= w2) continue;
        int c = h1 - (a + b);
        int f = h2 - (d + e);
        int g = w1 - (a + d);
        int h = w2 - (b + e);
        if (w3 - (c + f) == h3 - (g + h) && g + h < h3 && c + f < w3) {
            ans++;
        }
    }
    cout << ans << '\n';
}

 

 

D.

겹치는 선분들을 merge 하여 합집합을 출력하는 문제입니다. 

우선 (L,R)을 정렬합니다. 그 후 R[i]<L[i+1]이라면 i+1번째부터 새로운 선분이 시작됩니다. 

따라서 구간 시작점과 끝점을 L[i+1], R[i+1] 로 바꿔줍니다. 

R[i]>=L[i+1]이라면 선분이 겹친다는 의미이므로, 구간끝점만 최댓값으로 업데이트해주면 됩니다. 

#include<bits/stdc++.h>
using namespace std;
pair<int, int>a[200005];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i].first >> a[i].second;
    }
    a[n] = { 1e9,1e9 };
    sort(a, a + n);
    auto [s, e] = a[0];
    for (int i = 0; i < n; i++) {
        if (e < a[i + 1].first) {
            cout << s << " " << e << '\n';
            tie(s, e) = a[i + 1];
        }
        else {
            e = max(e, a[i + 1].second);
        }
    }
}

 

 

E.

i보다 x[i]가 먼저 나오면 가중치가 생깁니다. 이 때 적절히 배열하여 모두 방문할 때 가중치 합이 최소가 

되게 하는 문제입니다. x[i]에서 i로 그래프를 연결해줍시다.

 

관찰 1. 그래프 전체에 사이클이 없다면 답은 0입니다. 

자명합니다. 방향 그래프에서 역순으로 결정해주면 0이 됩니다.

 

관찰 2. 사이클이 있다면 그 사이클의 최소 가중치를 항상 택할 수 있습니다.

사이클이 생긴다면 우선 사이클 내에서 반드시 가중치가 더해질 수 밖에 없습니다. 그럼 항상 최소인 

가중치를 선택할 수 있는지 봐야하는데 가능함을 쉽게 알 수 있습니다. 

 

관찰 3. 따라서 사이클 컴포넌트들이 있을 때 답은 사이클 내의 최소가중치의 합이 됩니다. 

사이클 여부는 유니온 파인드로 판단하고 사이클을 순회해주면 됩니다. 여기서 구현할 때 주의점이 있는데

처음부터 i와 x[i]를 유니온시키고 사이클 컴포넌트를 더해주는 방식은 모든 사이클 요소마다 최소 가중치를 

더해주므로 안됩니다. 따라서 순회 1번을 하면서 연결시켜나가면 마지막에 사이클 요소가 끝날 때 1번만

값을 더해줄 수 있습니다. 구현과 아이디어 모두 어려운 문제였습니다.  

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, x[200005], c[200005], par[200005];

int find(int x) {
    return !~par[x] ? x : par[x] = find(par[x]);
}

void uni(int x, int y) {
    x = find(x), y = find(y);
    if (x != y) par[y] = x;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    memset(par, -1, sizeof(par));
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> x[i];
    for (int i = 1; i <= n; i++) cin >> c[i];
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        if (find(i) != find(x[i])) {
            uni(i, x[i]);
            continue;
        }
        int u = i;
        ll cyc_min = c[i];
        while (1) {
            u = x[u];
            if (u == i) break;
            cyc_min = min(cyc_min, c[u]);
        } 
        ans += cyc_min;
    }
    cout << ans << '\n';
}

 

 

F.

식정리+세그트리 문제입니다.

D[x]를 A[i]의 식으로 정리하면, 

D[x]=1/2*(∑x^2*A[x]-(2x+3)*∑(xA[x])+(x+1)(x+2)*∑A[x]) 임을 알 수 있습니다. 

여기서  ∑(x^2*A[x])와 ∑(xA[x]), ∑A[x]를 업데이트해주고 합을 구해주는건 펜윅트리로 할 수 있습니다. 

수가 매우 크므로 나머지 연산에 주의합니다. 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MAX = 200005, mod = 998244353;
ll n, q, v, a[MAX], X[MAX], Y[MAX], Z[MAX];
const ll inv = (1 + mod) / 2;

struct fenwick {
    void upd(ll tree[], int i, ll v) {
        while (i < MAX) {
            tree[i] += v;
            tree[i] %= mod;
            i += i & -i;
        }
    }
    ll sum(ll tree[], int i) {
        ll ret = 0;
        while (i) {
            ret += tree[i];
            ret %= mod;
            i -= i & -i;
        }
        return ret;
    }
}fw;

void update(ll i, ll v) {
    while (v < 0) v += mod;
    fw.upd(X, i, v);
    fw.upd(Y, i, i * v % mod);
    fw.upd(Z, i, i * i % mod * v % mod);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> q;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        update(i, a[i]);
    }
    while (q--) {
        ll op, i, v;
        cin >> op >> i;
        if (op & 1) {
            cin >> v;
            update(i, v - a[i]);
            a[i] = v;
        }
        else {
            ll ans = fw.sum(Z, i);
            ans += (i + 1) * (i + 2)% mod * fw.sum(X, i) % mod;
            ans %= mod;
            ans = (ans - (2 * i + 3) * fw.sum(Y, i)% mod + mod) % mod;
            cout << ans * inv % mod << '\n';
        }
    }
}

 

 

G.

풀이 예정

 

 

Ex.

2,3번은 레이지 세그로 쉽게 됩니다. 1번 쿼리를 어떻게 처리해야 할까요? 

관찰 :  1번 쿼리를 시행하면 값이 절반 이하로 줄어듭니다. 

따라서 log(1e5)이내에 값은 0이 됩니다. 따라서 시행을 할수록 같은 값이 점점 많아지게 됩니다. 

만약 어떤 구간이 모든 수가 같다면 그 부분은 레이지 세그먼트 트리 중에 처리해줄 수 있습니다. 

값이 차이가 난다면 내림때문에 같은 값이 갱신되지 않는 경우가 없기 때문입니다. 

따라서 쿼리1에서는 기존 레이지 세그 + min=max 인 경우까지 제한을 걸어서 쿼리를 수행해주면 됩니다.

따라서 최악의 시간복잡도는 O((N+QlogN)*log1e5)로 시간내에 풀 수 있습니다. 

세그트리는 min, max, sum을 모두 관리하도록 짜주면 됩니다. 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 500005;
struct Node {
	ll mn, mx, sum;
}tree[4 * MAX];
ll n, Q, a[MAX];

Node merge(Node a, Node b) {
	Node c;
	c.mn = min(a.mn, b.mn);
	c.mx = max(a.mx, b.mx);
	c.sum = a.sum + b.sum;
	return c;
}

struct segment_tree {
	ll lazy[4 * MAX];
	void propa(int node, int s, int e) {
		if (lazy[node] != -1) {
			tree[node].sum = 1LL * (e - s + 1) * lazy[node];
			tree[node].mn = lazy[node];
			tree[node].mx = lazy[node];
			if (s != e) {
				lazy[2 * node] = lazy[node];
				lazy[2 * node + 1] = lazy[node];
			}
			lazy[node] = -1;
		}
	}
	void upd1(int node, int s, int e, int qs, int qe, ll v) {
		propa(node, s, e);
		if (s > qe || e < qs) return;
		if (qs <= s && e <= qe && tree[node].mn == tree[node].mx) {
			lazy[node] = tree[node].mn / v;
			propa(node, s, e);
			return;
		}
		int m = (s + e) >> 1;
		upd1(2 * node, s, m, qs, qe, v);
		upd1(2 * node + 1, m + 1, e, qs, qe, v);
		tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
	}
	void upd2(int node, int s, int e, int qs, int qe, ll v) {
		propa(node, s, e);
		if (s > qe || e < qs) return;
		if (qs <= s && e <= qe) {
			lazy[node] = v;
			propa(node, s, e);
			return;
		}
		int m = (s + e) >> 1;
		upd2(2 * node, s, m, qs, qe, v);
		upd2(2 * node + 1, m + 1, e, qs, qe, v);
		tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
	}
	ll query(int node, int s, int e, int qs, int qe) {
		propa(node, s, e);
		if (s > qe || e < qs) return 0;
		if (qs <= s && e <= qe) return tree[node].sum;
		int m = (s + e) >> 1;
		return query(2 * node, s, m, qs, qe) + query(2 * node + 1, m + 1, e, qs, qe);
	}
}seg;

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> Q;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		seg.upd2(1, 1, n, i, i, a[i]);
	}
	while (Q--) {
		int op, L, R;
		ll x, y;
		cin >> op >> L >> R;
		if (op == 1) {
			cin >> x;
			seg.upd1(1, 1, n, L, R, x);
		}
		if (op == 2) {
			cin >> y;
			seg.upd2(1, 1, n, L, R, y);
		}
		if (op == 3) {
			cout << seg.query(1, 1, n, L, R) << '\n';
		}
	}
}