Google Code Jam 2019 Qualification Round 全完でした
codingcompetitions.withgoogle.com
Foregone Solution
任意の一例を構築すれば良いだけなので適当に。
T = int(input()) N = [input() for _ in range(T)] for i, n in enumerate(N): A = '' B = '' for d in n: if d=='4': A+='2' B+='2' else: A+=d B+='0' print('Case #' + str(i+1) + ': ' + str(int(A)) + ' ' + str(int(B)))
You Can Go Your Own Way
深さ優先探索してみたらTest set1のみ通過するものの、Test set2(n<=1000)でTLE。 N*Nの正方形でこれも任意の一例を示せばよいだけなので、裏返すだけでよかった。
部分点解法
T = int(input()) N = [] L = [] for _ in range(T): n = int(input()) l = input() #lydia's move N.append(n) L.append(l) from collections import deque for i, [n, l] in enumerate(zip(N,L)): # i: case i+1 # n: n*n maze # l: lydia's move l_positions = [(1,1)] dq=deque() dq.append((0,(1,1),'')) for l_direction in l: if l_direction =='E': l_positions.append((l_positions[-1][0] + 1, l_positions[-1][1] + 0)) if l_direction =='S': l_positions.append((l_positions[-1][0] + 0, l_positions[-1][1] + 1)) #print(l_positions) while dq: j, position, way = dq.pop() #print(i, n, l, j, position, way) if position == (n,n): print('Case #' + str(i+1) + ': ' + way) break if position!=l_positions[j]: if position[0] < n and position[1] <n: dq.extend([(j+1, (position[0]+1, position[1]), way+'E'), (j+1, (position[0], position[1]+1), way+'S')]) elif position[0] ==n: dq.append((j+1, (position[0], position[1]+1), way+'S')) elif position[1] ==n: dq.append((j+1, (position[0]+1, position[1]), way+'E')) else: if l[j] =='E' and position[1] < n: dq.append((j+1, (position[0], position[1]+1), way+'S')) elif l[j] =='S' and position[0] < n: dq.append((j+1, (position[0]+1, position[1]), way+'E'))
満点解答
T = int(input()) N = [] L = [] for _ in range(T): n = int(input()) l = input() #lydia's move N.append(n) L.append(l) for i, l in enumerate(L): l=l.replace('S','_') l=l.replace('E','S') l=l.replace('_','E') print('Case #' + str(i+1) + ': ' + l)
Cryptopangrams
ユークリッドの互除法はmath.gcdで省力化。エッジケースをあまり考えずに実装して、test caseは通るものの、実際のtest setではRE．最初同じ文字が並ぶ場合を考慮していなかった。
T = int(input())
N = []
L = []
ciphertexts = []
for _ in range(T):
n, l = list(map(int, input().split()))
ciphertext = list(map(int, input().split()))
N.append(n)
L.append(l)
ciphertexts.append(ciphertext)
from math import gcd
#from fractions import gcd
for i, [n,l,ciphertext] in enumerate(zip(N,L,ciphertexts)):
# i: case i+1
# n: maximum of prime, 101<=n<=10000(test1), 1e100(test2)
# l: the length of the list of values in the ciphertext, 25<=l<=100
# ciphertext: list of ints: (the prime for X) * (the prime for Y)
prime_l=[]
p1 = gcd(ciphertext[0], ciphertext[1])
p0 = ciphertext[0]//p1
prime_l.append(p0)
for j in range(l):
prime_l.append(ciphertext[j]//prime_l[j])
cipher_dict={p:c for p, c in zip(sorted(list(set(prime_l))), 'ABCDEFGHIJKLMNOPQRSTUVWXYZ')}
print('Case #' + str(i+1) + ': ' + ''.join([cipher_dict[p] for p in prime_l]))
初めて2個めの数字が出てくる位置を検索して、同じ文字が並んでいる場合と、2つの文字が交互に並んでいる場合があることに注意しつつ微修正して無事通過。この初めて違う数字が出てくるインデックス、whileで回したのだけどもっとスマートな書き方がありそう。
T = int(input()) N = [] L = [] ciphertexts = [] for _ in range(T): n, l = list(map(int, input().split())) ciphertext = list(map(int, input().split())) N.append(n) L.append(l) ciphertexts.append(ciphertext) #from math import gcd from fractions import gcd for i, [n,l,ciphertext] in enumerate(zip(N,L,ciphertexts)): # i: case i+1 # n: maximum of prime, 101<=n<=10000(test1), 1e100(test2) # l: the length of the list of values in the ciphertext, 25<=l<=100 # ciphertext: list of ints: (the prime for X) * (the prime for Y) prime_l=[] j=0 while ciphertext[j]==ciphertext[j+1]: j+=1 q = gcd(ciphertext[j], ciphertext[j+1]) p = ciphertext[j] // q prime_l = [q if (k-j)%2 else p for k in range(j+1)] #print(ciphertext[j], ciphertext[j+1], p, q, prime_l) for k in range(l-j): prime_l.append(ciphertext[j+k]//prime_l[j+k]) cipher_dict={p:c for p, c in zip(sorted(list(set(prime_l))), 'ABCDEFGHIJKLMNOPQRSTUVWXYZ')} print('Case #' + str(i+1) + ': ' + ''.join([cipher_dict[p] for p in prime_l]))
Dat Bae
このタイトル、Data Baseからaとsが脱落したタイトルなのか。今気づいた。
Test set1のF=10までは比較的自然な発想。全ビットを見分けられるようなQueryを投げて、返りを適当に。n列目をnの2進数表記をして、それを1~F回目のqueryで1桁ずつ送るようにすると、返り値を列ごとに並べて2進数→intで列数に戻るので便利。 itertoolsとnumpyによる転置と、int('xxxx', 2)を駆使して実装。高級言語万歳。
from itertools import product import math import numpy as np def solution(): n, b, f = list(map(int, input().split())) # n of workers, broken workers, lines m = min(f, math.ceil(math.log2(n))) queries = np.array(list(product([0,1], repeat = m))[:n]).T responses = [] for i in range(m): print(''.join(queries[i].astype('str')), flush=True) responses.append([int(s) for s in input()]) responses = np.array(responses) correct = [int(''.join(r.astype('str')), 2) for r in responses.T] broken = [str(_) for _ in range(n) if _ not in correct] print(' '.join(broken), flush=True) assert(input()=='1') t = int(input()) for _ in range(t): solution()
そうはいってもこれだとF=5に対応できない。B<=15という意味深な条件があるが…。
16個選ぶとかならず1個は生きてるビットがあることに気づく。116, 016と16個ずつ並べれば個々の戻り列は、どの16個の中にあるか特定できるので、そのなかで残りの4列を24=16に使って解ける。
from itertools import product, groupby import math import numpy as np def solution(): n, b, f = list(map(int, input().split())) # n of workers, broken workers, lines f=5 # 1st line r = (n+31)//32 print((('0'*16+'1'*16)*r)[:n], flush=True) response=input() broken_in_blocks = [len(list(g)) for k, g in groupby(response)] # 2nd - 5th line r = (n+15)//16 query4_16 = np.array(list(product([0,1], repeat = 4))).T queries = np.tile(query4_16, (1,r))[:,:n] #print(queries) responses = [] for i in range(f-1): print(''.join(queries[i].astype('str')), flush=True) responses.append([int(s) for s in input()]) responses = np.array(responses) l=0 correct = [] for i in range(r): m = broken_in_blocks[i] correct.extend([i*16 + int(''.join(x.astype('str')), 2) for x in responses[:,l:l+m].T]) l+=m broken = [str(_) for _ in range(n) if _ not in correct] print(' '.join(broken), flush=True) assert(input()=='1') t = int(input()) for _ in range(t): solution()
