Google Codejam Qualification Round 2016

• 그래 퀄이라도 올솔브 해야지ㅋㅋ... 중간중간 밖에 나갔다와서 페널티가 많이 붙음.
• A : operation을 직접 구현해서 돌려보면 되는 문젠데, operation수가 돌려볼만한 각이 나오는지 약간 생각이 필요하다. 상한은 100정도 될 것 같은데, \(N\)이 \(K\)자릿수라고 하면 \(c*N\)에 대해서 \(K+1\)자릿수는  \(1, 2, 3, \cdots, 9\)를 순차적으로 거쳐갈 수밖에 없기때문. 따라서 확실히 \(K+2\)자릿수가 생기는 100 이전에는 모든 숫자가 한번씩 나오게 될 것이라 예상할 수 있다.
• B : 역시 구현문제.. flip operation은 같은 위치에 여러번 할 필요 없이, 0-1로 수행하는 게 최적이다. 그리디로 맨 뒤에서부터 -가 있으면 range flip을 해주면서 답을 만들면 된다.
• C : ㅋㅋ재밌는 문제. small에 대해서는 \(2^{14}\)가 큰 값이 아니므로 그냥 돌려보면 된다. large는 \(2^{30}\)이 돌려볼 수 없는데다, \(10^{31}+1+x\)의 약수를 하나 찾는 걸 요구하고 있다. 직접적인 방법으론 불가능하고, 여러 우회로를 생각해 볼 수 있는데.. 가장 간단한 것은 small의 답을 이용하는 것이다. 만약 small의 답 중 하나로 [1000000001001111 3 2 3 2 7 2 3 2 3]을 찾았다고 해보자. 이 code에 대해서 한번 더 똑같은 문자열을 붙인 [10000000010011111000000001001111]을 생각한다. 얘는 길이가 32이고, 원래 수 [1000000001001111]에 대해 모든 진법에서 배수다. 뒤에 딸린 숫자들을 바꿀 필요도 없게되는 것. 따라서 small범위에서 500개 답을 찾은다음.. 그냥 그걸 길이만 늘려서 large에 내면 된다.
• D : 약간 고민이 필요하지만 어렵지 않다. 구성된 문자열을 depth가 C인 perfect K-ary tree의 leaf node로 생각하자. 여기서 하나의 leaf node를 확인하는 것의 의미를 따져본다. 이게 G인 경우 G가 하나 이상 있다는 걸 바로 확인한 것으로 더이상 볼 필요가 없다. L인 경우 의미가 중요한데, 이는 루트로부터 해당 리프노드까지 경로상의 모든 노드가 L임을 확인시켜준다. 이것을 아이디어로 constructive algorithm을 구성한다. 우리가 알고싶은 것은 문자열 1~K 각각 대한 정보고, 만약 1번째 문자를 알고싶다고 할 때, 이는 어떤 서브트리에서든 첫번째 자식 하나만 확인하면 된다. 결국 0부터 시작하는 K진법으로 리프노드의 위치를 나타낼 때... 만약 K=8, C=4라면 \(0123_{(K)}\), \(4567_{(K)}\)를 확인하면 G의 존재여부를 확인할 수 있다. 즉 최소 \(ceil(K/C)\)만큼의 확인작업이 필요한 것.