solved.ac Grand Arena #1

# 양말 짝 맞추기

## 풀이 1

홀수개 쓰인 숫자가 있다면, 해당 숫자를 가지고 짝을 모두 만들 수 없고, 반드시 하나가 남게 됩니다.

### 코드 (C++)

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

int main()
{
    vector<int> cnt(10);
    for (int i = 0; i < 5; i++)
    {
        int Ai;
        cin >> Ai;
        cnt[Ai]++;
    }
    for (int i = 0; i < 10; i++)
        if (cnt[i] % 2 == 1)
            cout << i << endl;
}
```

### 코드 (Python)

```python
def main():
    cnt = [0] * 10
    for i in range(5):
        Ai = int(input())
        cnt[Ai] += 1

    for i in range(10):
        if cnt[i] % 2 == 1:
            print(i)


if __name__ == '__main__':
    main()
```

## 풀이 2

[XOR(비트간 배타적 논리합)](https://ko.wikipedia.org/wiki/%EB%B0%B0%ED%83%80%EC%A0%81_%EB%85%BC%EB%A6%AC%ED%95%A9#%EB%B9%84%ED%8A%B8%EA%B0%84_%EB%B0%B0%ED%83%80%EC%A0%81_%EB%85%BC%EB%A6%AC%ED%95%A9) 연산 $\oplus$ 의 성질은 다음과 같습니다.

- 교환법칙: $a \oplus b = b \oplus a$
- 결합법칙: $a \oplus (b \oplus c) = (a \oplus b) \oplus c$
- 항등원: $a \oplus 0 = a$
- 자기 자신이 역원: $a \oplus a = 0$

XOR의 성질에 의해, 같은 수를 두 번 XOR하면 해당 수가 사라지게 됩니다. 즉, 유일하게 쌍을 만들지 못하는 수만 찾기 위해서는 입력으로 주어지는 모든 수를 XOR하면 됩니다.

### 코드 (C++)

```cpp
#include <iostream>
using namespace std;

int main()
{
    int ans = 0;
    for (int i = 0; i < 5; i++)
    {
        int Ai;
        cin >> Ai;
        ans ^= Ai;
    }
    cout << ans << endl;
}
```

### 코드 (Python)

```python
def main():
    ans = 0
    for i in range(5):
        Ai = int(input())
        ans ^= Ai

    print(ans)


if __name__ == '__main__':
    main()
```

# 끝말잇기

## 풀이 1

`?` 가 쓰인 위치를 각 $A_1, \cdots, A_M$ 으로 바꾼 이후에 올바른 끝말잇기 기록인지 확인합니다. $i$번째 문자열의 끝 문자와 $i+1$번째 문자열의 시작 문자가 같은지 확인하고, 중복된 문자열이 없는지 확인합니다.


### 코드 (C++)

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

bool ok(vector<string> S)
{
    int N = S.size();
    for (int i = 0; i < N; i++)
        for (int j = 0; j < i; j++)
            if (S[i] == S[j])
                return false;
    for (int i = 0; i < N - 1; i++)
        if (S[i].back() != S[i + 1].front())
            return false;
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    vector<string> S(N);
    for (auto &x : S)
        cin >> x;

    int q = find(S.begin(), S.end(), "?") - S.begin();
    int M;
    cin >> M;
    for (int i = 0; i < M; i++)
    {
        cin >> S[q];
        if (ok(S))
            cout << S[q] << endl;
    }
}
```

### 코드 (Python)

```python
def ok(S):
    N = len(S)
    for i in range(N):
        for j in range(i):
            if S[i] == S[j]:
                return False
    for i in range(N - 1):
        if S[i][-1] != S[i + 1][0]:
            return False
    return True


def main():
    N = int(input())
    S = [input() for _ in range(N)]

    q = S.index("?")

    M = int(input())
    for _ in range(M):
        S[q] = input()
        if ok(S):
            print(S[q])


if __name__ == "__main__":
    main()
```

