https://codingcompetitions.withgoogle.com/codejam/round/0000000000051705/000000000008830b
疑似的な暗号化問題。
26個の素数が選ばれ、大小関係を維持したまま各アルファベットに割り当てられる。
アルファベットから構成される文章が各文字ごとに対応する素数に変換され、 隣り合う素数との積を取った数列が"暗号文"として生成される。
暗号文のみが与えられたとき、元の文章を求めよ。
なお、素数には2は選ばれず、暗号文にはA-Zすべての文字が含まれることが保証される。
とりあえず素因数分解はすぐに必要だとわかる。
例えば、A = 3, B = 5, C = 7としたとき、 ABCという文章は"15 35"と暗号化されるため、隣り合う暗号文の共通因数を取ることで、 5が使われていることがわかる。
とりあえず共通因数をすべて取れば大体のアルファベットに対応する素数が取れるが、 一番端が計算されていないため、暗号文をさらに各素数で計算してあげればよい。 素数の範囲は大きいが、文字数が少ないためこの手法ができる。
構成される素数がすべてわかったら、変換を行う。 変換には最初の文字が必要だが、これの判別が少し面倒。
平文の1文字目の素数は暗号文の1文字目から構成される素数の中から2つ可能性として出てくる。 これらの候補を次の暗号文の文字から計算すればよいのだが、 この時、以下のように判定に使う暗号文の位置によって文字列の反転されていくことがわかる。
このため、最初の文字を求めるには、「2つの可能性のうちどちらで割り切れるか」だけでは不十分で ここに、「判別に使う暗号文までの距離」が必要。
ABCA => [15, 35, 21] BABCA => [15, 15, 35, 21] ABABCA => [15, 15, 15, 35, 21]
計算的には、 "15 35"で、15と35の間からここで5が使われているとわかったら、最初の文字は15 / 5 = 3であるが、
"15 15 35"で、同様に5が使われているとわかった場合、15 / (15 / 5) = 5が最初の文字となり、
同様に、"15 15 15 35"では、15/ (15 / (15 / 5 )) = 3が最初の文字となる。
もちろん"15 21"のように3が使われていれば、それぞれ逆になる。
これらを含めて偶奇で判断するようにして、最初の文字を判定すれば、そのあとは暗号文を割りながら変換していけばよい。
今思うと候補はたかが2つなのだから両方試して、矛盾が出たほうを切り捨ててもよかったなぁと思う。
import string import math def gcd(a, b): if b == 0: return a else: return gcd(b, a % b) def solve(N, L, S): Gs = [] for i in range(L - 1): if S[i] != S[i + 1]: g = gcd(S[i], S[i + 1]) Gs.append(g) Gs = list(set(Gs)) while len(Gs) != len(string.ascii_uppercase): for s in S: for g in Gs: c = s // g if s % g == 0 and c not in Gs: Gs.append(c) Gs = list(set(Gs)) dec_table = {g: c for c, g in zip(string.ascii_uppercase, sorted(Gs))} def find_first(S, table): s = S[0] for t in table: if s % t == 0: a, b = t, s // t break i = 0 while S[i] == s: i += 1 if S[i] % a == 0: i += 1 if i % 2 == 0: return b else: return a index = find_first(S, dec_table) ans = [dec_table[index]] for s in S: index = s // index ans.append(dec_table[index]) return "".join(ans) t = int(input()) for case in range(1, t + 1): N, L = tuple(map(int, input().split(" "))) S = list(map(int, input().split(" "))) print("Case #%d: %s" % (case, solve(N, L, S)))
実はこの問題、最後のコーナーケースがどうしても見つからなかった。 普段のコンテストだとあまりやらないが、 Qualificationで時間がたっぷりとれたので、自分で乱数生成して、暗号化して正しく複合できないケースを無理やり見つけられたのでよかった。 計算量確認もできるし、時間をかけたらかけただけモンキーテストが試せるので安心。
for _ in range(0, 10000): m = gen_map() str = string.ascii_uppercase * 10 + "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA" str = [c for c in str] random.shuffle(str) str = "".join(str) print(str) encrypted = encrypt(str, m) assert (solve(0, len(str) - 1, encrypted) == str)
https://codingcompetitions.withgoogle.com/codejam/round/0000000000051705/00000000000881de
Interactiveな問題。これ準備にめっちゃ時間かかった。去年のinteractive問題で試してなかったら多分できなかった。
壊れたworkercomputer群に入力をして、その出力結果から壊れたコンピュータを探す。
F=10だけ解けた。
コンピュータ数は1024までのため、10bitをフルに使って、00000 00000 から 11111 11111を並べ、縦に切り取った数値を投げる。
N=8として3bitで表現すると、以下の中から11110000と00110011と01010101を切り取ればよい。
000 001 010 011 100 101 110 111
これを投げて返ってきたデータを再度並べなおす。3回投げて返ってきた結果が以下だったとする。
000 001 011 100 110 111
これらの数値を10進数変換して、0 ~ Nの間で抜けているものを探せばよい。
F=10だとこれらの並び順の情報を一切使ってないので、F=5の時は並び順の情報も使えば行けるんじゃないかなとは思う。解説はまだ見てない。。
from sys import stderr, stdout def solve(N, B, F): outputs = ["" for _ in range(F)] for i in range(N): b = "{:010b}".format(i) for d in range(F): outputs[d] += b[d] response = [] for out in outputs: print(out, flush=True) stdout.flush() response.append(input()) resdata = ["" for _ in range(N - B)] for res in response: for i in range(N - B): resdata[i] += res[i] exists = [] for res in resdata: exists.append(int(res, 2)) ans = [] for i in range(N): if i not in exists: ans.append(str(i)) print(" ".join(ans), flush=True) verdict = input() if verdict == "1": return True else: return False t = int(input()) for case in range(1, t + 1): N, B, F = tuple(map(int, input().split(" "))) if not solve(N, B, F): break exit()
