[Codeforces] Codeforces Round #506 (Div. 3)

드디어 지난번까지 풀었던 코드포스에 대한 풀이를 거의 다 올렸습니다.

조금만 더!!!

A. Many Equal Substrings

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a string $t$ consisting of $n$ lowercase Latin letters and an integer number $k$.

Let's define a substring of some string $s$ with indices from $l$ to $r$ as $s[l\dots r]$.

Your task is to construct such string $s$ of minimum possible length that there are exactly $k$ positions $i$ such that $s[i\dots i+n-1]=t$. In other words, your task is to construct such string $s$ of minimum possible length that there are exactly $k$ substrings of $s$ equal to $t$.

It is guaranteed that the answer is always unique.

Input

The first line of the input contains two integers $n$ and $k$ ($1\le n,k\le 50$) — the length of the string $t$ and the number of substrings.

The second line of the input contains the string $t$ consisting of exactly $n$ lowercase Latin letters.

Output

Print such string $s$ of minimum possible length that there are exactly $k$ substrings of $s$ equal to $t$.

It is guaranteed that the answer is always unique.

Examples

input

Copy

3 4
aba

output

Copy

ababababa

input

Copy

3 2
cat

output

Copy

catcat

문제 해석

문자열이 주어집니다. 그리고, 문자열을 몇 번 반복해서 출력해야하는지 알려주는 정수가 하나 주어집니다.

이렇게 수가 주어졌을 때, 최소의 길이로 문자열을 반복해서 만드는 경우를 출력하는 겁니다!

뒤의 중복되는 부분과 앞의 중복되는 부분은 겹쳐져서 만들어 질 수 있습니다!

예를들면, 

aba에서 앞 뒤가 겹쳐질 수 있기 때문에, 이를 4번 반복하여 만들어질 수 있는 길이는 ababababa 인 것입니다!

aba

   aba

      aba

         aba

이렇게 보일 수 있는 것이죠!

어떻게 풀까?

이 문제는 앞, 뒤에서 어떻게 똑같은 부분을 찾는지 알아내는 방법입니다.

이를 위한 아주 유명한 방법이 바로 KMP 전처리 과정이죠!

KMP는 기회가 된다면 나중에 설명해드리도록 하겠습니다.

일단, 전처리 하는 과정에 대해서 설명드리겠습니다!

간단하게 설명드리면, 일단 문자열을 가르키는 포인터가 2개 있습니다.

그리고, 포인터 하나는 전체 문자열에서 인덱스를 하나씩 늘리는 것이고,

하나의 포인터는 맨 앞에서부터 똑같은 문자열의 개수를 나타냅니다.

그림을 통해 설명해드리죠!

자, 현재 상태가 이렇다고 합시다! 문자열은 현재 b까지 비교했습니다.

그리고, a와 b가 똑같은 문자이기 때문에 위의 상황은 저렇게 된다고 하죠!

비교하는 문자는 b와 b가 되고, 두 문자는 같기 때문에 모두 한 포인터씩 오른쪽으로 움직입니다!

그렇다면, 다음 결과는 이렇게 되겠죠!

만약, 문자열이 b와 c였다면 어땠을까요?

문자열 비교하는 포인터는 계속 오른쪽으로 향하고,  두 문자가 달랐기 때문에 똑같은 곳을 비교해주는 포인터는 시작점으로 이동합니다.

이런식으로 반복해서 끝까지 간다면, 마지막에 도달했을 떄, 처음 부분이 얼마나 반복되는지 알 수 있을 것입니다!

다만, 또 생각해봐야 할 부분이 있습니다.

아래 경우를 생각해 봅시다.

위 문자열의 시작과 끝부분이 같은 부분은 이렇게 abcd의 4부분 입니다.

그럼, 아까 제가 풀려고 했던 방법을 이용해서 문제를 풀어봅시다.

f뒤의 a부터 시작해서 abca까지는 같을 것입니다. 그리고 b와 b가 같기 때문에, 두 개의 포인터를 둘 다 한칸씩 오른쪽으로 이동시켜봅시다.

앗, c와 f는 다르기 때문에, 두번째 포인터를 다시 시작점으로 옮겨야합니다!

그렇게하면.. 세상에.. 똑같은 문자열이 하나밖에 안남게 됩니다.