## 풀이 2

끝말잇기 기록에서 대체되는 것이 `?` 밖에 없다는 점을 참고합시다. `?` 와 관련 있는 부분만 신경을 써서 구현해줍시다.

- 답은 `?` 이전 문자열의 마지막 문자로 시작해야합니다.
- 답은 `?` 다음 문자열의 처음 문자로 끝나야합니다.
- 답은 끝말잇기 기록의 문자열로 등장하지 않아야 합니다.

### 코드 (C++)

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    vector<string> S(N);
    for (auto &x : S)
        cin >> x;

    int q = find(S.begin(), S.end(), "?") - S.begin();
    int M;
    cin >> M;
    for(int i=0; i<M; i++)
    {
        string a;
        cin >> a;
        if (find(S.begin(), S.end(), a) != S.end())
            continue;
        if (q != 0 && S[q - 1].back() != a.front())
            continue;
        if (q != N - 1 && a.back() != S[q + 1].front())
            continue;
        cout << a << endl;
    }
}
```

### 코드 (Python)

```python
def main():
    N = int(input())
    S = [input() for _ in range(N)]

    q = S.index("?")

    M = int(input())
    for _ in range(M):
        a = input()
        if a in S:
            continue
        if q != 0 and S[q - 1][-1] != a[0]:
            continue
        if q != N - 1 and a[-1] != S[q + 1][0]:
            continue
        print(a)


if __name__ == "__main__":
    main()
```


# 게리맨더링

## 풀이 1

$0$은 합에 아무런 영향도 끼치지 않으므로 무시합니다. 수를 왼쪽부터 차례대로 살펴보면서, 수를 이전 구간에 포함시킬지 아니면 새로운 구간으로 만들지를 생각해봅시다.

- $A_i$가 양수인 경우, 해당 수를 추가해서 구간의 합이 $0$ 이하였다가 $0$ 초과가 되는 경우를 제외하고는, $A_i$로 시작되는 새로운 구간으로 나누는 것이 이득입니다.
- $A_i$가 음수인 경우, 해당 수를 추가해서 구간의 합이 $0$ 초과였다가 $0$ 이하가 되는 경우를 제외하고는, $A_i$를 이전 구간에 포함시키는게 이득입니다.

이렇게 구간을 나눈 이후에 최종적으로 양수인 구간이 음수인 구간보다 많은지를 판단해서 출력해줍니다.

### 코드 (C++)

```cpp
#include <cinttypes>
#include <iostream>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        int N;
        cin >> N;
        int range_diff = 0;
        int64_t sum = 0;
        auto cut = [&]()
        {
            if (sum < 0)
                range_diff--;
            if (sum > 0)
                range_diff++;
            sum = 0;
        };
        for (int i = 0; i < N; i++)
        {
            int a;
            cin >> a;
            if ((sum > 0) + (a > 0) + (sum + a <= 0) >= 2)
                cut();
            sum += a;
        }
        cut();

        cout << (range_diff >= 1 ? "YES" : "NO") << '\n';
    }
}
```

### 코드 (Python)

```python
import sys


def solve(A):
    r = s = 0

    def cut():
        nonlocal r, s
        if s > 0:
            r += 1
        if s < 0:
            r -= 1
        s = 0

    for a in A:
        if (s > 0) + (a > 0) + (s + a <= 0) >= 2:
            cut()
        s += a
    cut()

    return r >= 1


def input(): return sys.stdin.readline().rstrip()


def main():
    for _ in range(int(input())):
        N = input()
        *A, = map(int, input().split())
        print("YES" if solve(A) else "NO")


if __name__ == '__main__':
    main()

