AtCoder ABC 365 문제 A-E 상세 해설 및 구현 전략

A - 윤년 계산

문제 요약

입력으로 받은 연도 n을 기준으로 해당 연도의 일수가 365 일인지 366 일인지 판단해야 합니다.

해결책

윤년 여부를 판별하는 논리식을 적용하면 됩니다. 일반적으로 다음 규칙이 성립합니다:

  • 4 로 나누어 떨어지지 않는 경우 평년입니다.
  • 400 으로 나누어 떨어지는 경우 윤횔입니다.
  • 100 으로 나누어 떨어지지 않으면서 4 로 나누어 떨어지는 경우도 윤횔입니다.

위의 조건들을 조합하여 출력 값을 결정하면 됩니다.

코드 구현

#include<iostream>
#include<vector>
using namespace std;

void solve() {
    int year;
    if (!(cin >> year)) return;

    int days = 365;
    // 1. 400 의 배수인 경우
    if (year % 400 == 0) {
        days = 366;
    } 
    // 2. 100 은 배수지만 400 은 아님 (이 경우 아래로 안감)
    else if (year % 100 == 0) {
        days = 365;
    }
    // 3. 4 의 배수이지만 100 은 아님
    else if (year % 4 == 0) {
        days = 366;
    }

    cout << days << "\n";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

B - 두 번째로 큰 값

문제 요약

정수 배열 $a_n$ 이 주어졌을 때, 가장 큰 수를 제외한 나머지 수들 중 최댓값인 "두 번째 큰 값"의 인덱스를 구하는 문제입니다.

해결책

한 번의 순회 (Single Pass) 를 통해 현재까지 발견된 최댓값과 두 번째 최댓값을 유지하면서 진행하면 $O(N)$ 시간에 해결할 수 있습니다.

  • 현재 요소가 기존 최댓값보다 크면: 이전 최댓값을 두 번째 최댓값으로 올리고, 현재 요소를 새로운 최댓값으로 설정합니다.
  • 현재 요소가 최댓값보다는 작지만 두 번째 최댓값보다는 크면: 두 번째 최댓값과 그 위치를 업데이트합니다.

코드 구현

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

    vector<long long> nums(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> nums[i];
    }

    long long first_val = nums[1];
    long long second_val = -1e18; 
    
    int first_idx = 1;
    int second_idx = -1;

    for (int i = 2; i <= n; ++i) {
        if (nums[i] > first_val) {
            second_val = first_val;
            second_idx = first_idx;
            
            first_val = nums[i];
            first_idx = i;
        } else if (nums[i] > second_val) {
            second_val = nums[i];
            second_idx = i;
        }
    }

    cout << second_idx << "\n";
    return 0;
}

C - 이동 비용 합계

문제 요약

$x$라는 변수를 사용하여 모든 항목에 대해 $\min(A_i, x)$ 의 합이 $M$ 이하가 되도록 하는 $x$ 의 최댓값을 구합니다. 만약 충분히 큰 $x$ 에도 조건이 만족된다면 무한대로 출력합니다.

해결책

함수 $f(x) = \sum \min(A_i, x)$ 는 $x$ 에 대해 단조 증가하는 특성을 가집니다. 따라서 $x$ 를 이진 탐색 (Binary Search) 하여 조건을 만족하는 최대 값을 찾을 수 있습니다.

  1. 우선 $x$ 가 매우 클 때 ($10^{17}$ 등) 합이 $M$ 이하인지 확인하여 무한대 여부와 무관한 경우를 처리합니다.
  2. 아니라면 범위를 $[0, M]$ 로 잡고 이진 탐색을 수행합니다.
  3. 검증 함수 (check function) 에서 주어진 $mid$ 에 대해 합계를 계산하여 조건을 체크합니다.

코드 구현

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int n;
long long m_limit;
vector<long long> costs;