이를 극복하기 위해선 어떠한 방법이 필요할까요!?

정답부터 우선 말씀 드리면, 이 알고리즘의 문제점은, c와 f를 비교했을 때 틀리면 바로 시작점으로 이동해버렸기 때문입니다!

f이전에는 ab가 있기 때문에, 실제로는 abc를 통해서 시작지점이 아니라, abca의 인덱스로 인동해야 하는 것이죠!

이를 위해선 어떤 방법을 써야할까요??

우선, f를 비교하는 곳으로 가 봅시다!

위 그림을 보면, f와 c가 다른 곳이 바로 abc문자열, 즉 2번 인덱스일 경우라는 것을 알 수 있습니다! (a를 0번 인덱스라고 하겠습니다.)

즉, 만약, f가 2번 인덱스와 똑같은 c였다면, 계속해서 진행할 수 있었다는 것을 알 수 있는 것입니다!!!

그렇다면, 만약에 5번 인덱스인 f를 비교할 때, f가 아닌 상황이 되었다고 해 봅시다!

하지만, 그 문자열이 만약 2번 인덱스와 같은 c였다면!? 똑같은 곳을 나타내는 포인터는 시작점을 가르킬 필요도 없이 바로 3번 인덱스인 a를 가르키면 됩니다!

 그렇다면 위에서 발생했던 문제를 해결할 실마리를 찾을 수 있습니다.

일차원 배열에, 만약 똑같은 곳의 인덱스가 틀리다면, 원래는 어떤 인덱스의 문자가 나와야 하는지를 저장하는 일차원 배열을 만듭시다!

(참고로 시작점을 알 수 있기 위해서 시작점은 -1로 넣어 놓겠습니다.) 

그리고, 다시 한 번 위의 문자열을 처리해 봅시다.

배열에는 만약 틀렸으면, 어디부터 다시 확인해야하는지에 대한 인덱스가 들어있습니다!

그렇다면, f까지는 이렇게 만들어질 것 입니다! 하지만, f와 c는 다르기 때문에, 이제 a는 다시 처음부터 봐야겠죠!

a쪽에는 다시 처음부터 봐야하기 때문에 0을 넣습니다!

이제 다시 abcab까지는 똑같을 것입니다!

앗, c와 f를 비교하는데 c와 f가 다릅니다!

다르기 때문에, 봐야하는 이동해야하는 포인터를 확인합니다.

2번 인덱스와 비교합니다!

오옷, 2번 인덱스와는 똑같습니다!

즉, c에는 2를 넣습니다.

그럼 이제 다음 문자를 확인합니다.

이렇게 되겠죠!

하지만, 제가 이 배열에 저장했던 것이 문자열이 다르면 확인해야하는 인덱스의 번호였다는 것에 주목하셔야 합니다.

즉, 위의 경우에는 맨 마지막 문자는 어떤 문자가 오든, 3이 들어온다는 것입니다!

아래 처럼 말이죠! 왜냐하면 d가 다르면 3번 인덱스를 확인해야 한다! 는 것이 이 배열의 목적이기 때문이죠.

따라서, 마지막 문자가 정확하게 제대로 끝나는지 확인하기 위해서는 추가 작업이 필요합니다.

맨마지막 문자가 밑의 인덱스 3번과 같은 문자라고 한다면, 처음과 똑같은 문자의 길이는 3보다 1 큰 4가 됩니다.

그리고, 만약 다르다면 똑같은 문자열의 길이는 0이 되죠!

그런데, 다르다고 해도 맨 처음 문자와 같으면 똑같은 문자의 길이는 1이 됩니다.

또한, 길이가 1일 경우에는, 똑같은 문자의 길이를 0으로 반환해야겠죠! 

이제, 이렇게 똑같은 문자의 길이를 알았다면, 어떻게 하면 될까요?

일단, 주어진 문자를 한번 출력하고, 똑같은 문자의 길이만큼 제외한 뒤의 문자만큼을 계속해서 출력하면 됩니다!

예제 1번의 경우를 확인해 보죠!

input

Copy

3 4
aba

위 같은 경우에는 똑같은 문자가 aba 1이기 때문에,

