Google Code Jam 2019 Qualification Round : C. Cryptopangrams

また多倍長来たか。
https://codingcompetitions.withgoogle.com/codejam/round/0000000000051705/000000000008830b

問題

アルファベット大文字で構成される文字列Sに対し、以下のような暗号化を行う。

まず、N以下の素数26個を選び、昇順に並べ、A～Zをそれぞれ対応させる。
ここで文字cに対応する素数をf(c)とする。

文字列Sから、長さ|S|-1の整数列Aを生成する。
その際、A[i]=f(S[i])*f(S[i+1])とする。

N,Aが与えられたとき、Sを復元せよ。

解法

Aの隣接要素同士A[i],A[i+1]が異なるとき、そのGCDを取れば、GCDをgとして元の文字の(i+1)番目の文字の素数が求められる。
あとはそこから前後の文字に対応する素数を連鎖的に求めていこう。
Nや登場する素数が大きいので、多倍長整数とGCDが取れる環境を使うとよい。

import sys
import math

T=int(input())

for t in range(T):
	N,L=list(map(int,input().strip().split(" ")))
	A=list(map(int,input().strip().split(" ")))
	
	R=[0]*(L+1)
	for i in range(len(A)-1):
		if A[i]!=A[i+1]:
			g = math.gcd(A[i],A[i+1])
			R[i+1]=g
			for j in range(i+2,L+1):
				R[j]=A[j-1]//R[j-1]
			for j in range(i,-1,-1):
				R[j]=A[j]//R[j+1]
			break
	
	P=sorted(list(set(R)))
	rev={}
	for i in range(len(P)):
		rev[P[i]]=i
	
	S=""
	for r in R:
		S+=chr(ord('A')+rev[r])
	print("Case #%d: %s" % (t+1,S))

まとめ

昨年と比べて使える言語増えた？