결과
링크 2023.02.09 DIV2
3솔, 1165/15956 (7.3%) 1442 (+118) (퍼포1742)
B,C번을 빨리 풀면서 3솔까지 1시간 안에 끊을 수 있었다. 덕분에 초딱이 탈출! 다 풀고 4솔 시도했는데 TLE 떴다
A One and Two
개요
00:03:09
1과 2로 이루어진 배열에서 왼쪽과 오른쪽의 곱이 같아지는 최소 인덱스
접근
- 앞에 1분 정도는 직접 곱해서 푸는 문제인가? 했음. 근데 1은 곱할 필요가 없네. 그러면 2만 곱하면 되는거니까 아하 2의 개수를 세는 거구나.
- 처음에는 답이 여러개인 스페셜저지 문제인 줄 알고 + 인덱스를 0부터 잡는 바람에 WA받음.
- 1부터 세어주면서 전체 2의 개수를 저장하고 절반이 될 때 인덱스를 return 하면 됨.
Pseudo code
count_all = 0
for (1~n)
if (a[i] == 2)
count_all++
count_half = 0
for (1~n)
if (a[i] == 2)
count_all--, count_half++
if (count_all == count_half)
return i
return -1Source code
#include <iostream>
using namespace std;
int test() {
int n;
cin >> n;
int a[n+1];
int b = 0;
int c = 0;
for (int i=1; i<=n; i++) {
cin >> a[i];
if (a[i] == 2)
b++;
}
for (int i=1; i<n; i++) {
if (a[i] == 2)
b--, c++;
if (b==c)
return i;
}
return -1;
}
int main() {
int t;
cin >> t;
while (t--)
cout << test() << "\n";
}B Sum of Two Numbers
개요
00:18:11
모든 자리수 합의 차이가 1이하가 되도록 n을 두 수로 나누기
접근
생각보다 너무 어려운 것 같아서 잠깐 헤맸음. 우선 짝수면 n/2하면 아예 두 수가 같은 수니까 된다는 것까진 알겠는데 홀수는 어쩌지? 23 같은 수는 11 12로 나누면 되는데, 19999같은 수는?
23 -> (23/2, 23/2+1) = (11,12) (O) 19999 -> (9999, 9999+1) = (9999,10000) (X)아 그러면 끝자리가 9인 경우에 대해서만 특이하게 해볼까? 하다가 굳이 끝자리만 고려할 필요가 있나? int로 푸는 문제가 아니구나 하는 걸 깨달음. 문자열로 풀어야 겠구나.
n번째 자리수를 s[n]이라하면 s[n]이 짝수이면 바로 절반 나눠주면 됨. 홀수면? (절반, 절반+1)로 나눠주면 되는데 그러면 한쪽에만 +1이 몰빵되면서 차이가 1보다 커지겠네... 그러면 아하 서로 번갈아서 (절반, 절반+1), (절반+1, 절반)을 주면 되겠구나
마지막으로 leading zero 제거해주고 출력해주면 됨.
Pseudo code
for (n : string)
if (n = 짝수)
a[i] = n/2, b[i] = n/2
else
// d = 홀수 등장 횟수
// d가 홀수이면 (h+1, h) 짝수이면 (h, h+1)
add = (d++)%2
a[i] = n/2+add, b[i] = n/2+!addSource code
#include <iostream>
using namespace std;
void test() {
string s,a,b;
int c = 0;
cin >> s;
int l = s.size();
for (int i=0; i<l; i++) {
a.push_back('0');
b.push_back('0');
int n = s[i]-'0';
a[i] += n/2;
b[i] += n/2;
if (n%2) {
(c%2?a:b)[i]++;
c++;
}
}
int sa = 0, sb = 0;
while(a[sa]=='0' && sa<l-1) sa++;
while(b[sb]=='0' && sb<l-1) sb++;
cout << a.substr(sa,l) << " " << b.substr(sb,l) << "\n";
}
int main() {
int t;
cin >> t;
while (t--) test();
}C Matching Numbers
개요
00:50:39
[1,2n] permutation에서 합이 1씩 차이나는 n개의 distinct pair 구하기
접근
생각보다 단순하게 풀릴거라는 건 알겠는데 규칙 찾기가 까다로웠음. 문제를 보고 힌트를 얻어보자. 짝수는 다 안되네? 진짜 안되나?
(1 ~ 2n) 합 = pair의 총합 = (2n+1)*n pair 개수 = n -> pair 합 평균 = pair의 중간값 = (2n+1) 가장 왼쪽 pair = 2n+1-((n-1)/2) 가장 오른쪽 pair = 2n+1+((n-1)/2)아하 2n+1-((n-1)/2)가 정수이려면 n이 홀수여야 하는구나. (n-1)인 이유는? 가장 가운데 원소 하나를 뺀 나머지 왼쪽 날개가 (n-1)/2개 이므로. 이후로는 n/2 = (n-1)/2이므로 편의상 n/2로 쓰려 한다.
그럼 pair를 어떻게 만드느냐 하는게 핵심인데, 이것도 문제의 힘을 빌리면, 1은 우선 2n이랑 pair를 만들자. n=9, 11을 그려보면서 하는게 도움이 많이 됐다.
n = 9 pairs = {{15,16,17,18},19,{20,21,22,23}} |------------------------------------------| 19 (1,2n) // left wing 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |----------------------------------| 18 (2,2n-2) |--------------------------| 17 (3,2n-4) |------------------| 16 (4,2n-6) |----------| 15 (5,2n-8) -> 2n-3 = 2n+1-n/2 // right wing 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |-----------------------------| 23 (6,2n-1) |---------------------| 22 (7,2n-3) |--------------| 21 (8,2n-5) |-----| 20 (9,2n-7)markdown이라 잘 보일지는 모르겠는데
- left, right wing을 따로 만든다 생각하고
- left wing을 만드려면 (2,2n-2)부터 (+1,-2)를 해주면서 이동하면 됨. 언제까지? pair의 합이 left_end인 2n+1-n/2가 될 때까지
- right wing을 만드려면 왼쪽값은 계속 +1만 해주고 오른쪽 값은 2n-1부터 -2 해주면서 이동하면 됨.
왜 이렇게 되냐? left_end의 pair는 (1+n/2, n+1)인데, 1+n/2 < n+1은 반드시 만족하므로 left wing은 반드시 구성 가능함. 그럼 right wing을 남은 원소로 구성가능하냐? 하는건데
// 남은 왼쪽 원소 = 2+n/2 ~ n (+1) = {6,7,8,9} // 남은 오른쪽 원소 = 2n-1 ~ n+2 (-2) = {17,15,13,11} // 이미 구성된 pair = 2n+1-n/2 ~ 2n+1 = {15,16,17,18,19} // 필요한 pair = 2n+2 ~ 2n+1+n/2 = {20,21,22,23} left_end_of_right_wing = n+(n+2) = 2n+2 right_end_of_right_wing = (2n-1) + (2+n/2) = 2n+1+n/2남은 왼쪽원소는 +1씩, 오른쪽 원소는 -2씩 하면서 더해주면 pair합은 -1씩 될테고, 남은 원소를 모두 사용하며 필요한 pair가 모두 구성된다.
Pseudo code
pair[1] = 2n, pair[2n] = 1
// left wing
start = 2, end = 2n-2
while (s + e <= 2n+1-n/2)
pair[s] = e, pair[e] = s
s++, e-=2
// right wing
end = 2n-1
while (s < e)
pair[s] = e, pair[e] = s
s++, e-=2Source code
#include <iostream>
using namespace std;
void test() {
int n;
cin >> n;
if (n%2 == 0) {
cout << "No\n";
return;
}
n *= 2;
int a[n+1];
int b[n+1];
a[0] = 0;
b[0] = 1;
for (int i=1; i<=n; i++)
a[i] = 0, b[i] = 0;
a[1] = n, a[n] = 1;
int s, e;
s = 2, e = n-2;
while(!a[s]&&!a[e] && (s+e)>=1+n-n/4) {
a[s] = e, a[e] = s;
s ++, e -= 2;
}
e = n-1;
while(!a[s]&&!a[e]) {
a[s] = e, a[e] = s;
s ++, e -= 2;
}
cout << "Yes\n";
for (int i=1; i<=n; i++)
if (!b[i]) {
cout << i << " " << a[i] << "\n";
b[i] = 1, b[a[i]] = 1;
}
}
int main() {
int t;
cin >> t;
while (t--) test();
}D Moving Dots
개요
TLE
일부 원소를 빼고 왼쪽 혹은 오른쪽 중 가까운 점으로 이동할 때 구성하는 집합의 개수의 총합
접근
N = 3000이니까 죽어도 O(N^3)에는 안된다는 걸 머리로는 알았지만 가슴이 3중 루프를 시켰음. 5번 케이스에서 TLE가 뜬 걸보면 방법은 맞나 싶은데 O(N^2)으로 풀려면 방법이 아예 달라야 하는 것 같음.
방법은 우선 2,3개 부분집합은 무조건 1개로 수렴하니까 nC2, nC3을 더해주고, dp를 이용함.
dp는 어떻게? dp[m][e]는 m을 끝점의 왼쪽 점, e를 끝점으로 포함하며 집합을 구성할 때 집합의 수
갱신은 언제? 3개 점에 대해서 가운데 점이 왼쪽이 더 가까우면 오른쪽 점도 왼쪽 점의 집합으로 갈테니까 dp[m][e] = dp[s][m] 아니면 가운데점과 오른쪽 점이 새로운 집합을 구성하니까 dp[m][e] = dp[s][m]+1
그리고 s앞의 원소는 모두 빼는 경우를 제외하고 스위치처럼 포함/배제를 통해 부분집합을 구성할 수 있으니까
answer += dp[m][e]*(2^s-1)O(N^2)의 시도는 해보긴 했는데, 왼쪽점의 범위에 따라 000001111 이런식으로 1로 변하는 지점이 존재하고, 그점을 p라 하면 아래처럼
answer += (dp[s][m]+1)*sigma(1~m)(2^s-1) - sigma(1~p)(2^s-1) = (dp[s][m]+1)*(2^m-2)-(2^p-2)이렇게 해봤는데 테케 답이 도무지 나오지 않아서 실패함. 나오지 않은 이유는 끝나고 나서 당연히 보였는데 sigma(s=1~m)((dp[s][m]+1)*(2^s-1))을 해야 하는데 dp[s][m]+1을 sigma 밖으로 빼버렸다. 사실 s에 대해 dp[s][m]이 모두 다른가? 하는 것은 아직 의문이지만 답이 안나온데는 그만한 이유가 있지 않을까..
가장 큰 패착은 70분이라는 귀중한 시간을 3솔정도면 충분하다 생각하고 대충 보낸 것 같은데 다음부터는 4솔도 해낼 수 있다는 생각으로 최선을 다해봐야겠다. 우선 업솔빙을 해보자.
Tutorial을 읽어보니 O(n^2logn)에서 해결 가능하고 풀이도 내 풀이보다 단순했다. 한 집합을 구성하는 left, right에 대해 이 둘이 집합을 구성하는 것이 유효한 상황 내에서 left 왼쪽의 원소와 right 오른쪽의 원소는 스위치로 포함/배제 해주면 됐다.
C번 문제의 left/right wing 개념을 다시 사용해보자.dist = right-left rel = right_end_of_left_wing = left-dist ler = left_end_of_right_wing = right+dist start = lower_bound(rel) end = lower_bound(ler) ans += 2^(s) * 2^(n-e) = 2^(s+n-e)이게 되는 이유는? 중복은 안되나? 하는 생각이 막 들었는데
우선 되는 이유는 집합의 개수를 센다 = 두 원소가 집합을 이루는 경우 ++해준다와 같기 때문이었고
둘이 집합을 구성하는 것이 유효하지 않은 경우는? 하고 생각해보면 그 둘로만 이루어진 집합을 만들어버리면 되는거라서 가능했다.
중복이 안되는 이유는 lower bound를 해주기 때문인데 아래 상황을 가정하자.
// 어떤 두 (left,right) pair에 대해 r1+(r1-l1) = l2-(r2-l2) = v right_wing_of_pair1 = {v ~ max} left_wing_of_pair2 = {min ~ v-1}이므로 겹치는 v에 대해 서로 다른 두 pair가 집합에 포함시키는 경우가 없다.
Source code
// TLE
#include <bits/stdc++.h>
using namespace std;
const int R = 1e9+7;
const int N = 3010;
using ld = long long;
ld dp[N][N];
ld pp[N];
int main() {
int n;
cin >> n;
ld x[n];
for (int i=0; i<n; i++)
cin >> x[i];
pp[0] = 1;
for (int i=1; i<N; i++)
pp[i] = (pp[i-1]*2)%R;
sort(x,x+n);
ld ans = 0;
ld v, d;
ans += n*(n-1)/2;
if (n >= 3)
ans += (n*(n-1)*(n-2))/6;
for (int e=0; e<n; e++)
for (int s=0; s<e; s++)
dp[s][e] = 1;
for (int i=0; i<n; i++)
for (int e=0; e<i; e++) {
d = 0;
for (int s=e-1; s>=1; s--) {
if (x[e]-x[s] > x[i]-x[e])
d = 1;
v = (pp[s]-1)%R;
ans += ((dp[s][e]+d)*v)%R;
ans %= R;
}
dp[e][i] += d;
}
cout << ans;
}// upsolving
#include <bits/stdc++.h>
using namespace std;
const int R = 1e9+7;
const int N = 3010;
using ld = long long;
ld pp[N];
ld x[N];
int main() {
ld n;
cin >> n;
for (int i=0; i<n; i++) {
cin >> x[i];
}
pp[0] = 1;
for (int i=1; i<N; i++)
pp[i] = (pp[i-1]*2)%R;
ld ans = 0;
ld dist, rel, ler;
ld s, e;
for (ld r=0; r<n; r++)
for (ld l=0; l<r; l++) {
dist = x[r]-x[l];
rel = x[l]-dist;
ler = x[r]+dist;
s = lower_bound(x,x+n,rel)-x;
e = lower_bound(x,x+n,ler)-x;
ans += pp[s+n-e];
ans %= R;
}
cout << ans;
}'코드포스 > 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 852 (0) | 2023.02.13 |
| Codeforces Round 848 (0) | 2023.02.08 |
| TypeDB Forces 2023 (0) | 2023.02.08 |
댓글