앞에서부터 1개를 제외한 ba만 2번 더 출력하면 됩니다!

aba ba ba 이렇게 3번 출력해주면 되죠!

코드

#pragma once
#include<cstdio>
 
int n, k;
int w;
char str[51];
int kmp[51];
int last;
 
char resRes[1000000];
int reslen;
int setLast() {
    int prev = 0;
    kmp[0] = -1;
    int j = 0;
 
    for (int i = 1; i < n; i++) {
        j++;
        while (j != -1 && str[j] != str[i]) {
            j = kmp[j];
        }
        kmp[i] = j;
    }
    kmp[n - 1] = str[kmp[n - 1]] == str[n - 1] ? kmp[n - 1] + 1 : str[0] == str[n - 1];
 
    return kmp[n - 1];
}
 
int main() {
    scanf("%d %d\n", &n, &k);
    scanf("%s\n", str);
    int idx = n == 1 ? 0 : setLast();
 
    char res[51];
    int rlen = 0;
    for (int i = 0; i < n - idx; i++) {
        res[i] = str[i + idx];
    }
 
    for (int i = 0; i < n; i++) resRes[reslen++] = str[i];
    k--;
    while (k--) {
        for (int i = 0; i < n - idx; i++)
            resRes[reslen++] = res[i];
    }
 
    resRes[reslen] = 0;
    printf("%s\n", resRes);
 
    return 0;
}

시간 복잡도

모두 문자열의 길이 N만큼 반복하는것 밖에 없기 때문에 시간 복잡도는 O(N) 입니다!

B. Creating the Contest

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a problemset consisting of $n$ problems. The difficulty of the $i$-th problem is $a_i$. It is guaranteed that all difficulties are distinct and are given in the increasing order.

You have to assemble the contest which consists of some problems of the given problemset. In other words, the contest you have to assemble should be a subset of problems (not necessary consecutive) of the given problemset. There is only one condition that should be satisfied: for each problem but the hardest one (the problem with the maximum difficulty) there should be a problem with the difficulty greater than the difficulty of this problem but not greater than twice the difficulty of this problem. In other words, let $a_{i_1},a_{i_2},\dots ,a_{i_p}$ be the difficulties of the selected problems in increasing order. Then for each $j$ from $1$ to $p-1$ $a_{i_{j+1}}\le a_{i_j}\cdot 2$ should hold. It means that the contest consisting of only one problem is always valid.

Among all contests satisfying the condition above you have to assemble one with the maximum number of problems. Your task is to find this number of problems.

Input

The first line of the input contains one integer $n$ ($1\le n\le 2\cdot {10}^5$) — the number of problems in the problemset.

The second line of the input contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le {10}^9$) — difficulties of the problems. It is guaranteed that difficulties of the problems are distinct and are given in the increasing order.

Output

Print a single integer — maximum number of problems in the contest satisfying the condition in the problem statement.

Examples

input

Copy

10
1 2 5 6 7 10 21 23 24 49

output

Copy

4

input

Copy

5
2 10 50 110 250

output

Copy

1

input

Copy

6
4 7 12 100 150 199

output

Copy

3

Note

Description of the first example: there are $10$ valid contests consisting of $1$ problem, $10$ valid contests consisting of $2$ problems ($[1,2],[5,6],[5,7],[5,10],[6,7],[6,10],[7,10],[21,23],[21,24],[23,24]$), $5$ valid contests consisting of $3$ problems ($[5,6,7],[5,6,10],[5,7,10],[6,7,10],[21,23,24]$) and a single valid contest consisting of $4$ problems ($[5,6,7,10]$).

In the second example all the valid contests consist of $1$ problem.

In the third example are two contests consisting of $3$ problems: $[4,7,12]$ and $[100,150,199]$.

문제 해석

오름차순으로 배열이 주어집니다!

이 때, 오름차순으로 부분 배열을 만들려고 합니다!

하지만, 조건이 있습니다!

바로, 모든 부분 집합의 원소들에 대해서  를 만족해야 한다는 것 입니다!

이 때, 가장 긴 부분 집합의 길이를 구하세요!

어떻게 풀까?

문제가 오름차순으로 주어집니다!

자 우선, 구성된 부분집합 S가 있다고 하겠습니다!