```

## 풀이 2

$D_i$ 를 $A_1, \cdots, A_i$ 까지 보았을 때 양수인 구간의 개수에서 음수인 구간의 개수를 뺀 것의 최댓값이라고 합시다.

- $D_0 = 0$ 

- $D_i = \max_{0 \le j < i} D_j + {\mathrm{sgn}}(A_{j+1} + \cdots + A_i)$

와 같은 방식으로 동적계획법을 세울 수 있습니다. 여기서 ${\mathrm {sgn}(x)}$ 는 $x$가 양수이면 $+1$, 음수이면 $-1$, $0$이면 $0$입니다.

이제, $A_1 + \cdots + A_i = S_i$, 그리고 $\mathrm{sgn}$ 의 값에 따라서 나눠주면 다음과 같은 동적계획법 식이 됩니다.

- $D_0 = 0$
- $D_i = \max_{0 \le j < i}\left[\max_{S_i < S_j}(D_j + 1), \max_{S_i=S_j} (D_j), \max_{S_i > S_j}(D_j-1) \right]$

이는 좌표압축과 세그먼트트리를 이용해서 구현할 수 있습니다.

### 코드 (C++)

```
<준비중>
```

### 코드 (Python)

```
<준비중>
```

# Same Range

## 풀이

$\min(A_i, \cdots, j) = \min(B_i, \cdots, B_j) = x$ 인 최소의 $(i, j)$ 쌍의 모양을 생각해봅시다.

$A_x = k$라고 가정하고, 해당 수를 포함하는 $(i, j)$의 모양을 생각합시다.

- $\min(A_f, \cdots, A_k), \min(B_f, \cdots, B_k) \ge x$인 최소의 $f$, $\min(A_k, \cdots, A_t), \min(B_k, \cdots, B_t) \ge x$인 최대의 $t$에 대해서, $i \in [f, k]; j \in [k, t]$인 경우 $\min(A_i, \cdots, A_j) = x$, $\min(B_i, \cdots, B_j) \ge x$를 만족하게 됩니다.
  - 이 범위를 넘어가게 되는 경우 $k$를 포함하지 않거나, $\min(A_i, \cdots, A_j) <x$가 됩니다.
- 이제, $B_s = x = B_e$를 만족하는 $s \le k \le e$ 이고 최대의 $s$, 최소의 $e$에 대해서 $i \in (s, k]; j \in [k, e)$인 경우에는 $B_i, \cdots, B_j$가 $x$를 포함하지 않으므로 $\min(B_i, \cdots, B_j) > x$ 입니다.

즉, $A_k = x$를 포함하는 구간에 대해서 가능한 $(i, j)$는 $[f, t] \times [k, t] - (s, k] \times [k, e)$이고, 이는 직사각형 두 개의 합집합으로 표현이 가능합니다. 모든 $k = 1, \cdots, N$에 대해 합집합을 구해주면 $(i, j)$의 범위는 직사각형 최대 $2N$개의 합집합으로 표현할 수 있습니다.

같은 방법으로 $\max$도 마찬가지 방법으로 직사각형들의 합집합으로 표현한 이후, $\min$모양과 $\max$모양의 두 구간의 교집합을 구하면 됩니다. 이는 특수한 형태의 세그먼트 트리를 이용하여 해결할 수 있습니다.

### 코드 (C++)

```cpp
#include <algorithm>
#include <climits>
#include <functional>
#include <iostream>
#include <set>
#include <vector>
using namespace std;

struct Seg
{
    struct Node
    {
        int cnt12, cnt1, cnt2, col1, col2;
        Node() : cnt12(), cnt1(), cnt2(), col1(), col2() {}
        void recalc_leaf()
        {
            cnt12 = col1 && col2 ? 1 : 0;
            cnt1 = col1 ? 1 : 0;
            cnt2 = col2 ? 1 : 0;
        }
        void recalc_internal(const Node &L, const Node &R, int len)
        {
            cnt1 = col1 ? len : L.cnt1 + R.cnt1;
            cnt2 = col2 ? len : L.cnt2 + R.cnt2;
            cnt12 = col1 || col2 ? min(cnt1, cnt2) : L.cnt12 + R.cnt12;
        }
    };

