Atcoder Weekday Contest 5

2/21/2026 · 3 min read

PSAtcoder

Atcoder Weekday 005 풀이

오랜만에 Atcoder를 풀어봤는데 새로운 콘테스트가 생겨서 한번 풀어봤다. 아마 매일 할 수 있으면 할 듯?

대회 링크는 아래와 같다

link : https://atcoder.jp/contests/awc0005

1. A - Reward of Multiples

그냥 구현해주면 된다.

int n,k;
 
void solve(){
	ri(n, k);
	int res = 0;
	for(int i = 0; i < n; i++){
		int x; ri(x);
		res += (x % k == 0 ? x : 0);
	}
	po(res);
}

2. B - Updating the Report Card

이것도...그냥 구현해주면 된다.

int n, m, k, res;
 
void solve(){
	ri(n, m, k);
	vi v(n + 1);
	for(int i = 1; i <= n; i++) ri(v[i]);
	while(m--){
		int a,b; ri(a, b);
		v[a] = b;
	}
	for(int i = 1; i <= n; i++) res += (v[i] < k);
	po(res);
}

3. C - Staircase-Shaped Flower Bed

그냥 간단 그리디

int n, k,res;
 
void solve(){
	ri(n, k);
	vi v(n); ri(v);
	vi L(n), R(n);
	L[0] = v[0];
	for(int i = 1; i < n; i++){
		L[i] = max<int>(v[i], L[i - 1] - k);
	}
	R[n - 1] = v[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        R[i] = max(v[i], R[i + 1] - k);
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int B = max<int>(L[i], R[i]);
        ans += (B - v[i]);
    }
	po(ans);
}

4. D - Splitting Delivery Packages

간단하게 파라메트릭 서치로 풀린다. 결정문제를 잘 잡아보자.

int n,k,S;
 
void solve(){
	ri(n, k);
	vi v(n); for(auto& i : v) ri(i),S += i;
	auto check = [&](const int mid) -> bool{
		int su = 0,cnt = 0;
		for(int i = 0; i < n; i++){
			su += v[i];
			if(su >= mid){
				cnt++;
				su = 0;
			}
		}
		return cnt >= k;
	};
	int L = 0,R = S + 1;
	while(L + 1 < R){
		int mid = L + R >> 1;
		if(check(mid)) L = mid;
		else R = mid;
	}
	po(L);
}

5. E - Mountain Height Survey

최대값 세그를 이용하면 쉽게 풀린다. ~~걍 이정도면 세그 구현문제 아니냐~~

const int bias = 1 << 17;
vector<int> T(bias << 1, -INF);
 
void update(int i, int val){
	--i |= bias; T[i] = val;
	while(i >>= 1) T[i] = max<int>(T[i << 1], T[i << 1 | 1]);
}
 
int query(int l, int r){
	int lv = -INF, rv = -INF;
	--l |= bias; --r |= bias;
	while(l <= r){
		if(l & 1) lv = max<int>(T[l++], lv);
		if(~r & 1) rv = max<int>(rv, T[r--]);
		l >>= 1, r >>= 1;
	}
	return max<int>(lv, rv);
}
 
int n,q;
 
void solve(){
	ri(n, q);
	for(int i = 1; i <= n; i++){
		int x; ri(x); update(i, x);
	}
	while(q--){
		int a, b; ri(a, b);
		if(a > b) swap(a, b);
		po(query(a, b));
	}
}