AtCoder Regular Contest 151

A - Equal Hamming Distances

뜬금없이 어렵다.

초반 문제를 빠르게 못 푸는 내 성향상 더 말렸다. 그래도 WA는 안 쌓은게 어디...

 

최상위 코더들 코드를 확인해봤는데, 구현에 문제가 있는 것은 아니다. 그냥 속도가 느린 것.

그냥... 할 말이 없네.

 

쉬운 문제들 빨리 푸는 연습?을 더 해라?

 

B - A < AP

반성해야 할 문제이다.

이번 ARC는 어려워서 빠른 2솔이 중요한데, 시간을 너무 잡아먹은 바람에 퍼포먼스가 잘 안 나왔다. (민트 중상위 퍼포)

 

시작할 때부터 등호 조건은 구하기 쉽네~ 이랬는데, 삽질하다가 못 알아차림...

꾸준히 스스로 지적하고, 또 조금씩 고쳐지는 것 같기도 한 습관 중에 하나인데, 풀이 방향을 섣불리 정하는 것이다. 풀이 초반에는 다양한 접근을 하면서 가장 좋은 방향을 찾아내는 것이 중요한데, 어디서 본 듯하거나 하면 그 방향에 꽂힌다. 이걸 좀 스스로 자제해야 한다.

아무래도 CF Div.2 A~B 정도의 typical하고 쉬운 문제들에는 잘 먹히다 보니 습관이 된 것 같다. 어차피 Div.2 A~B 푸는 속도도 느린데 그냥 이 습관을 버리는 게 어떨지..??

 

이 문제 같은 경우는 수형도를 찾아서 재귀적인 패턴을 구하려는 시도를 처음부터 밀고 들어갔다. 하지만 등호 조건을 구하는 방법만 안다면 not equal의 경우를 2로 나눠 간단히 구해줄 수 있다. 뭐 이게 중요한 것은 아니다. 조금 고민했으면 몰랐을 리가 없는 것.

웃긴 점은 수형도로 풀어냈다는 것이다. ㅋㅋㅋㅋㅋㅋ 아무튼 앞으로는 이런 일 줄이도록...

 

C - 01 Game

사전지식이 조금 필요하지만, 퀄리티가 높은 문제이다.

사전지식을 충분히 알고 있다면 스스로 풀어보는 것을 추천한다.

 

subgame에 대한 sprague-grundy 정리를 잘 이해하고 있어야 한다.

물론 이 문제는 덤으로 관찰할 것들이 좀 있다.

같은 것 사이에 낀 것들, 다른 것 사이에 낀 것들, 맨 끄트머리 상황들을 함께 고려하면 된다는 것을 생각보다 잘 발견했다.

다만, 양쪽 끄트머리가 모두 존재하는 일반적인 경우들에 대해 sprague-grundy를 때렸어야 되는데 잘 몰라서 못 풀었다.

 

$g$는 전체 game에 대한 grundy number, $g_i$들은 각 subgame들의 grundy number들이다.

$g=g_1\oplus g_2\oplus \cdots.$ (subgame의 특징이고, grundy game은 또 다르다.)

 

sprague-grundy는 정보올림피아드 필기에서도 요즘 자주 다루는 개념이니 시간을 두고 더 익혀볼 필요가 있다.

https://yujaa.tistory.com/entry/게임이론-스프라그-그런디-정리

https://web.mit.edu/sp.268/www/nim.pdf

 

코드:

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

const int M = 2e5+3;
ll n, m, x[M]; bool y[M];
ll grundy;

int main() {
    cin >> n >> m;
    rep(i,1,m) {
        cin >> x[i] >> y[i];
        if (i > 1 and y[i-1] == y[i]) grundy ^= 1;
    }
    if (m == 0)
        cout << (n%2 ? "Takahashi" : "Aoki");
    else {
        grundy ^= (x[1]-1)^(n-x[m]);
        cout << (grundy ? "Takahashi" : "Aoki");
    }
}