S의 가장 오른쪽에 있는 수는 a라고 하겠습니다.

이제, 입력 b가 주어집니다.

만약, b가 a의 2배보다 크다면 어떻게 될까요?

그렇다면, 어짜피 b 뒤에 들어오는 다른 수 모두다 a보다 2배 더 크다는 것 입니다!

결국, b 뒤는볼 필요가 없다는 말이죠!

따라서, 부분 집합 S를 공집합에서 부터 시작해서 b가 a의 2배 이하라면 집합 S의 맨 뒤에 포함시키고,

a의 2배보다 크다면, 부분 집합 S를 b원소 하나만 갖게 만들어서 다시 위 과정을 반복하면 됩니다!

이렇게 하면 S의 최대 길이를 구할 수 있죠!

예제를 풀어보겠습니당

input

Copy

10
1 2 5 6 7 10 21 23 24 49

자 처음에 1만 넣습니다!

다음에 2가 오기 때문에

부분 집합을 1 2 로 넣습니다.

다음에 5가 들어오지만, 1, 2, 5를 이을 수 없기 때문에

부분 집합 S를 5로 채웁니다!

여기서 1과 2를 포함해서 만들 수 있는 부분 집합의 크기는 정말로 1,2 밖에 없다는 것을 알 수 있습니다! 어짜피 뒤에것은 다 붙일 수 없기 때문이죠..

자! 그럼 이제 다음 6을 붙입니다.

부분 집합 : 5, 6

7에 10까지도 붙일 수 있죠!

부분 집합 : 5, 6, 7, 10

하지만 21은 붙일 수 없습니다!

부분 집합을 수정합니다. : 21

23,24 까지 넣을 수 있습니다!

부분 집합 : 21, 23, 24

다음엔 이제 49 하나가 남습니다.

부분 집합 : 49

이제, 가장 큰 길이는 5, 6, 7, 10 이라는 것을 알 수 있습니다!!

답은 4!

코드

#pragma once
#include<cstdio>
 
int arr[200010];
 
int main() {
    int n;
    int l = 0;
    arr[0] = -1;
    scanf("%d\n", &n);
    int in;
    scanf("%d\n", &in);
 
    arr[1] = in;
    l = 1;
    int max = 1;
    for (int i = 1; i < n; i++) {
        int in;
        scanf("%d\n", &in);
 
        if (arr[l] * 2 >= in) {
            l++;
            arr[l] = in;
            max = max < l ? l : max;
        }
        else {
            l = 1;
            arr[1] = in;
        }
    }
    printf("%d\n", max);
    return 0;
}

시간 복잡도

여기에서도 배열의 길이만큼 한 번 반복하는 것 밖에 없기 때문에 O(N) 입니다!

C. Maximal Intersection

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given $n$ segments on a number line; each endpoint of every segment has integer coordinates. Some segments can degenerate to points. Segments can intersect with each other, be nested in each other or even coincide.

The intersection of a sequence of segments is such a maximal set of points (not necesserily having integer coordinates) that each point lies within every segment from the sequence. If the resulting set isn't empty, then it always forms some continuous segment. The length of the intersection is the length of the resulting segment or $0$ in case the intersection is an empty set.

For example, the intersection of segments $[1;5]$ and $[3;10]$ is $[3;5]$ (length $2$), the intersection of segments $[1;5]$ and $[5;7]$ is $[5;5]$(length $0$) and the intersection of segments $[1;5]$ and $[6;6]$ is an empty set (length $0$).

Your task is to remove exactly one segment from the given sequence in such a way that the intersection of the remaining $(n-1)$segments has the maximal possible length.

Input

The first line contains a single integer $n$ ($2\le n\le 3\cdot {10}^5$) — the number of segments in the sequence.

Each of the next $n$ lines contains two integers $l_i$ and $r_i$ ($0\le l_i\le r_i\le {10}^9$) — the description of the $i$-th segment.

Output

Print a single integer — the maximal possible length of the intersection of $(n-1)$ remaining segments after you remove exactly one segment from the sequence.

Examples

input

Copy

4
1 3
2 6
0 4
3 3

output

Copy

1

input

Copy

5
2 6
1 3
0 4
1 20
0 4

output

Copy

2

input

Copy

