bubbler   2년 전

49381796, 57474209, 59280282, 59398220 등의 풀이가 현재 통과하고 있는데, 이들은 공통적으로 색깔과 닉네임을 hash set에 넣어놓고, 각 팀명의 모든 가능한 prefix 길이에 대해 그 prefix와 나머지 suffix가 두 set에 들어있는지를 체크합니다. 색깔이 존재하는지 체크할 때 해시 값이 맞는지 검사한 후 문자열 전체가 맞는지 한번 더 검사하는데, 길이 1부터 1000까지의 모든 prefix의 검색이 성공하면 1000^2의 시간이 걸리고, 이것이 Q~20000번 반복되므로 TLE를 받아야 합니다.

아래 코드로 생성되는 데이터를 추가해 주세요.

djm03178   1년 전

i + j + k + l + c * n 들을 추가할 메리트가 있나요? Prefix든 suffix든 문자열 비교는 앞에서부터 하니까 c * n + i + j + k + l 들만 있어야 최악의 케이스가 될 것 같은데, PyPy3 기준 한쪽을 집중공략해야 16초가 나오는지라 절반이 잘리면 TLE가 안 날 것 같아요. 그리고 가능하면 더미들로 colors, name 각각 4000개를 채우는 편이 set 접근 자체도 조금이라도 더 느리게 하지 싶기도 하네요.

댓글을 작성하려면 로그인해야 합니다.