bool is_valid(long long val) {
    long long total_cost = 0;
    for (int i = 0; i < n; ++i) {
        total_cost += min(costs[i], val);
        if (total_cost > m_limit) return false;
    }
    return total_cost <= m_limit;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> n >> m_limit)) return 0;

    costs.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> costs[i];
    }

    if (is_valid(200000000000000000LL)) {
        cout << "infinite\n";
        return 0;
    }

    long long low = 0, high = m_limit;
    long long ans = 0;

    while (low <= high) {
        long long mid = low + (high - low) / 2;
        if (is_valid(mid)) {
            ans = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    cout << ans << "\n";
    return 0;
}

D - 가위바위보 3

문제 요약

상대가 정해진 순서로 손 모양 ($S, P, R$) 을 낼 때, 상대방은 절대 패하지 않으며 연속된 두 번의 출수는 같을 수 없습니다. 이때 내가 얻을 수 있는 승리 횟수의 최댓값을 구해야 합니다.

해결책

이 문제는 전역적인 제약조건 때문에 단순히 Greedy 로 접근하기 어려우며, 상태 전이가 존재하므로 동적 계획법 (DP) 을 사용해야 합니다.

  • 상태 정의: $dp[i][0]$ 은 $i$ 번째 라운드에서 내가 비겼을 때의 최대 승패 횟수, $dp[i][1]$ 은 $i$ 번째 라운드에서 내가 이겼을 때의 값입니다.
  • 전이: 현재 선택한 손모양이 직전 회차의 손모양과 겹치지 않아야 합니다.
  • 이기는 행: 상대의 $S$ 에서는 내 $P$, $R$ 에서는 내 $S$, $P$ 에서는 내 $R$ 입니다.

코드 구현

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    string opp_moves;
    cin >> n >> opp_moves;

    // dp[i][0]: non-win (win tie) count, dp[i][1]: win count
    vector<vector<int>> dp(n, vector<int>(2, -1));

    // Base case initialization is handled by transitions mostly
    // We treat the first move specially or initialize carefully
    
    int current_tie_move = -1; 
    int current_win_move = -1;
    
    auto get_tie = [&](char op) { return op; };
    auto get_win = [&](char op) {
        if (op == 'S') return 'P';
        if (op == 'P') return 'R';
        return 'S';
    };

    for (int i = 0; i < n; ++i) {
        char opponent = opp_moves[i];
        
        // Possible moves we can make now to TIE or WIN
        char tie_move = get_tie(opponent);
        char win_move = get_win(opponent);

        int prev_tie_score = 0;
        int prev_win_score = -1e9;

        if (i > 0) {
             // Check previous state validity implicitly via logic or initialized values
             // Here we simply assume accessing i-1
             // But for code simplicity relative to original, let's stick to loop logic
        }

        // Initialize base state logic manually inside loop or separate
        if (i == 0) {
            dp[0][0] = 0;
            dp[0][1] = 1; 
        } else {
            // Logic derived from previous states
            // If we want to tie now with `tie_move`:
            // Previous could have been Tie (different move) or Win (different move)
            
            // Determine scores if we pick TIE move
            int t_score = -1e9;
            if (i > 0) {
                if (current_tie_move != tie_move && dp[i-1][0] >= 0) 
                    t_score = max(t_score, dp[i-1][0]);
                if (current_win_move != tie_move && dp[i-1][1] >= 0)
                    t_score = max(t_score, dp[i-1][1]);
            }
            
            // Determine scores if we pick WIN move (+1 score)
            int w_score = -1e9;
            if (i > 0) {
                if (current_tie_move != win_move && dp[i-1][0] >= 0)
                    w_score = max(w_score, dp[i-1][0] + 1);
                if (current_win_move != win_move && dp[i-1][1] >= 0)
                    w_score = max(w_score, dp[i-1][1] + 1);
            }
            
            // Update global prev moves for next iteration
            current_tie_move = tie_move;
            current_win_move = win_move;
        }
        
        // Correcting implementation to match previous flow properly for safety
        // Resetting approach for clarity:
    }
    
    // Simplified logic rewrite matching core requirement
    
    // Re-writing main DP logic cleanly
    fill(dp.begin(), dp.end(), vector<int>(2, -1000000000));
    
    // Initial State handling
    // Round 0
    if (opp_moves[0] == 'S') { /* tie=S, win=P */ }
    else if (opp_moves[0] == 'R') { /* tie=R, win=S */ }
    else { /* tie=P, win=R */ }
    
    dp[0][0] = 0;
    dp[0][1] = 1;

    // Tracking last played moves
    // 0: Rock(S), 1: Paper(P), 2: Scissor(R) mapping
    // Using direct char comparison is easier with original logic style but renamed vars
    
    char last_non_win = opp_moves[0]; 
    char last_win = (opp_moves[0]=='S'?'P':(opp_moves[0]=='P'?'R':'S'));

    for(int i=1; i

E - 이산 적분 (Xor Sigma)

문제 요약

주어진 배열 $A_N$ 에 대해, 모든 서브배열 $A_{i+1} \dots A_j$ 의 XOR 합을 모두 더한 결과 값을 구해야 합니다.

해결책

이 문제를 해결하기 위해서는 XOR 앞쪽 합 (Prefix XOR) 의 개념을 활용해야 합니다.区间 $[l, r]$ 의 XOR 합은 $Prefix[r] \oplus Prefix[l-1]$ 로 계산됩니다.

원래 식은 모든 쌍 $(i, j)$ 에 대한 XOR(prefix difference) 의 합입니다. 이를 확장하면, 모든 원소들의 XOR 합을 구하고, 서로 다른 prefix pair 들 간의 XOR 합을 구하여 결합한 후, 원래 단일 원소 $A_i$ 들의 총합을 빼주는 방식으로 접근할 수 있습니다.

또는 각 비트 별 기여도를 계산하는 방법으로도 최적화할 수 있습니다. 특정 비트 위치 $k$ 에서 1 인 숫자들의 개수를 세어 조합 수학을 적용하거나, 직접 구간 XOR 합들을 모두 계산하여 누적하는 방식입니다.

코드 구현

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

    vector<long long> b(n + 1);
    vector<long long> pre_xor(n + 1, 0);

    for (int i = 1; i <= n; ++i) {
        cin >> b[i];
        pre_xor[i] = pre_xor[i-1] ^ b[i];
    }

    // Calculate sum of all single elements (to subtract later)
    long long initial_sum_elements = 0;
    for (int i = 1; i <= n; ++i) initial_sum_elements += b[i];

    // The result consists of: 
    // 1. Sum of all prefix XORs themselves
    // 2. Sum of pairwise XORs between prefix sums
    
    long long final_res = 0;
    
    // Part 1: Sum of individual prefix XORs
    for (int i = 1; i <= n; ++i) {
        final_res += pre_xor[i];
    }

    // Part 2: Sum of pairwise XORs (similar to original "Two XOR" problem logic)
    // Count set bits for each position across all prefix sums
    vector<int> bit_counts(20, 0);
    long long mx_bits = 0;
    
    for (int i = 1; i <= n; ++i) {
        long long val = pre_xor[i];
        for(int k=0; k<20; ++k){
            if ((val >> k) & 1) bit_counts[k]++;
        }
    }

    for (int k = 0; k < 20; ++k) {
        int count_ones = bit_counts[k];
        long long count_zeros = n - count_ones;
        // Contribution to pairwise XOR sum: ones * zeros * 2^k
        final_res += (long long)count_ones * count_zeros * (1LL << k);
    }

    // Subtract the sum of original elements as derived from formula logic
    final_res -= initial_sum_elements;

    cout << final_res << "\n";
    return 0;
}

태그: C++ atcoder-abc binary-search dynamic-programming xor-prefix-sum

8월 16일 16:02에 게시됨

인기 태그

©2026 괴물 클럽