Problem:


MathJax.Hub.Config({
tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}
});

D: パスワード

問題

AOR イカちゃんは英小文字のみからなる強力なパスワードを作りたいと思っています。
友達から $N$ 個の危険なパスワードの例を教えてもらった AOR イカちゃんは、
以下の条件を全て満たすようなパスワードを作ることにしました。

    
長さは1文字以上である。

    
どの危険なパスワードの、どの連続した部分文字列とも異なる。

    
1, 2 の条件を満たした中で、最も短い文字列である。

    
1,2,3の条件を満たした中で、辞書順に並べたとき先頭に来る文字列である。

AOR イカちゃんに代わって強力なパスワードを生成するプログラムを書いてください。

入力

入力は以下の形式で標準入力から与えられる。

$N$

$S_1$

$\vdots$

$S_N$

1 行目には、文字列の数を表す整数 $N$ が与えられる。

2 行目からの $N$ 行には、文字列 $S_i$ が与えられる。

$|S_i|$ とは文字列の長さであり、1 文字以上である。

$1 \le N \le 100,000$ を満たす。

$1 \le \sum_{1\le i \le N} |S_i| \le 400,000$ を満たす。
 

文字列は英小文字のみを含む。

出力

答えを 1 行で出力せよ。また、末尾に改行も出力せよ。

サンプル

サンプル入力 1

5
password
login
admin
root
master

サンプル出力 1

b

サンプル入力 2

3
abcdefghijklmnopqrstuvwxy
qwertyuiopasdfghjklxcvbnm
qawsxedcrfvtgbyhnujmikolp

サンプル出力 2

z

サンプル入力 3

1
abcdefghijklmnopqrstuvwxyz

サンプル出力 3

aa



Sample input:
5
password
login
admin
root
master


Sample output:
b

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LS(): return input().split()
def I(): return int(input())
def F(): return float(input())
def S(): return input()


def main():
    n = I()
    a = [S() for _ in range(n)]
    def sn(s):
        r = 0
        for i in range(len(s)):
            c = ord(s[i]) - 96
            r = r*27+c
        return r

    def ns(n):
        r = ''
        while n > 0:
            r = chr(n%27+96) + r
            n //= 27
        return r

    for i in range(1,5):
        ss = set()
        for s in a:
            sl = len(s)
            for j in range(sl-i+1):
                ss.add(sn(s[j:j+i]))
        if len(ss) >= 26**i:
            continue
        for ia in itertools.combinations_with_replacement(range(1,27), i):
            t = 0
            for ti in ia:
                t = t*27+ti
            if t not in ss:
                return ns(t)
    return ''


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LS(): return input().split()
def I(): return int(input())
def F(): return float(input())
def S(): return input()


def main():
    n = I()
    a = [S() for _ in range(n)]
    def sn(s):
        r = 0
        for i in range(len(s)):
            c = ord(s[i]) - 96
            r = r*27+c
        return r

    def ns(n):
        r = ''
        while n > 0:
            r = chr(n%27+96) + r
            n //= 27
        return r

    for i in range(1,6):
        ss = set()
        for s in a:
            sl = len(s)
            for j in range(sl-i+1):
                ss.add(sn(s[j:j+i]))
        if len(ss) >= 26**i:
            continue
        for ia in itertools.combinations_with_replacement(range(1,27), i):
            t = 0
            for ti in ia:
                t = t*27+ti
            if t not in ss:
                return ns(t)
    return ''


print(main())

Submission status: Time Limit Exceeded

Solution code:
[
    print(x) + exit()
    for itertools in [__import__("itertools")]
    for S in [[input() for _ in range(int(input()))]]
    for n in range(max([len(s) for s in S]))
    for x in ["".join(X) for X in itertools.combinations_with_replacement("abcdefghijklmnopqrstuvwxyz", n + 1)]
    if x not in set([s[i:i+n+1] for s in S for i in range(len(s))])
]

Submission status: Time Limit Exceeded

Solution code:
[
    print("".join(x)) and exit()
    for S in [[input() for _ in range(int(input()))]]
    for n in range(max([len(s) for s in S]))
    for x in __import__("itertools").combinations_with_replacement("abcdefghijklmnopqrstuvwxyz", n + 1)
    if "".join(x) not in set([s[i:i+n+1] for s in S for i in range(len(s))])
]

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = ''
alf = ['.']
for i in range(ord('a'), ord('z')+1):
    alf.append(chr(i))
for i in range(n):
    s += input() + ' '

for a in alf:
    for b in alf:
        for c in alf:
            for d in alf:
                t = (a + b + c + d).replace('.', '')
                if t not in s:
                    print(t)
                    quit()

Submission status: Time Limit Exceeded

Solution code:
def make_alphabet(now_alphabet, alphabet):
    next_alphabet = []
    for n_al in now_alphabet:
        for al in alphabet:
            next_alphabet.append(n_al+al)
    return next_alphabet

a = int(input())
b = []
for a in range(a):
    b.append(input())