    Seg(int n): N(1)
    {
        while (N < n)
            N *= 2;
        idx.resize(2 * N);
    };
    int getv() { return idx[1].cnt12; }
    void setv(int tp, int v, int s, int e)
    {
        function<void(int, int, int)> F = [&](int i, int l, int r)
        {
            if (e < l || r < s)
                return;
            if (s <= l && r <= e)
            {
                if (tp == 1)
                    idx[i].col1 += v;
                else
                    idx[i].col2 += v;
            }
            else
            {
                int m = (l + r) / 2;
                F(2 * i, l, m);
                F(2 * i + 1, m + 1, r);
            }
            if (i >= N)
                idx[i].recalc_leaf();
            else
                idx[i].recalc_internal(idx[2 * i], idx[2 * i + 1], r - l + 1);
        };
        F(1, 0, N - 1);
    }

private:
    int N;
    vector<Node> idx;
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    vector<int> A(N), B(N);
    for (int &a : A)
        cin >> a;
    for (int &b : B)
        cin >> b;

    vector<int> C = A;
    copy(B.begin(), B.end(), back_inserter(C));
    sort(C.begin(), C.end());
    C.erase(unique(C.begin(), C.end()), C.end());
    int K = C.size();
    auto comp = [&](int x)
    { return distance(C.begin(), lower_bound(C.begin(), C.end(), x)); };

    set<int> smallB, largeB;
    vector<vector<int>> Aidx(K), Bidx(K), mnidx(K), mxidx(K);
    for (int i = 0; i < N; i++)
    {
        A[i] = comp(A[i]);
        B[i] = comp(B[i]);
        Aidx[A[i]].push_back(i);
        Bidx[B[i]].push_back(i);
        mnidx[min(A[i], B[i])].push_back(i);
        mxidx[max(A[i], B[i])].push_back(i);
        largeB.insert(i);
    }
    enum EventType
    {
        MIN_PUSH,
        MIN_POP,
        MAX_PUSH,
        MAX_POP
    };
    vector<vector<tuple<EventType, int, int>>> events(N + 1);
    for (int n = 0; n < K; n++)
    {
        for (int i : mxidx[n])
            largeB.erase(i);

        for (int i : Aidx[n])
        {
            int left_same = -1, left_large = -1, left_small = -1;
            int right_same = N, right_large = N, right_small = N;

            auto vit = upper_bound(Bidx[n].begin(), Bidx[n].end(), i);
            if (vit != Bidx[n].begin())
                left_same = *prev(vit);
            vit = lower_bound(Bidx[n].begin(), Bidx[n].end(), i);
            if (vit != Bidx[n].end())
                right_same = *vit;

            auto sit = largeB.upper_bound(i);
            if (sit != largeB.begin())
                left_large = *prev(sit);
            sit = largeB.lower_bound(i);
            if (sit != largeB.end())
                right_large = *sit;

            sit = smallB.upper_bound(i);
            if (sit != smallB.begin())
                left_small = *prev(sit);
            sit = smallB.lower_bound(i);
            if (sit != smallB.end())
                right_small = *sit;

            if (left_large < left_same && i < right_large)
            {
                events[i].emplace_back(MAX_PUSH, left_large + 1, left_same);
                events[right_large].emplace_back(MAX_POP, left_large + 1, left_same);
            }
            if (left_large < i && right_same < right_large)
            {
                events[right_same].emplace_back(MAX_PUSH, left_large + 1, i);
                events[right_large].emplace_back(MAX_POP, left_large + 1, i);
            }

            if (left_small < left_same && i < right_small)
            {
                events[i].emplace_back(MIN_PUSH, left_small + 1, left_same);
                events[right_small].emplace_back(MIN_POP, left_small + 1, left_same);
            }
            if (left_small < i && right_same < right_small)
            {
                events[right_same].emplace_back(MIN_PUSH, left_small + 1, i);
                events[right_small].emplace_back(MIN_POP, left_small + 1, i);
            }
        }

        for (int i : mnidx[n])
            smallB.insert(i);
    }

