콘테스트 기록

A, B, C, D를 어렵지 않게 풀었다. E는 좀 더 집중을 했으면 풀었을지도 모르지만 아직 풀지 않았다. F는 읽고 문제 내용을 이해했지만 해결법을 전혀 모른다.

A	B	C	D	E	F
00:07	00:12	00:25	00:47	-	-

1681A Game with Cards

각 경기자의 최선의 수는 자신이 가지고 있는 가장 큰 수 카드를 내는 것이다. Alice를 선공, Bob을 후공이라고 하자. Alice와 Bob이 가진 카드에 적힌 수 중 가장 큰 것을 각각 라고 하자.

• 이면, Alice가 첫 수로 를 냈을 때 Bob이 대응할 수 있는 수가 없다.
• 이면, 두 번째 수로 Bob은 항상 를 낼 수 있고, Alice는 이에 대응할 수 있는 수가 없다.

Bob이 선공인 경우에도 마찬가지 분석을 할 수 있다.

1681B Card Trick

법 에 대해 번째 카드를 찾으면 된다.

1681C Double Sort

수학적 귀납법을 통해 풀이와 정당성을 얻을 수 있다. 에 대해 번째 원소가 정렬되었다고 하면, 정렬되지 않은 원소 중 가 동시에 최솟값이 되는 를 번째 자리에 넣으면 번째 원소가 정렬된다. 이러한 를 찾을 수 없으면, 주어진 는 원하는 상태에 도달할 수 없다.

1681D Required Length

long long을 사용할 수 있는데, 표시할 수 있는 최댓값이 보다 크고, 연산은 항상 보다 작은 수와 9 이하의 수의 곱을 통해 새로운 수를 만들기 때문이다. 새로 만들어지는 수는 주어진 에 대해 항상 꼴이고, 위에서 관찰했듯 이러한 수는 이하이다. 을 얻을 수 있는데, 이를 만족하는 은 많아야 가지로, 수가 많지 않다. 따라서 단순히 BFS로 해결할 수 있다.