Dashboard - Kickstart Round F 2018 - Google Code Jam
あーよかったさくっと解けた。
連続した文字列でのアナグラムを含んだ一致数を数える。
文字数が最大50文字なので、1文字の時、高々50パターン、2文字の時49パターン、、となる。 この状況では、50+1 * 25 < 1300程度にしかパターンができないので、それぞれcollections.Counterでカウント数をとっておき、 A,Bそれぞれでパターンを収集、マッチングさせる。
1300* 1300の力業でも計算量は大した量ではないので実装の楽さを優先して以下のように実装。 ほぼすべてデバッガーの実行時チェックなしで書けたのは良い感じ。
from collections import Counter def solve(A, B): L = len(A) acounters = [] bcounters = [] for i in range(1, L+1): for j in range(0, L-i+1): acounters.append(Counter(A[j:j+i])) bcounters.append(Counter(B[j:j+i])) c = 0 for a in acounters: if a in bcounters: c += 1 return c