3
4 5
1 2
9 20

output

Copy

0

input

Copy

2
3 10
1 5

output

Copy

7

Note

In the first example you should remove the segment $[3;3]$, the intersection will become $[2;3]$ (length $1$). Removing any other segment will result in the intersection $[3;3]$ (length $0$).

In the second example you should remove the segment $[1;3]$ or segment $[2;6]$, the intersection will become $[2;4]$ (length $2$) or $[1;3]$(length $2$), respectively. Removing any other segment will result in the intersection $[2;3]$ (length $1$).

In the third example the intersection will become an empty set no matter the segment you remove.

In the fourth example you will get the intersection $[3;10]$ (length $7$) if you remove the segment $[1;5]$ or the intersection $[1;5]$ (length $4$) if you remove the segment $[3;10]$.

문제 해석

n개의 쌍이 주어집니다! 

한 쌍 (a,b)는 a~b의 구간을 가진다는 의미입니다!

자, 이제 여러개의 구간이 겹쳐지는 것도 가능합니다!

예를 들면, (1,5) 구간과 (3,10) 구간은

(3,5)가 겹치는 구간이죠!

이렇게 구간의 쌍이 주어질 때, 모둔 구간에 겹쳐지는 구간을 찾고, 그 구간의 최장길이를 구하세요!

어떻게 풀까?

모든 쌍에서 포함되는 구간에 대해 생각해봅시다!

일단 모든 구간의 시작점에서부터 한번 보죠!

모든 구간의 쌍에서 시작점을 모았을 때, 시작점은 이 모임 중에서 가장 큰 값을 선택해야 합니다!

input

Copy

5
2 6
1 3
0 4
1 20
0 4

이 경우에는, 시작점들이 0 0 1 1 2 이기 때문에, 2를 선택해야 한다는 것이죠!

이유는 간단합니다! 가장 큰 값이 아닌 1을 선택했다고 하면, 1번 쌍(2,6)에서는 1을 포함하지 않기 때문이죠!

작은 시작점을 선택하면 그보다 큰 시작점을 가지고 있는 쌍들은 해당 지점의 점을 가지지 못하기 때문이에요!

끝점들은 이와 반대입니다.

끝점들을 모아 놓으면, 그 중에서 가장 작은 끝점을 선택해야 모든 구간에 포함되는 끝점을 만들 수 있죠!

그리고 이렇게 선택된 두 점이 바로 구간의 길이가 최대가 되는 두 점이라는 것을 알 수 있습니다!

왜냐하면, 이 시작점보다 한칸 더 크게 하거나, 끝점이 한칸 줄어들면, 구간의 길이가 작아지고,

시작점을 한 칸 작게 하거나, 끝 점을 한 칸 크게 하면, 해당 지점을 포함하지 못하는 쌍이 생기기 때문이죠!

자, 가장 큰 시작점과, 가장 작은 끝점을 선택해서 위와 같은 구간을 만들었다고 해봅시다!

이보다 더 키우기 위해서, 1을 구간에 하나 더 넣으려고 합니다!

하지만, 2,3,4,5가 선택되었다는 것은 어떤 한 쌍은 시작점이 2라는 것입니다!

따라서, 해당 쌍에서는 1을 포함하지 못합니다. 따라서 답이 될 수 없죠.

반대로 2를 빼버리면, 답은 되는데 구간이 줄어들기 때문에 또한 답이 아닙니다.

위 두 경우는 끝점에 대해서도 마찬가지이죠!

문제를 보면, 이제 구간의 길이는 끝점 - 시작점을 통해 구할 수 있다는 것을 알 수 있습니다.

단, 문제의 조건에서 하나의 쌍을 지운다는 조건이 있습니다! 

이를 해결하는 방법은 생각보다 간단합니다.

쌍은 총 n개 입니다.

1번 쌍 ~ n번 쌍 까지 존재하죠.

그리고, 모든 쌍에서 나올 수 있는 시작점을 모두 배열에 입력받고 정렬하고,

모든 쌍에서 나올 수 있는 끝점을 모두 배열에 입력받고 정렬합시다.

이제 1번 쌍 ~ n번 쌍을 확인합시다.

만약 i번 쌍에서의 시작점이 가장 큰 시작점이라면 어떻게 해야할까요?