    int64_t ans = 0;
    Seg seg(N);
    for (int i = 0; i < N; i++)
    {
        for (auto [ev, s, e] : events[i])
            seg.setv(ev == MIN_PUSH || ev == MIN_POP ? 1 : 2, ev == MIN_PUSH || ev == MAX_PUSH ? +1 : -1, s, e);
        ans += seg.getv();
    }

    cout << ans << endl;
}
```

### 코드 (Python)

```
<준비중>
```


# 배수 피하기

## 풀이

$X+Y$가 $K$의 배수이고 $X$를 $K$로 나눈 나머지가 $i$이면, $Y$를 $K$로 나눈 나머지가 $(K-i) \bmod K$여야 하는 점에 착안합시다.

$A_i$ 를 $K$ 로 나눈 나머지가 $j$인 것의 개수를 $C_j$ 라고 합시다.

- $v = 1, \cdots, \lceil \frac K 2 \rceil -1$일 때 나머지가 $v$혹은 $K-v$인 수들을 고르는 경우의 수
  - $v$와 더해서 $K$의 배수가 되는 수는 $K-v$ 입니다. 즉, $S$에는 $K$로 나눈 나머지가 $v$이거나 $K-v$ 인 수만 들어가야합니다.
  - $S$ 에 $K$ 로 나눈 나머지가 $v, K-v$ 인 수가 하나 이상 들어가는 경우의 수는 각각 $2^{C_v} -1,2^{C_{K-v}}-1$이며, 둘 중 어떤 수도 들어가지 않는 경우는 $1$가지 입니다. 즉, 해당 나머지를 고르는 경우의 수는 $2^{C_v} + 2^{C_{K-v}} - 1$입니다.
- $v = 0$ 혹은 $K$가 $2$의 배수이고 $v = \frac K 2$ 일 때
  - $v$와 만나서 $K$의 배수가 되는 수는 $v$입니다. 즉 나머지가 $v$인 수는 최대 하나 들어갈 수 있습니다. 이런 경우의 수는 $C_v + 1$입니다.

답은 각 나머지를 고르는 방법을 모두 곱한 것입니다.

### 코드 (C++)

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

const int MOD = 1e9 + 7;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, K;
    cin >> N >> K;
    vector<int> c(K);
    for (int i = 0; i < N; i++)
    {
        int a;
        cin >> a;
        c[a % K]++;
    }
    int ans = 1;
    for (int i = 1; i < (K + 1) / 2; i++)
    {
        int pi = 1, pj = 1;
        for (int k = 0; k < c[i]; k++)
            pi = pi * 2 % MOD;
        for (int k = 0; k < c[K - i]; k++)
            pj = pj * 2 % MOD;
        ans = (int64_t)ans * (pi + pj - 1) % MOD;
    }
    ans = (int64_t)ans * (c[0] + 1) % MOD;
    if (K % 2 == 0)
        ans = (int64_t)ans * (c[K / 2] + 1) % MOD;

    ans = (ans + MOD - (N + 1)) % MOD;
    cout << ans << endl;
}
```

### 코드 (Python)

```python
import sys


def input(): return sys.stdin.readline().rstrip()


def main():

    MOD = 10**9 + 7
    N, K = map(int, input().split())
    c = [0]*K
    *A, = map(int, input().split())
    for a in A:
        c[a % K] += 1

    ans = 1
    for i in range(1, (K + 1) // 2):
        ans = ans * (pow(2, c[i], MOD) + pow(2, c[K-i], MOD) - 1) % MOD

    ans = ans * (c[0] + 1) % MOD
    if K % 2 == 0:
        ans = ans * (c[K // 2] + 1) % MOD
    ans = (ans - (N + 1)) % MOD
    print(ans)


if __name__ == "__main__":
    main()
```


