결과
링크 2023.02.12 DIV2
3솔, 3283/9339 (35.1%) 1420 (-22) (퍼포1257)
A를 6트만에, B를 3트만에 맞으면서 점수를 너무 많이 깎였다. D는 거의 풀기 직전까지 갔는데 아쉽게 못풀었다. 너무 당황을 많이 해서 실수를 많이 한 듯 하다. 경험이 부족한 내 한계, 차분하고 꼼꼼하게 문제에 접근하는 습관을 들여야겠다.
A Yet Another Promotion
개요
00:18:48
N개의 물건을 m+1 혜택을 받으며 개당 a원에 구입하거나, 그냥 개당 b원에 구입하면서 들이는 비용의 최솟값
접근
너무 많이 막혔고, 여러번 시도했고, 결국 어렵게 풀었다. 핑계라도 대보자면 대회 직전까지 14238을 정리하다가 정신이 없었다.
문제가 헷갈리는데, 헷갈릴수록 천천히 쓰면서 접근해야 한다. m번의 구매로 m+1개를 얻을 수 있다. 이때 이렇게 상황을 가정할 수 있다.
- a <= b인 경우를 생각하자. 직관적으로 b를 적게 사용해야 할 것 같은데 사실 부등호가 여기서 끊기면 안된다. 그렇다면 혜택을 받는 것이 이득인 구간은 어디일까?
- m+1 개를 구매한다고 생각하자. a만 사용하면 a×m을, b만 사용하면 b×(m+1)을 비용으로 들일 것이다. 그럼 만약 a×m <= b×(m+1)라면? 이때는 a를 사용하는 것이 최선이다. 따라서 아래처럼 정리할 수 있다.
// a*m <= b*(m+1), 혜택을 최대로 max_promotion = n/(m+1) remain = n-max_promotion*(m+1) answer = max_promotion*(a*m)+remain*b?? (X) answer = max_promotion*(a*m)+remain*min(a,b) (O)위의 사례에서 혜택을 최대로 받았다. 그러면 나머지는 b의 개수인가? 아니다. 만약 a가 더 작다면 남은 것이 m개 미만이라도 a를 이용해 사는 것이 좋다. 따라서 혜택을 받은 나머지에는 min(a,b)를 곱해야 한다.
두 번째 상황, a×m > b×(m+1)인 경우, 이 때는 혜택을 아예 안 받는 것이 최선이다. 그러면 min(a,b)×n을 하면 된다. 튜토리얼은 다르게 했는데 그냥 이게 단순하다.
Source code
// 불필요한 부분 주석처리
#include <iostream>
using namespace std;
using ld = long long;
void test() {
ld a, b, n, m;
cin >> a >> b >> n >> m;
ld p, q;
ld ans = min(a,b)*n;
// p = (n+m)/(m+1), q = n-p*(m+1);
// if (q < 0) q = 0;
// ans = min(ans, m*a*p+min(a,b)*q);
p = n/(m+1), q = n-p*(m+1);
// if (q < 0) q = 0;
ans = min(ans, m*a*p+min(a,b)*q);
cout << ans << "\n";
}
int main() {
int t;
cin >> t;
while(t--) test();
}B Fedya and Array
개요
00:56:23
인접한 원소의 차이가 1이면서 극대값의 합이 x, 극소값의 합이 y인 배열
접근
뇌정지를 너무 많이 준 문제, 특히 극대극소의 "합"에 집중하면서 초반에 당황을 많이했다. 하지만 조건을 잘 읽으면 코드를 더럽지 않게 짤 수 있다.
우선 예시들의 사례가 (양수,음수)임에 주목했다. 그래서 (+,+), (+,-), (-,+), (-,-)의 네 가지 경우를 나눠보려 했다.
우선 (+,-), 예시를 잘 보면 전체 개수는 절댓값의 합 × 2이다. 이게 왜지? 하고 생각하다가 매 순간의 선택지를 이렇게 구성하면 되는 것을 알았다.
(+) -> /\ * abs(n) (-) -> \/ * abs(n)양수면 높이가 1인 윗봉우리를 절댓값만큼, 음수면 높이가 1인 아랫봉우리를 절댓값만큼 그려주면 됐다. 예를 들면
(5, -3) /\/\/\/\/\ \/\/\/ -> {0,1,0,1,0,1,0,1,0,1,0,-1,0,-1,0,-1}여기까지 하고 문제가 생각보다 쉽게 풀릴거라는 것을 알았다. 다만 내가 쉽게 생각하지 못했다. 다음으로 (+,+). 처음엔 8,5와 같은 수를 생각했다.
둘 다 양수이므로 (+,-)의 방법은 사용할 수 없다.
출발점을 바꿔보기로 했다. 0이 아닌 자리에 대해서 막 해보다가 시간을 많이 썼다. 그렇게 수많은 삽질 후에 출발이 0이 아니어야 한다는 것은 확신을 가졌고, 시간이 꽤 지나서야 5에서 8로 올라갔다 다시 5로 내려가면 되는것이구나 하는 생각을 했다.(8,5) /\ / 8 / \ / 7 / \/ 6오른쪽의 3개는 가상으로 그린 것이다. 이렇게 N모양을 만들면 극대가 8, 극소가 5가 된다. 이 단순한 생각을 하는데 10분이 넘게 걸린 것이다.
이후로는 두 값의 차이에 대해 생각했다. 여기서도 실수를 한 것이 두 값의 차이가 0이 나올 수 없고, 0보다 작을 수도 없는데 abs를 씌우고 0인 경우도 고려했다. 참고로 두 값이 같다면 어떤 경우에도 경로를 만들 수 없다.
값의 차이가 1인 경우를 처음에는 분리해서 생각했다. 이게 끝점과 처음점이 연결되어있다는 생각을 하기가 쉽지 않아서 많이 헤맸다. 그런데 작대기를 두 개만 그리면 됐다. 처음엔 하나인줄 알았다.
(4,3) /\/
따라서 y에서 x까지 올라가고, x에서 y까지 내려가면 끝, 길이는 (x-y)*2이다.
Source code
#include <iostream>
using namespace std;
using ld = long long;
void up(ld s, ld e) {
for (ld i=s; i<e; i++)
cout << i << " ";
}
void down(ld s, ld e) {
for (ld i=s; i>e; i--)
cout << i << " ";
}
void test() {
ld a, b;
cin >> a >> b;
ld d = a-b;
cout << d*2 << "\n";
up(b, a);
down(a, b);
cout << "\n";
}
int main() {
int t;
cin >> t;
while(t--) test();
}C Dora and Search
개요
01:21:32
[L,R]에서 L,R이 최대, 혹은 최소가 되지 않도록 하는 어떤 L,R 구하기
접근
마찬가지로 당황을 많이 했고 규칙 찾기가 너무 어려웠다. 뭔가 투포인터의 냄새가 났지만 내가 투포인터를 맞게 쓸 자신이 없었다.
그래서 접근을 좀 그지같이 했다. 세그트리를 써 볼 생각도 하고, 완탐 해 볼 생각도 하고, swap을 써야하나 하다가 뒤큰수,뒤작수,앞큰수,앞작수도 구해보고 했는데 다 부질 없는 것 같아서 투 포인터로 찍었고 테케가 풀리길래 그냥 제출했다. 말하자면 틀왜맞했다.
왜 될까? 원리는 생각보다 단순하다. 양쪽에서 최소나 최대를 배제하면서 이동하면 되는데, 만약 배제되었다면 그 다음 최소나 최댓값을 찾으면 된다. 이게 무슨 말이냐.
1 6 3 2 5 4 7 X - - - - - X1-7이 안된다는 것은 쉽게 확인할 수 있다. 그 말은 a[1]이나 a[7]이 최대 또는 최소라는 것이고, 그 둘을 포함하는 어떤 경우에도 둘은 최대나 최소가 된다. 그러므로 둘다 배제한다.
1 6 3 2 5 4 7 // min=1, max=7, 1탈락, 7탈락 X 6 3 2 5 4 X // min=2, max=6, 6탈락 X X 3 2 5 4 X // min=2, max=5, 3생존, 4생존 -> [3, 6]
둘다 생존가능하면 [왼쪽,오른쪽]이 답이 된다. B에서 너무 겁을 줘놓고 C는 논리가 너무 정직했다. 풀어놓고도 찝찝했다.
Pseudo code
while (l < r)
if (a[l] = max)
l--, max--
else if (a[l] = min)
l++, min++
else if (a[r] = max)
r--, max--
else if (a[r] = min)
r--, min++
else
return {l, r}Source code
#include <iostream>
using namespace std;
#define N 200010
int a[N];
void test() {
int n;
cin >> n;
for (int i=1; i<=n; i++)
cin >> a[i];
int l, r, s, e;
l = 1, r = n;
s = 1, e = n;
while(l < r) {
if (a[l] == s)
l++, s++;
else if (a[l] == e)
l++, e--;
else if (a[r] == s)
r--, s++;
else if (a[r] == e)
r--, e--;
else {
cout << l << " " << r << "\n";
return;
}
}
if (l==r)
cout << "-1\n";
}
int main() {
int t;
cin >> t;
while(t--) test();
}D Moscow Gorillas
개요
WA
등장하지 않은 수 중 최솟값이 같은 공통 연속 부분 수열의 개수
접근
아마 D까지 풀었다면 레이팅이 올랐을거고 첫 4솔도 할 수 있을거라 많이 아쉽다. 에디토리얼이 내 풀이랑 너무 비슷해서 더 아쉬운 문제. 심지어 에디토리얼은 이해를 못해서 그냥 다시 풀어봤더니 풀렸다.
등장하지 않은 수란 무엇일까? 예시부터가 왜 16인지, 11인지 이해하기가 복잡한데, 2번째 예시를 보자.
// X : 고르면 안됨, O : 골라야 함, ? : 상관 없음 7 3 6 2 1 5 4 6 7 2 5 3 1 4 ? ? ? ? X X ? // MEX = 1 -> (4+3+2+1) + 1 = 11 ? ? X X O O ? // MEX = 2 -> (1+1) = 2 ? X O O X O ? // MEX = 3 -> (x) ? O O O O O X // MEX = 4 -> (1+1) = 2 ? O O X O X O // MEX = 5 -> (x) X ? X O O O O // MEX = 6 -> (x) O O O O O O O // MEX = 7 -> 1 => 16이렇게 풀어야만 쉽게 해결할 수 있다. 풀이의 핵심은 뭐냐, 만약 MEX가 2가 되려면 2를 포함하는 집합은 고르면 안된다. 또한 1은 반드시 포함해야 한다. 이를 일반화하면 MEX가 n이려면 [1,n-1]을 포함해야 하고 n을 포함하면 안된다.
여기까지 다 구해놓고 구현을 잘 못해서 못 풀었다. 진짜 급한 성미가 죄다.이걸 어떻게 판단하냐? i번 for문을 돌면서 i와 i-1의 위치관계를 지속적으로 비교해주면 된다. MEX=2로 만들기 위한 아래 예시들을 보자.
// 1) a[i], b[i] 모두 a[i-1], b[i-1]보다 뒤에 있는 경우 ......2...3........ ....2.........3.... |--|...|-|.........2를 포함하면서 3을 포함하지 않으려면 (2의 왼쪽)과 (2의 오른쪽 & 3의 왼쪽)이 가능하다.
// 2) a[i], b[i] 모두 a[i-1], b[i-1]보다 앞에 있는 경우 ......3...2........ ....3.........2.... .......|-|.....|--|2를 포함하면서 3을 포함하지 않으려면 (3오2왼)과 (2오)가 가능하다.
// 3) 포함되는 경우 ........2.......3.. ....3......2....... .....|-|....|--|...이때는 (3오2왼)과 (2오3왼)이 된다. 1은 고려 안하냐? 안한다. 왜냐하면 우리가 사용할 것은 사실 2의 위치가 아니라 1과 비교하여 업데이트된 1,2 포함 구간의 왼쪽과 오른쪽이기 때문이다.
즉 [1,n-1]을 거치며 비교해 온 최소 최대와 a[n],b[n]의 위치관계를 통해 MEX = n을 만족하는 경우를 구할 수 있다. 이 말이 복잡한데 달리 설명할 방법이 없다.정답에 더해줄 때는 위에서 구한 두 값을 곱해 더한다. 왜냐? 왼쪽에는 선택지 개수가 왼쪽값만큼, 오른쪽에는 선택지 개수가 오른쪽 값만큼 존재하기 때문이다.
마지막으로 MEX = n+1과 MEX = 1일 때를 고려하자. n+1일 때는 당연하겠지만 전체 수열이므로 1개이다. 1일때는 (1왼)과 (1오), (1사이) 이렇게 세개가 된다.
Pseudo code
a[i], b[i] = index_of_i
lbn = left_before_n = min(a[1],b[1])
rbn = right_before_n = max(a[1],b[1])
// n+1일 때, 1왼, 1오, 1사이
ans = 1 + sigma(lbn-1) + sigma(n-rbn) + sigma(rbn-lbn-1)
for (i = 2~n)
ln = min(a[i], b[i])
rn = max(a[i], b[i])
// 둘 다 뒤에 있음
if (rbn < ln)
// n왼n-1오 * n-1왼
ans += (ln-rbn)*(lbn)
// 둘 다 앞에 있음
else if (rn < lbn)
// n오n-1왼 * n-1오
ans += (lbn-rn)*(n-rbn+1)
// 사이에
else if (lbn < [ln,rn] < rbn)
// n왼n-1오 * n오n-1왼
ans += (ln-lbn)*(rbn-rn)
rbn = max(a[i],b[i],rbn)
lbn = min(a[i],b[i],lbn)Source code
// upsolving
#include <iostream>
using namespace std;
#define N 200010
using ld = long long;
ld a[N], b[N];
ld sum(ld n) {
if (n > 0)
return n*(n+1)/2;
return 0;
}
int main() {
ld n;
cin >> n;
ld x;
for (int i=1; i<=n; i++) {
cin >> x;
a[x] = i;
}
for (int i=1; i<=n; i++) {
cin >> x;
b[x] = i;
}
ld p, q;
ld r, s;
ld ans = 1;
p = max(a[1], b[1]);
q = min(a[1], b[1]);
ans += sum(q-1)+sum(n-p)+sum(p-q-1);
for (int i=2; i<=n; i++) {
r = max(a[i], b[i]);
s = min(a[i], b[i]);
if (p < s)
ans += (q)*(s-p);
else if (r < q)
ans += (n-p+1)*(q-r);
else if (s < q && p < r)
ans += (q-s)*(r-p);
p = max(p, r);
q = min(q, s);
}
cout << ans << "\n";
}'코드포스 > Rated' 카테고리의 다른 글
| Educational Codeforces Round 149 (0) | 2023.05.26 |
|---|---|
| Codeforces Round 874 (0) | 2023.05.20 |
| Educational Codeforces Round 148 (0) | 2023.05.13 |
| Codeforces Round 872 (0) | 2023.05.09 |
| Codeforces Round 858 (0) | 2023.03.22 |
| Codeforces Round 851 (0) | 2023.02.10 |
| Codeforces Round 848 (0) | 2023.02.08 |
| TypeDB Forces 2023 (0) | 2023.02.08 |
댓글