그 시작점은 이제 i번 쌍에서 삭제된다는 의미이기 때문에 다음으로 큰 시작점을 선택하면 됩니다.

만약, i번 쌍에서의 끝점이 가장 큰 끝점이라면?

반대로, 그 다음으로 작은 끝점을 선택하면 되겠죠.

이렇게 쌍을 하나씩 빼고, 그 때의 최솟값을 구하면 답을 구할 수 있습니다!

예제를 풀어보죠!

5
2 6
1 3
0 4
1 20
0 4

output

Copy

2

시작점을 정렬하면,

0 0 1 1 2가 되겠군요.

끝점은 3 4 4 6 20 이 되겠죠!

자 1번 쌍 부터 확인합시다.

1번 쌍의 시작점이 가장 큰 점입니다! 그럼 이제 정렬된 시작점에서 2 번째로 큰 값을 선택해야 합니다! 1을 선택하겠죠!

1번 쌍의 끝점은 6 이기 때문에, 가장 작은 끝점인 3을 선택합니다.

두 수를 빼면 2가 됩니다!

2번 쌍 : 시작점은 2, 끝 점은 4를 선택합니다.

두 수를 빼면 2가 됩니다.

3번 쌍 : 시작점은 2, 끝 점은 3, 차이는 1 입니다.

4번 쌍 : 시작점은 2, 끝 점은 3 차이는 1 입니다.

5번 쌍 : 시작점은 2, 끝 점은 3 차이는 1 입니다.

따라서, 가장 큰 구간은 1번 쌍을 빼거나, 2번 쌍을 뺐을 때의 구간

(1,3) 과 (2, 4)의 길이 2입니다!

코드

#pragma once
#include<cstdio>
#include<algorithm>
#include<vector>
 
using namespace std;
 
typedef pair<int, int> PII;
int n;
int x[300001], y[300001];
vector<PII> vec;
 
int main() {
 
    scanf("%d\n", &n);
 
    for (int i = 0; i < n; i++) {
        scanf("%d %d\n", &x[i], &y[i]);
        vec.push_back({ x[i], y[i] });
    }
 
    sort(x, x + n);
    sort(y, y + n);
    sort(vec.begin(), vec.end());
 
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int xx = i == n - 1 ? x[n - 2] : x[n - 1];
        int yy = vec[i].second == y[0] ? y[1] : y[0];
 
        int d = yy - xx;
        ans = ans < d ? d : ans;
    }
    printf("%d\n", ans);
    return 0;
}

시간 복잡도

시간 복잡도는 끝점과 시작점을 정렬하기 위한 O(N log N) 입니다.

D. Concatenated Multiples

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array $a$, consisting of $n$ positive integers.

Let's call a concatenation of numbers $x$ and $y$ the number that is obtained by writing down numbers $x$ and $y$ one right after another without changing the order. For example, a concatenation of numbers $12$ and $3456$ is a number $123456$.

Count the number of ordered pairs of positions $(i,j)$ ($i\ne j$) in array $a$ such that the concatenation of $a_i$ and $a_j$ is divisible by $k$.

Input

The first line contains two integers $n$ and $k$ ($1\le n\le 2\cdot {10}^5$, $2\le k\le {10}^9$).

The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le {10}^9$).

Output

Print a single integer — the number of ordered pairs of positions $(i,j)$ ($i\ne j$) in array $a$ such that the concatenation of $a_i$ and $a_j$ is divisible by $k$.

Examples

input

Copy

6 11
45 1 10 12 11 7

output

Copy

7

input

Copy

4 2
2 78 4 10

output

Copy

12

input

Copy

5 2
3 7 19 3 3

output

Copy

0

Note

In the first example pairs $(1,2)$, $(1,3)$, $(2,3)$, $(3,1)$, $(3,4)$, $(4,2)$, $(4,3)$ suffice. They produce numbers $451$, $4510$, $110$, $1045$, $1012$, $121$, $1210$, respectively, each of them is divisible by $11$.

In the second example all $n(n-1)$ pairs suffice.

In the third example no pair is sufficient.

문제 해석

a와 b 두개의 수를 합칠 수 있습니다!

예를들면, 12와 3456을 합치면 123456이 되는 겁니다!