# 돌 옮기기

## 풀이

기본적인 아이디어는, 남에게 추가적인 턴을 주지 않으면서 몇 턴동안 자기 팀의 돌을 움직일 수 있는지 세는 것입니다.

돌을 가장 뒤에서부터 하나씩 봅시다. 일반성을 잃지 않고 가장 뒤에 있는 돌이 `B`라고 합시다.

- 이 돌은 앞으로 움직여도 흰색 팀에게 추가 턴을 주지 않기 때문에 움직일 수 있다면 움직이는 것이 이득입니다. 마찬가지로, `W`가 나오기 전까지의 돌들은 움직여도 됩니다.

- 뒤에서부터 보면서 가장 처음에 나온 `W` 돌은 움직이기 않는게 이득입니다. 왜냐하면, 이 `W` 돌을 앞으로 한 칸 움직이면 뒤에 있는 `B` 돌을 앞으로 한 칸 움직이는 방식으로 `B`가 추가 턴을 얻을 수 있습니다.

이제 가장 뒤에 있는 `WBBB...` 에서 `B` 가 움직일 수 있는 총 길이를 센 이후, 해당 돌들을 모두 제외하고 앞으로 가서 나머지에 대해 움직일 수 있는 돌의 개수를 판단해주면 됩니다.

### 코드 (C++)

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

bool solve(string s)
{
    int64_t move = 0, cnt = 0;
    char cur = '.';

    reverse(s.begin(), s.end());
    for (char c : s)
    {
        if (cur == '.')
            cur = c;
        if (cur == '.')
            continue;
        if (c == '.')
            move += (cur == 'W' ? +1 : -1) * cnt;
        else if (c == cur)
            cnt++;
        else
            cur = '.', cnt = 0;
    }
    return move > 0;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        string s;
        cin >> s;
        cout << (solve(s) ? "WHITE" : "BLACK") << '\n';
    }
}
```

### 코드 (Python)

```python
import sys


def solve(s):
    move, cnt, cur = 0, 0, '.'
    for c in s[::-1]:
        if cur == '.':
            cur = c
        if cur == '.':
            continue
        if c == '.':
            move += (1 if cur == 'W' else -1) * cnt
        elif c == cur:
            cnt += 1
        else:
            cnt, cur = 0, '.'

    return move > 0


def input(): return sys.stdin.readline().rstrip()


def main():
    for _ in range(int(input())):
        print("WHITE" if solve(input()) else "BLACK")


if __name__ == '__main__':
    main()

```


# 막대 만들기

## 풀이

길이가 $i$ 인 막대를 만드는 방법의 수는 $i$ 인 막대를 그대로 사용하거나, $i$의 약수인 막대를 $k$ 배 늘리는 것입니다.

즉, $A_v = i$인 $v$의 개수를 $C_i$ 라고 하면, $D_i = C_i + \sum_{1 \le j < i;\ j \mid i} D_j$입니다.

이는 구현에 따라 $O(K \sqrt K)$ 혹은 $O(K \log K)$ 시간 복잡도에 구할 수 있습니다.

## 구현 1

$X$의 모든 약수를 $O(\sqrt X)$ 시간에 구하는 방법을 사용하면 $O(K \sqrt K)$ 시간 풀이가 됩니다.

### 코드 (C++)

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

int main()
{
    int N, Q;
    cin >> N;
    vector<int> A(N);
    for (int &a : A)
        cin >> a;
    cin >> Q;
    vector<int> L(Q);
    for (int &l : L)
        cin >> l;

    int MX = max(*max_element(A.begin(), A.end()), *max_element(L.begin(), L.end()));
    vector<int64_t> D(MX + 1);
    for (int a : A)
        D[a]++;

    for (int i = 2; i <= MX; i++)
        for (int j = 1; j * j <= i; j++)
            if (i % j == 0)
            {
                D[i] += D[j];
                if (j * j != i && j != 1)
                    D[i] += D[i / j];
            }
    for (int l : L)
        cout << D[l] << ' ';
    cout << endl;
}
```

