본문으로 건너뛰기
SERIES · AtCoder Weekday Contest

AtCoder Weekday Contest 001

AtCoder Weekday Contest 001 풀이

2026년 7월 30일 · 3 min read


AtCoder Weekday Contest 001 풀이

A - Bacteria Growth Experiment

implementation

답은 N+1N + 1이 자명하다.

print(int(input()) + 1)

B - Exam Passers

implementation

[l,r][l, r]구간 사이에 있는 얘들만 넣고 정렬

int n,l,r;
 
void solve(){
	ri(n, l, r);
	vp v;
	for(int i = 0; i < n; i++){
		int x; ri(x);
		if(l <= x and x <= r) v.pb({x, i + 1});
	}
	if(v.empty()){
		po(-1);
		return;
	}
	sort(all(v), [&](auto& a, auto& b){
		return a.fi == b.fi ? a.se < b.se : a.fi > b.fi;
	});
	po(v[0].se);
}

C - Discount Coupon

greedy

내림차순 정렬 이후 NKN - K개만 보기

int n,k,res;
 
void solve(){
	ri(n, k);
	vi v(n); ri(v); sort(rall(v));
	for(int i = k; i < n; i++) res += v[i];
	po(res);
}

D - Merchant on the Highway

dp

dp[i][c]dp[i][c] : ii번째 원소를 반드시 선택했고, 총 비용이 cc일 때 만들 수 있는 최대 가치

int n,m,k,A[222], B[222];
 
auto solve = [](){
    ri(n, m, k);
    for(int i = 1; i <= n; i++) ri(A[i], B[i]);
    vector<vector<int>> dp(n + 1, vi(m + 1, -inf));
    int res = -inf;
    for(int i = 1; i <= n; i++){
        dp[i][B[i]] = max<int>(dp[i][B[i]], A[i]);
        for(int j = max<int>(1, i - k); j < i; j++){
            for(int c = 0; c + B[i] <= m; c++){
                if(dp[j][c] == -inf) continue;
                dp[i][c + B[i]] = max<int>(dp[i][c + B[i]], dp[j][c] + A[i]);
            }
        }
        for(int c = 0; c <= m; c++) res = max<int>(res, dp[i][c]);
    }
    po(res);
};

E - Temperature Fluctuation Range

segment_tree

구간 최대, 구간 최소를 지원하는 세그를 짜면 O(nlogn)O(nlogn)에 해결 가능

struct mxsegtree{
    const int sz = 1 << 18;
    vector<int> tree;
    mxsegtree():tree(sz << 1, -inf){}
    void U(int i, int val){
        --i |= sz; tree[i] = val;
        while(i >>= 1) tree[i] = max<int>(tree[i << 1], tree[i << 1 | 1]);
    }
    int Q(int l, int r){
        int res = -inf;
        --l |= sz; --r |= sz;
        while(l <= r){
            if(l & 1) res = max<int>(res, tree[l++]);
            if(~r & 1) res = max<int>(res, tree[r--]);
            l >>= 1, r >>= 1;
        }
        return res;
    }
} mxseg;
 
struct mnsegtree{
    const int sz = 1 << 18;
    vector<int> tree;
    mnsegtree():tree(sz << 1, inf){}
    void U(int i, int val){
        --i |= sz; tree[i] = val;
        while(i >>= 1) tree[i] = min<int>(tree[i << 1], tree[i << 1 | 1]);
    }
    int Q(int l, int r){
        int res = inf;
        --l |= sz; --r |= sz;
        while(l <= r){
            if(l & 1) res = min<int>(res, tree[l++]);
            if(~r & 1) res = min<int>(res, tree[r--]);
            l >>= 1, r >>= 1;
        }
        return res;
    }
} mnseg;
 
int n,k;
 
auto solve = [](){
    ri(n, k);
    for(int i = 1; i <= n; i++){
        int x; ri(x);
        mxseg.U(i, x); mnseg.U(i, x);
    }
    int mx = -inf;
    for(int i = 1; i + k - 1 <= n; i++){
        int l = i, r = i + k - 1;
        mx = max<int>(mx, mxseg.Q(l, r) - mnseg.Q(l, r));
    }
    po(mx);
};
SERIES1 / 16회차

AtCoder Weekday Contest

  1. 1.AtCoder Weekday Contest 001지금 읽는 중
  2. 2.AtCoder Weekday Contest 005
  3. 3.Atcoder Weekday Contest 009
  4. 4.Atcoder Weekday Contest 015
  5. 5.Atcoder Weekday Contest 017

관련 글