처음에는 새벽 3시에 시작하는 줄 알았는데 알고보니 새벽 2시 35분에 시작하는 것 같아서 30분 정도 불고 계속 루프를 돌았다.
A. 접두사 및 접미사 배열
https://codeforces.com/contest/1794/problem/A
문제 – A – 코드 힘
codeforces.com
알고리즘 분류: Brute Force, String
이 문제의 제목을 먼저 보세요. 후위 배열 및 LCP 배열나는 $( $suffix array & lcp array $)$를 기억했다.
그리고 코딩을 하다가 10분정도 있다가 문득 lcp배열을 쓸까 하는 생각이 들었습니다.
문자열 > 접미사 배열하지만 지금 문제 접미사 배열 > 문자열그래서 방법 자체가 잘못됐다는 걸 깨달았다.
그리고 돌이켜보면 내가 생각해낸 알고리즘 입력 접두사는 문자열의 접미사입니다.
그래서 L이 문자열의 길이라면 $L – 1$ 길이의 문자열 2개원래 문자열을 찾으려면.
길이가 $L – 1$인 문자열을 각각 $A와 B$로 명명하고 $A와 B$를 다음과 같이 정의하면,
$$ A := a_{1}a_{2}\cdots a_{L – 1} $$
$$ 비 := b_{1}b_{2}\cdots b_{L – 1} $$
원래 문자열은 $Ab_{L – 1} = a_{0}B$ 또는 $Ba_{L – 1} = B_{0}A$입니다.
나는 원래 문자열을 가지고 펠린드롬 체크결과를 출력합니다.
AC$ ($00:59$ )$
B. 공유하지 마세요
https://codeforces.com/contest/1794/problem/B
문제 – B – 코드 힘
codeforces.com
알고리즘의 분류: 그리디 알고리즘
문제 유도$ a_{1} ~ a_{i} $가 문제 조건에 맞게 변환되면, $a_{i+1}$ 변환설사 $ a_{1} ~ a_{i}$는 조건을 그대로 충족당신은 그것을 볼 수 있습니다
그러므로 $a_{1} $부터 적은접근 $ a_{i + 1}\ \equiv \ 0 \ (mod \ a_{i}) $ then $ a_{i + 1} $ 1 증가하다 $ ( $-1 WA$ ) $
다시 생각해봐, $a_{i} $가 1인 경우 $ a_{i + 1} $는 a_{i + 1}\ \equiv \ 0 \ (mod \ a_{i})$이므로 이 경우 $는 아무리 $가 변형되어도 $ 일체 포함} $를 1 증가시킨 후 다시 확인하십시오. $ ( $-2 WA$ ) $
$1 1 3$$a_{1}$와 같은 입력이 1이면 $2 1 3$$a_{2}$는 $a_{1}$로 나눌 수 없으므로 그대로 계속합니다.
$a_{2}$가 1이므로 $2 2 3$이때 이전에 검색한 $a_{2}$를 a_{1}로 나누어 문제를 일으킨다.
따라서 모든 입력이 1이면 2로 변경됩니다.
그리고 $a_{i+1}$가 $a_{i}$로 나누어지면 1씩 증가합니다.
$a_{i}$마다 최대 2까지 증가하므로 최대 $2n$까지 증가합니다.
AC$ ( $01:20$ ) $
C. 스코어링 서브시퀀스
https://codeforces.com/contest/1794/problem/C
문제 – C – 코드 힘
codeforces.com
알고리즘의 분류: 그리디 알고리즘
$(a_{1}, a_{2}, \ \cdots \ a_{k}) $ 사이의 값이 가장 큰 구간을 $(a_{i}, a_{i + 1}, \ \cdots \ a_{j} ) $라고 하자. 그 다음에 $ a_{i} \ \leq \ a_{k + 1} $$j = k$이므로,
부분 $ (a_{i}, a_{i + 1}, \ \cdots \ a_{k}) $ $ \leq $ 간격 $ (a_{i + 1}, a_{i + 2}, \ \cdots \ a_{k + 1}) $.
그러므로 대기줄$a_{k + 1}$의 값을 대입하고 앞에서 빼는 경우와 빼지 않는 경우를 비교한다.
빼지 않은 케이스가 커질 때까지 반복$를 하다 ( $욕심$ ) $
AC$ ( $01:52$ ) $
마지막 3634등으로 했습니다.
30분 일찍 모든 작업을 완료했다고 다시 계산했을 때 1500번째를 끝낼 수 있었기 때문에 조금은 아쉬운 랩이었습니다.