### 코드 (Python)

```python
from itertools import count
import sys


def input(): return sys.stdin.readline().rstrip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    L = list(map(int, input().split()))

    MX = max(max(A), max(L))
    D = [0] * (MX + 1)
    for a in A:
        D[a] += 1

    for i in range(2, MX + 1):
        for j in count(1):
            if j * j > i:
                break
            if i % j == 0:
                D[i] += D[j]
                if j * j != i and j != 1:
                    D[i] += D[i // j]

    print(*(D[i] for i in L))


if __name__ == '__main__':
    main()

```

## 구현 2

배수를 세는 것이 약수를 세는 것보다 쉽습니다. $j$를 $1$부터 증가시켜 주면서, $D_j$의 계산이 완료된 이후 $j$의 배수 $i$에 대해 $D_i$에 $D_j$를 더해주는 방향으로 구현하면 시간복잡도가 $O\left(\frac K 1 +  \frac K 2 + \cdots + \frac K K = K \log K\right)$ 시간에 해결할 수 있습니다.

### 코드 (C++)

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

int main()
{
    int N, Q;
    cin >> N;
    vector<int> A(N);
    for (int &a : A)
        cin >> a;
    cin >> Q;
    vector<int> L(Q);
    for (int &l : L)
        cin >> l;

    int MX = max(*max_element(A.begin(), A.end()), *max_element(L.begin(), L.end()));
    vector<int64_t> D(MX + 1);
    for (int a : A)
        D[a]++;

    for (int j = 1; j <= MX; j++)
        for (int i = 2 * j; i <= MX; i += j)
            D[i] += D[j];
    for (int l : L)
        cout << D[l] << ' ';
    cout << endl;
}
```

### 코드 (Python)

```python
import sys


def input(): return sys.stdin.readline().rstrip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    L = list(map(int, input().split()))

    MX = max(max(A), max(L))
    D = [0] * (MX + 1)
    for a in A:
        D[a] += 1

    for j in range(1, MX + 1):
        for i in range(2 * j, MX + 1, j):
            D[i] += D[j]

    print(*(D[i] for i in L))


if __name__ == '__main__':
    main()

```


# 행렬 연산 (행렬 계산하기)

## 풀이

행렬의 $r$번째 행, $c$번째 열에 있는 수를 바꾸는 연산은 다음 두 가지 연산 중 하나입니다.

1. $r$번째 행에 $v$를 더합니다.

2. $c$번째 열에 $v$를 더합니다.

즉, $r$번째 행, $c$번째 열에 있는 수는 $r$번째 행 전체에 더해진 수와 $c$번째 행 전체에 더해진 수를 더한 값입니다.

이는 각 행과 열에 더해진 값을 누적하는 것으로 문제를 해결할 수 있습니다.

### 코드 (C++)

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, M, Q;
    cin >> N >> M >> Q;
    vector<int> R(N), C(M);
    for (int i = 0; i < Q; i++)
    {
        int t, rc, v;
        cin >> t >> rc >> v;
        if (t == 1)
            R[rc - 1] += v;
        else
            C[rc - 1] += v;
    }
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
            cout << R[i] + C[j] << ' ';
        cout << '\n';
    }
}
```

### 코드 (Python)

```python
import sys


def input(): return sys.stdin.readline().rstrip()


def main():
    N, M, Q = map(int, input().split())
    R = [0] * N
    C = [0] * M
    for _ in range(Q):
        t, rc, v = map(int, input().split())
        if t == 1:
            R[rc - 1] += v
        else:
            C[rc - 1] += v
    for i in range(N):
        for j in range(M):
            print(R[i] + C[j], end=' ')
        print()


if __name__ == "__main__":
    main()

```


# 행렬 연산 (연산 찾기)

## 풀이

