문제 A: 조건부 쌍 카운팅

분수 i/j의 소수부가 0.5 미만이 되도록 하는 (i, j) 쌍의 개수를 구하는 문제입니다. 수학적으로 변형하면:

i/j - ⌊i/j⌋ < 0.5

양변에 j를 곱하면 i - ⌊i/j⌋·j < 0.5j가 됩니다. 여기서 왼쪽 항은 나머지 연산 i % j와 동일하므로, 최종 조건은 i % j < 0.5j로 단순화됩니다.

구간 패턴 분석

고정된 j에 대해 i가 0부터 n까지 변할 때, i % j는 주기 j로 0 ~ j-1을 반복합니다. 각 주기에서 0부터 (j-1)/2까지의 값들이 조건을 만족하므로, 각 주기의 "절반"이 유효 구간이 됩니다.

차분 배열 활용

각 j에 대해 유효한 i들은 여러 개의 연속 구간으로 표현됩니다. 이를 효율적으로 처리하기 위해 차분 기법을 적용합니다.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<long long> diff(n + 2);
    
    for (int denom = 1; denom <= n; ++denom) {
        for (int start = 0; start <= n; start += denom) {
            int end = min(start + (denom - 1) / 2 + 1, n + 1);
            diff[start] += 1;
            diff[end] -= 1;
        }
    }
    
    long long cur = 0;
    for (int i = 1; i <= n; ++i) {
        cur += diff[i];
        cout << cur << " \n"[i == n];
    }
    
    return 0;
}

복잡도는 조화수 합으로 O(n log n)입니다.

문제 B: 비트 연산자 배열의 최대값과 위치

길이 n의 배열 사이에 k개의 AND(&)와 n-k-1개의 OR(|)를 배치하여 결과값을 최대화하고, 그 중 사전순으로 가장 큰 연산자 위치 배열을 찾는 문제입니다.

그리디 관찰

AND는 양쪽이 모두 1일 때만 1을 유지하므로 "까다롭고", OR은 한쪽이라도 1이면 1이 되므로 "유연합니다". 따라서 AND를 앞쪽에, OR을 뒤쪽에 배치하는 것이 유리합니다.

기본 배치: a[1] & a[2] & ... & a[k+1] | a[k+2] | ... | a[n]

50점: 이차 탐색 접근

세 번째 조건(사전순 최대)을 만족하기 위해, 뒤에서부터 각 AND의 위치를 조정합니다. 뒤쪽 AND부터 시작해 가능한 한 뒤로 이동시키면서 결과값이 변하지 않는지 확인합니다.

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

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;
    
    vector<ll> val(n + 1);
    for (int i = 1; i <= n; ++i) cin >> val[i];
    
    // 기본 배치: 앞 k개 AND, 나머지 OR
    vector<int> op(n); // 1: AND, 0: OR
    for (int i = 1; i <= k; ++i) op[i] = 1;
    
    ll target = val[1];
    for (int i = 1; i <= k; ++i) target &= val[i + 1];
    for (int i = k + 1; i < n; ++i) target |= val[i + 1];
    
    vector<int> andPos(k + 1);
    int boundary = n - 1;
    
    for (int idx = k; idx >= 1; --idx) {
        op[idx] = 0;
        int pos = boundary;
        op[pos] = 1;
        
        ll calc = val[1];
        for (int j = 1; j < n; ++j) {
            if (op[j]) calc &= val[j + 1];
            else calc |= val[j + 1];
        }
        
        while (calc != target && pos > 0) {
            swap(op[pos], op[pos - 1]);
            --pos;
            
            calc = val[1];
            for (int j = 1; j < n; ++j) {
                if (op[j]) calc &= val[j + 1];
                else calc |= val[j + 1];
            }
        }
        
        andPos[idx] = pos;
        boundary = pos - 1;
    }
    
    for (int i = 1; i <= k; ++i) {
        cout << andPos[i] << " \n"[i == k];
    }
    
    return 0;
}

100점: 선형 시간 최적화

매번 전체를 재계산하는 O(n)의 반복을 제거해야 합니다. 연산의 결합 법칙을 활용하여, 위치 이동 시 변화하는 부분만 빠르게 갱신하는 방식으로 O(n)에 도달할 수 있습니다.