대회 링크 : https://codeforces.com/contest/1705
A. Mark the Photographer (AC / 00:03 / Try : 1)
\(2n \) 개의 정수를 vector<int> \(v \)에 모두 받고 정렬합니다.
그 후, 0 \( \leq \)i < n 인 i 에 대하여 \(v[i]\) 와 \(v[i + n]\) 을 비교합니다.
만약 \( v[i] + h > v[i + n] \) 인 Case가 하나라도 생기게 된다면, 답은 "NO"입니다.
아니라면 답은 "YES"입니다.
대회 중에는 이러한 Greedy한 발상을 직관적으로 알아채고 풀었었습니다.
증명은 "정렬된 vector에서 \( v[i] + h > v[i + n] \) 인 Case가 하나라도 생기게 된다" \( \rightarrow \) "답이 NO"를 첫 번째로 보이고, "!(위의 가정)" \( \rightarrow \) "답이 YES"임을 각각 보이면 될 것 같습니다.
코드는 다음과 같습니다.
void main() {
int tc;
cin >> tc;
while (tc--) {
int n, h;
cin >> n >> h;
vector<int> v;
for (int i = 0; i < 2 * n; i++) {
int tmp;
cin >> tmp;
v.push_back(tmp);
}
sort(v.begin(), v.end());
bool broken = false;
for (int i = 0; i < n; i++) {
if (v[i] + h > v[i + n]) {
broken = true;
break;
}
}
if (broken) cout << "NO" << '\n';
else cout << "YES" << '\n';
}
}B. Mark the Dust Sweeper (AC / 00:23 / Try (Tries): 1 (2?))
첫 번째로 나오는 0이 아닌 숫자부터 마지막 바로 전 숫자까지의 0의 갯수를 세면, 채워야 하는 0의 갯수를 셀 수 있습니다.
청소를 하는 순서는 "0을 먼저 채운다" \( \rightarrow \) "뒤에서부터 끝까지 먼지를 민다" 순입니다.
즉, (처음부터 맨 끝 바로 전 칸 까지의 총 먼지의 수) + (채워야 하는 0의 갯수)를 하면 답이 나옵니다.
저는 코드에 혹시 몰라서 치워야 하는 먼지가 없는 경우 따로 0을 출력하게 했는데, 지금 생각해보니까 필요가 없었네요.
코드는 다음과 같습니다.
int main() {
int tc;
cin >> tc;
while (tc--) {
int n;
cin >> n;
vector<ll> v;
bool nonzero = false;
int first_nonzero = 0;
int zeros = 0;
ll sum = 0;
for (int i = 0; i < n; i++) {
ll tmp;
cin >> tmp;
if(i!=n-1) sum += tmp;
v.push_back(tmp);
if (tmp != 0) {
if (!nonzero) {
nonzero = true;
first_nonzero = i;
}
}
else {
if (nonzero && i != n - 1) {
zeros++;
}
}
}
if (!nonzero)cout << 0 << '\n';
else cout << sum + zeros << '\n';
}
}(+)
1. Tries가 (2?)인 이유는 마음이 급해져서 복붙할 때 괄호를 하나 뺐습니다. 결국 둘다 23분대 제출이라 결과에는 영향이 없었습니다.
2. 마음이 급해진 이유는 문제를 잘못 읽어서 말렸기 때문입니다. nonzero가 아니라 증가수열에서 먼지를 옮길 수 있을 때 최소 횟수를 구하는 상상 속의 문제를 풀었습니다. 예제 3번째 테스트케이스가 이상하게 12가 나와야 하는데 왜 11이 나오지? 라는 생각을 시작으로 문제를 잘못 읽었다고 깨닫고 다시 원래 문제로 돌아갔습니다. 누가 이거 문제로 내주시면 감사하겠습니다. 이 아이디어 무단 도용 하셔도 돼요.
C. Mark and His Unfinished Essay (AC / 01:24 / Try : 1)
첫 번째 발상은 "다 해보기"입니다. 이게 될리가 없기 때문에 구현까지는 하지 않았습니다.
한동안 풀이를 떠올릴 수 없어서 다른 문제를 보고 다시 와서 보니 누적합과 재귀를 이용한 아이디어가 떠올랐습니다.
풀이는 다음과 같습니다.
1. 문자열 복사 과정에서 복사된 문자열의 수만큼 누적합을 구합니다.
2. 문자열 복사 과정에서 복사를 시작한 문자열의 위치를 기록합니다.
3. 문자 출력 과정에서 숫자가 들어오면, 구해놓은 누적합을 통해서 어떤 부분이 복사된 곳인지를 알아냅니다.
4-1. 만약 복사된 부분이 문자열의 길이보다 작다면, 해당 문자열에서 그 부분을 출력합니다.
4-2. 만약 복사된 부분이 문자열의 길이보다 크다면, 3의 과정으로 돌아갑니다.
이걸 구현한 코드는 다음과 같습니다.
ll bin_s(vector<ll>& v, ll tmp) {
ll s = 0, e = v.size();
while (s + 1 < e) {
ll m = (s + e) / 2;
if (v[m] < tmp) s = m;
else e = m;
}
return e;
}
ll query(vector<ll>& nujeok, vector<ll>& start, ll tmp, int len) {
//cout << tmp << " * " << len << '\n';
if (tmp <= len) return tmp;
ll x = bin_s(nujeok, tmp);
ll less = nujeok[x] - tmp;
ll next = start[x] + nujeok[x] - nujeok[x - 1] - less - 1;
//cout << less << ' ' << x << ' ' << next << '\n';
return query(nujeok, start, next, len);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int tc;
cin >> tc;
while (tc--) {
int l, c, q;
cin >> l >> c >> q;
string s;
cin >> s;
vector<ll> nujeok;
vector<ll> start;
nujeok.push_back(l);
start.push_back(0);
for (int i = 0; i < c; i++) {
ll tmp1, tmp2;
cin >> tmp1 >> tmp2;
nujeok.push_back(nujeok.back() + tmp2 - tmp1 + 1);
start.push_back(tmp1);
}
for (int i = 0; i < q; i++) {
ll tmp;
cin >> tmp;
cout << s[query(nujeok, start, tmp, l) - 1]<<'\n';
}
}
}(+)
1. 대회때 "누적"을 뜻하는 영어단어가 안떠올라서 누적합 벡터 이름 "nujeok" ㅠㅠ
D. Mark and Lightbulbs ( - / - / Try : 0)
기본적인 접근은 C보다도 빠르게 했지만, 사고 과정에서 실수가 있었습니다.
기본적으로 왼편에 있는 1/0 여부, 오른편에 있는 1/0 여부, 1로 이루어진 Group의 개수를 통해 가능 여부를 판단했습니다.
여기서 실수를 하는데, 001000 - 001100 - 001010이 자연스럽게 되는 연산이라고 판단해서 위와 아래의 Group의 개수가 같은 때가 아닌 위가 Group이 아래보다 더 적거나 같은 경우를 가능한 경우로 판단했습니다.
1을 오른쪽 왼쪽으로 옮기는 경우 2의 cost가 들고, Group의 크기를 늘리는 경우 1의 cost가 들기 때문에 Group의 개수가 같은 경우에 대해서는 Greedy하게 n번째에 있는 Group끼리 연결해서 cost를 계산하면 되는 문제지만, 잘못된 판단으로 인해서 아래가 더 적은 경우에서 답을 찾지 못해서 포기했습니다. 개인적으로 코포치면서 가장 아쉬운 순간이 아닐까 싶네요.
(+)
1. 코포를 6번밖에 안쳐서 아쉬운 순간을 떠나서 그냥 "순간" 자체가 많이 없었긴 했지만...
E. Mark and Professor Koro ( - / - / Try : 0)
이 문제를 Round 진행 당시에 보고 든 생각은 2개였습니다.
1. 문제 틀이 세그 기본 문제하고 매우매우 비슷하다.
2. 들어오는 모든 수에 대해서 답은 \( int(log_2({\sum 2^i})) \)이다.
1을 쓰자니 풀이를 모르겠고 2를 쓰자니 제가 아는 선에서 TLE가 납니다.
못풀겠어요.
F. Mark and the Online Exam( - / - / Try : 0)
문제 딱 한줄 읽고 버렸습니다.
"Interaction"
감사합니다.
결과
32가 오르긴 했는데 배치 Boost 50점 감안하면 18점 떨어졌네요.
골랜디 열심히 돌리겠습니다.