행렬의 $r$번째 행, $c$번째 열에 있는 수를 바꾸는 연산은 다음 두 가지 연산 중 하나입니다.

1. $r$번째 행에 $v$를 더합니다.

2. $c$번째 열에 $v$를 더합니다.

즉, $r$번째 행, $c$번째 열에 있는 수는 $r$번째 행 전체에 더해진 수와 $c$번째 행 전체에 더해진 수를 더한 값입니다.

이제, 첫번째 행에 더하는 수를 $x$라고 합시다.

- 첫번째 행에 더하는 수와 $c$번째 열에 더하는 수의 합이 $A_{1, c}$가 되어야 하기 때문에, $c$번째 열에 더하는 수는 $A_{1, c} - x$가 되어야 합니다.
- $r$번째 행과 첫번째 열에 더하는 수의 합이 $A_{r, 1}$가 되어야 하기 때문에, $r$번째 행에 더하는 수는 $A_{r, 1} - (A_{1, 1}-x)= x + (A_{r, 1} - A_{1, 1})$가 되어야 합니다.

연산 횟수를 최소화하고 싶기 때문에, 각 행과 열에 더하는 수를 최대한 많이 $0$으로 만들어야 합니다. 이를 위해서는 $x$를 모든 $A_{1, c}$ 와 $A_{1,1} - A_{r, 1}$ 중 가장 많은 수로 고르면, 최대한 많은 행과 열들에 더해야 하는 수를 $0$으로 만들 수 있습니다.

 $x$를 정하고 각 행과 열에 더하는 수를 계산한 이후, 실제로 연산을 진행해서 $A$ 배열과 같아지는지 확인하면 됩니다.

### 코드 (C++)

```cpp
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, M;
    cin >> N >> M;
    vector<vector<int>> A(N, vector<int>(M));
    for (auto &y : A)
        for (int &x : y)
            cin >> x;

    map<int, int> cnt;
    for (int i = 0; i < N; i++)
        cnt[A[0][0] - A[i][0]]++;
    for (int i = 0; i < M; i++)
        cnt[A[0][i]]++;
    int mxv = 0, mxc = 0;
    for (auto [v, c] : cnt)
        if (mxc < c)
            mxv = v, mxc = c;

    vector<int> R(N), C(M);
    for (int i = 0; i < N; i++)
        R[i] = mxv + A[i][0] - A[0][0];
    for (int i = 0; i < M; i++)
        C[i] = A[0][i] - mxv;

    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            if (R[i] + C[j] != A[i][j])
            {
                cout << -1 << endl;
                return 0;
            }

    cout << N + M - mxc << '\n';
    for (int i = 0; i < N; i++)
        if (R[i])
            cout << 1 << " " << i + 1 << " " << R[i] << '\n';
    for (int i = 0; i < M; i++)
        if (C[i])
            cout << 2 << " " << i + 1 << " " << C[i] << '\n';
}
```

### 코드 (Python)

```python
import sys
from collections import defaultdict


def input(): return sys.stdin.readline().rstrip()


def main():
    N, M = map(int, input().split())
    A = [list(map(int, input().split())) for i in range(N)]

    cnt = defaultdict(int)
    for i in range(N):
        cnt[A[0][0] - A[i][0]] += 1
    for i in range(M):
        cnt[A[0][i]] += 1

    mxv = mxc = 0
    for v, c in cnt.items():
        if mxc < c:
            mxv, mxc = v, c

    R = [mxv+A[i][0] - A[0][0] for i in range(N)]
    C = [A[0][i] - mxv for i in range(M)]

    for i in range(N):
        for j in range(M):
            if R[i] + C[j] != A[i][j]:
                print(-1)
                return

    print(N + M - mxc)
    for i in range(N):
        if R[i]:
            print(1, i + 1, R[i])
    for i in range(M):
        if C[i]:
            print(2, i + 1, C[i])


if __name__ == '__main__':
    main()

```