이 때, N개의 수와 K라는 수가 주어졌을 때,

N개의 수 2개를 합쳐서 K라는 수로 나눌 수 있는 개수를 구하면 됩니다!

어떻게 풀까?

우선, 두 수를 합친다는 의미에 대해서 생각해봅시다!

12와 3456을 합친다는 것은,

3456이 네자리이기 때문에 120000 + 3456을 의미하는 것입니다!

그리고, 모듈러 연산 덕분에

123456 % K = ((120000%K) + (3456%K))%K 를 계산하는 것과 같죠!

그리고, 120000%K = ((12%K) * (10000%K))%K와 같습니다!

이렇게 하면, 뭔가 방법이 떠오를 것 같습니다.

주어지는 수는 100000000를 넘지 않습니다.

즉, 10자리 수를 넘지 않는다는 것이죠!

그렇다면, 모든 수에서 이미 10자리 수의 K와 모듈러 연산을 한 값을 저장합시다!

모든 수들의 i 번째 자리수에서 나오는 모듈러 연산 후 나오는 값들은 vec[i]에 저장합니다.

그럼, 이제 어떻게하면 나누어 떨어지는지 알 수 있을까요!?

자, n번째 수를 an이라고 하겠습니다!

an % k 의 값을 매우 쉽게 구할 수 있겠죠!

나누어 떨어지기 위해서는 k - (an%k)의 값을 가지는 수와 조합해야 합니다!

an의 ㅏ자리수가 i 라면,

결국, vec[i] 중에서 k - (an%k)를 가지는 값이 몇개인지 찾으면 됩니다!!!!

단, 같은 수를 중복해서 고르면 안되기 때문에, 만약 k - (an%k) 와 an%k 가 같으면 1을 빼줘야 합니다!

코드

#pragma once
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
 
vector<long long> vec[12];
 
long long remains[200001][12];
long long remains1[200001];
int p[200001];
 
int getDigit(long long i) {
    int res = 0;
    while (i) {
        i /= 10;
        res++;
    }
    return res;
}
 
int size(vector<long long> & vec, long long value) {
    int l = 0; int r = vec.size() - 1;
    int m;
    while (l < r) {
        m = (l + r) / 2;
 
        if (value <= vec[m]) {
            r = m;
        }
        else {
            l = m + 1;
        }
    }
 
    int i1 = r;
    l = 0; r = vec.size() - 1;
    while (l < r) {
        m = (l + r) / 2;
        if (value < vec[m]) {
            r = m;
        }
        else {
            l = m + 1;
        }
    }
    if (vec[i1] != value) return 0;
    int i2 = r;
    if (vec.size() - 1 == i2 && vec[i2] == value) i2++;
    return i2 - i1;
}
 
int main() {
    int n; long long k;
    scanf("%d %lld\n", &n, &k);
 
    for (int i = 0; i < n; i++) {
        long long in;
        scanf("%lld\n", &in);
        remains[i][0] = in % k;
        p[i] = getDigit(in);
        for (int j = 1; j < 12; j++) {
            remains[i][j] = (remains[i][j - 1] * 10) % k;
            vec[j].push_back(remains[i][j]);
        }
    }
    long long res = 0;
    for (int i = 1; i < 12; i++) sort(vec[i].begin(), vec[i].end());
 
    for (int i = 0; i < n; i++) {
        int pow = p[i];
        res += size(vec[pow], (k - remains[i][0]) % k);
        if (remains[i][pow] == (k - remains[i][0]) % k) res--;
    }
 
    printf("%lld\n", res);
 
    return 0;
}

시간 복잡도

시간 복잡도는 각 자리수마다 최고 n개의 인자를 정렬해야 할 수 있기 때문에,  O(N log N) 입니다.

여담

이때의 코포도 굉장히 아까운 순간이었습니다.

왜냐하면, res를 int로 했기 때문에 틀렸다는 것을 너무 늦게 깨달았기 때문이죠!

생각해보면, 2 개의 식을 조합하는 개수만 해도 이었는데.. 너무 안일했습니다.

코포가 시간에 쫓기는 싸움이다 보니 더 이런 상황에서 대처를 잘 못하는 것 같아요.

좀 더 분발해야겠습니다.