5월 22일 #JOI 깃발

JOI 깃발

캬 ㅋㅋㅋㅋㅋ
오늘 정말 행복하다!

신이 많이 도와주시는군 >ㅇ<
기차 타면서 내내 이 문제의 구현에 대해 생각했는데 저녁 10시 25분 경에 드디어 구현에 성공했고,
3484ms 라는비범한 시간에 내 코드가 1트만에 통과하는 기적을 목도했다.

구사과님한테 어그로 끌려서 이 문제를 풀게 되었는데 
끌리기 정말 잘했다는 생각이 든다!!

메모

1. 적어도 1개 이상이라는 조건은 매우 더럽다. 여사건을 이용하자.
2. 비트 필드 dp를 할 거다. M개의 비트를 들고 다니자.
3. 현재 넣을 알파벳이 'J' 나 'O'라면 위에는 아무 상태나 넣어도 된다.
4. 현재 넣을 알파벳이 'I'라면 바로 위가 'JO'인 상태는넣으면 안된다.
5. J와 O를 같은 비트(0)으로 취급할 건데, 맨 첫번째 비트는 'J'다 or 'O'다 라는 정보가 필요하므로 총 m+1개의 비트를 들고 다니며 0은 J, 2는 O로 관리하자.

210523 UPD) 다른 분들의 방법을 배워서 내 코드를 최적화 했다.

비재귀 방법의 풀이는 다음과 같다.

비트 스크롤링 dp를 실시
한 칸씩 옮겨가면서 dp를 갱신한다.

길이 m 비트의 상태를 계속 들고 다니는데
'J' 칸 오른쪽이 'JO'면 1로 체크한다.
이때 상태의 마지막 비트는 항상 0인 것,
상태에 연속한 1이 존재하지 못하는 것을 관찰할 수 있다.

이런 상태의 개수는 
따라서 21번째 피보나치 수(D1 = F3 = 2, D2 = F4 = 3, ... D19 = F21 = 10946)인 10946이 총 가능한 상태의 수가 된다.

각 상태 X에 대응되는 번호를 id[X>>1]에 저장한다 (마지막 비트가 0이므로 앞 m-1길이 만큼의 비트를 저장해도 충분.)
그리고 각 번호 id에 대응되는 상태를 st[id]에 저장한다

dp식은 다음과 같이 잡는다.
dp[r][c] [state] [carry]
s[r][c] 문자를 마지막으로 하는 상태 state의 가짓수를 구하는 것이다.
이때 carry는 무슨 의미이냐면, 마지막 문자가 J인지를 1과 0으로 저장한다.
다음 문자가 O가 되었을 때 JO (비트 1)이 생기는지 판정해주는 역할이다.

문자를 s[0][0] 에서 s[n-1][m-1]까지 윗쪽 행, 왼쪽 열부터 차례대로 본다.
------->
------->
------->
이럴 경우  dp[state][carry]와 상태 전이를 위한 nxtdp[state][carry]
2개의 공간만으로 마지막 문자까지 봤을 때 dp 상태를 구할 수 있다.
이 기법을 토글링이라 한다.
아직 아무 문자도 보지 않았을 때 가능한 상태는 오직 (0,0) 뿐이므로 
dp[0][0] = 1를 초기 상태로 두고 dp를 채워 나가기 시작한다.

현재 보는 문자가 'J'일 때는 carry를 1로 설정해야 하는 것에 유의하자
현재 보는 문자가 'O'일 때는 앞서 보는 상태의 carry가 1일 경우 m-1번째 문자를 1로 설정하는 것에 유의하자.
상태에 carry를 OR 연산하는 것으로 처리 가능
현재 보는 문자가 'I'일 때는 열번호가 j-1이거나 윗상태가 1(JO)가 아닐 때만 추가 가능한 것에 유의하자.

문자 c를 볼 때 직전 상태 X에 대해
X<<m-1이 바로 윗 상태,
X&1이 바로 왼쪽 상태다.
그림을 그려 보면 쉽게 이해 가능