alphabet = [chr(ch) for ch in range(97,123)]
now_alphabet = alphabet
count=0
flag=0

while flag==0:
    letter = []
    for word in b:
        for i in range(len(word)-count):
            letter.append(word[i:i+1+count])
    letter = list(set(letter))
    for al in now_alphabet:
        if al not in letter:
            print(al)
            flag=1
            break
    count+=1
    now_alphabet = make_alphabet(now_alphabet, alphabet)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LS(): return input().split()
def I(): return int(input())
def F(): return float(input())
def S(): return input()


def main():
    n = I()
    a = [S() for _ in range(n)]
    def sn(s):
        r = 0
        for i in range(len(s)):
            c = ord(s[i]) - 96
            r = r*27+c
        return r

    def ns(n):
        r = ''
        while n > 0:
            r = chr(n%27+96) + r
            n //= 27
        return r

    for i in range(1,6):
        ss = set()
        for s in a:
            sl = len(s)
            for j in range(sl-i+1):
                ss.add(sn(s[j:j+i]))
        if len(ss) >= 26**i:
            continue
        for ia in itertools.product(range(1,27), repeat=i):
            t = 0
            for ti in ia:
                t = t*27+ti
            if t not in ss:
                return ns(t)
    return ''


print(main())

Submission status: Accepted

Solution code:
def make_alphabet(now_alphabet, alphabet):
    next_alphabet = []
    for n_al in now_alphabet:
        for al in alphabet:
            next_alphabet.append(n_al+al)
    return next_alphabet

a = int(input())
b = []
for a in range(a):
    b.append(input())
alphabet = [chr(ch) for ch in range(97,123)]
now_alphabet = alphabet
count=0
flag=0

while flag==0:
    letter = []
    for word in b:
        for i in range(len(word)-count):
            letter.append(word[i:i+1+count])
    rem = list(set(now_alphabet) - set(letter))
    if rem!=[]:
        print(sorted(rem)[0])
        flag=1
    count+=1
    now_alphabet = make_alphabet(now_alphabet, alphabet)

Submission status: Accepted

Solution code:
N = int(input())
S = []
for _ in range(N):
    s = input()
    S.append(s)
    
class RollingHash:
    def __init__(self, s, base=1007, mod=10**9+7):
        self.s = s
        self.length = length = len(s)
        self.base = base
        self.mod = mod
        self.h = h = [0] * (length + 1)
        for i in range(length):
            h[i + 1] = (h[i] * base + ord(s[i])) % mod
        self.p = p = [1] * (length + 1)
        for i in range(length):
            p[i + 1] = pow(base, i + 1, mod)

    def get(self, l, r):
        mod = self.mod
        return ((self.h[r] - self.h[l] * self.p[r - l]) + mod) % mod
    
    
H = [RollingHash(s) for s in S]

abcd = [chr(97+i) for i in range(26)]
sub_strs = ['']
#print(abcd)
l = 1
while 1:
    sub_set = set()
    for h in H:
        for i in range(len(h.s)-(l-1)):
            sub_set.add(h.get(i,i+l))
    
    tmp = []
    for s1 in sub_strs:
        for s2 in abcd:
            tmp.append(s1+s2)
    sub_strs = tmp[:]
    
    flag = False
    for s in sub_strs:
        h = RollingHash(s).get(0,len(s))
        if h in sub_set:
            continue
        else:
            flag = s
            break
    if flag:
        print(s)
        break
    l += 1

Submission status: Accepted

Solution code:
# coding:utf-8
# AOJ 2808 RUPC 2017 Password

import itertools

INF = float('inf')
MOD = 10 ** 9 + 7


def inpl(): return list(map(int, input().split()))


class RollingHash:
    def __init__(self, s, base, mod):
        self.s = s
        self.length = length = len(s)
        self.base = base
        self.mod = mod
        self.h = h = [0] * (length + 1)
        for i in range(length):
            h[i + 1] = (h[i] * base + ord(s[i])) % mod
        self.p = p = [1] * (length + 1)
        for i in range(length):
            p[i + 1] = pow(base, i + 1, mod)

    def get(self, l, r):
        mod = self.mod
        return ((self.h[r] - self.h[l] * self.p[r - l]) + mod) % mod


def solve():
    N = int(input())
    hash_list = []
    for _ in range(N):
        s = input()
        h1 = RollingHash(s, 103, MOD)
        hash_list.append((len(s), h1))

    ss = 'abcdefghijklmnopqrstuvwxyz'
    hash_set = set()
    for i in range(4 * 10 ** 5):
        for length, h1 in hash_list:
            for l in range(length - i):
                v1 = h1.get(l, l + i + 1)
                if v1 not in hash_set:
                    hash_set.add(v1)

        for s in itertools.product(ss, repeat=i + 1):
            v1 = RollingHash(s, 103, MOD).get(0, len(s))
            if v1 not in hash_set:
                return ''.join(s)

    return -1


print(solve())