코드포스 - 점수가 계속 하락 중
codeforce round #828(div 3), EDU #137(div 2) 업솔빙
codeforce round #828(div 3), EDU #137(div 2) 업솔빙
으음.. 요즘 계속 점수가 떨어지고 있다. 이러다가 뉴비까지 간다면 정말 부끄러워서 죽고싶을 것 같다.
실력이 늘고 있다는 생각도 잘 안들고, 점수는 오히려 낙하하니 멘탈이 많이 안좋아졌다.
그래서 구글에 코드포스 잘하는 법 같은걸 쳐서 좀 봤다.ㅋㅋ
그 중에서 인상깊었던 내용은 shift님의 글 이었다.
표본에 따라서 못해보일 수도 있고 어쨋든 실력은 늘고 있다는 것에 뭔가 힘이 났다.
어쨋든 나는 코드포스랑 끝장을 볼꺼니까 못해도 계속할 것이다.
어쨋든 828은 div3라 무난했고 5솔을 하며 블루퍼포가 나오는 줄 알았지만 open hack 때 hack당했다.(TLE)… 완전 절망이었다.
그리고 에듀라운드 137은….할많하않이다.
나는 에듀라운드를 잘 본적이 없다. 뒤에서 업솔빙하며 왜 망했는지 분석을 해보도록 하겠다.
828 A. A. Number Replacement(0:05)
이 전에 나왔던 숫자를 map으로 저장해두고 중간에 모순이 생기면 “NO”를 출력하면 된다.
828 B. Even-Odd Increments(0:14)
짝수+짝수 = 짝수, 짝수 + 홀수 = 홀수, 홀수 + 홀수 = 짝수
위 성질을 이용하면 된다.
828 C. Traffic Light(0:25)
문제이해가 조금 까다로웠지만 그냥 정해진 패턴이 계속 반복되고 초록불일 때 건널 수 있다.
그 때 가장 긴 대기시간만 찾으면 된다.
주어진 색깔의 idx를 저장하는 스택을 만들어 이를 해결했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
#define fast_io cin.tie(NULL); ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
int main(){
fast_io
int tt; cin >> tt;
while (tt--) {
int n; char c;
cin >> n >> c;
string traffic; cin >> traffic;
traffic += traffic;
stack<int> s;
int res = 0;
for(int i=0;i<traffic.size();i++){
if(traffic[i]==c) s.push(i);
if(traffic[i]=='g'){
while (!s.empty()) {
res = max(res, i-s.top());
s.pop();
}
}
}
cout << res << '\n';
}
}
828 D. Divisibility by 2^n(0:54)
문제는 꽤 간단한데 2의 거듭제곱의 순서가 까다로웠다. (예를 들면, 4가 6보다 먼저나옴)
- 2가 몇개 들어가는지 구한다.
- 내가 가진 수의 개수(i의 개수)에 2의 몇승 까지 들어갈 수 있는지 check한다.
아래 코드는 이 두가지 논리 중에 아랫부분만 썼다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int res = 0;
int k = 1, c=-1;
while (k<=n) {
k <<= 1;
c++;
}
k >>= 1;
for(;k!=1;k >>= 1, c--){
int p = n/k-n/(k<<1);
for(int i=0;i<p;i++){
cnt += c;
res++;
if(cnt >= n) break;
}
if(cnt >= n) break;
}
828 E1. Divisible Numbers (easy version)(upsolving)
E번은 꽤나 잘풀었는데 핵 당했다… 확인해보니 while문만 안썼어도 통과했을 것이다..
시간 복잡도가 nlogn으로 계산해서 넉넉할줄 알았는데 while문을 쓰면 안됐다 ㅠㅠ
내가 많이 하는 실수 중 하나인데 예를들어 9가 몇개 있어야 100을 넘어가냐 라고 한다면 9*(100/9+1)를 하면 되는데 이를 while문으로 찾다가 시간초과 나는 것이다.
아래 그 시간초과 난 코드를 기입했다.(여기서 while문만 빼면 답이다 ㅠㅠ)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
#define fast_io cin.tie(NULL); ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b){
if(a<b) return gcd(b, a);
return (!b ? a : gcd(b, a%b));
}
int main(){
fast_io
int tt; cin >> tt;
while (tt--) {
ll a, b, c, d;
cin >> a >> b >> c >> d;
ll p = a*b;
pll res = {-1, -1};
for(ll i=a+1;i<=c;i++){
ll g = gcd(p, i);
ll k = p/g;
ll cnt = 1;
while (k*cnt<=d) {
cnt++;
}
cnt--;
if(k*cnt>b){
res = {i, k*cnt};
}
}
cout << res.first << ' ' << res.second << '\n';
}
}
828 F. MEX vs MED(upsolving)
F인데 E2보다 쉬운것 같아서 풀다가 끝났다.
규칙은 찾아냈는데 0, 1, 2 이런식으로 원소들이 빠짐없이 있어야 MEX가 더 크다.
1
137 A. Password(0:03)
조합론 문제였다.
안쓰인 것 중 2개를 고르고 4자리 중 다시 2자리를 고르면 된다.
배열을 입력받은 것을 안쓰는게 낚시다.
137 B. Permutation Value(0:12)
1 n 2 n-1 3 n-2 .. 순으로 출력하면 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
#define fast_io cin.tie(NULL); ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
int main(){
fast_io
int tt; cin >> tt;
while (tt--) {
int n; cin >> n;
vector<int> ans(n+1);
for(int i=1;i<=(n+1)/2;i++){
ans[2*i-1] = i;
}
for(int i=n;i>(n+1)/2;i--){
ans[2*(n-i+1)] = i;
}
for(int i=1;i<=n;i++) cout << ans[i] << ' ';
cout << '\n';
}
}
137 C. Save the Magazines(upsolving)
이것 땜에 나락갔는데 냅색 테크닉 처럼 풀면 바로 풀릴 줄 알았따.
근데 내가 dp를 하지 않고 냅색처럼해서 시간 초과가 났다.
근데 여기서 뇌절인게 dp로 바꿔서 풀어야하는데 내풀이를 최적화 하려다가 망했다.
아래는 dp풀이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
#define fast_io cin.tie(NULL); ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAX = 2e5+1;
int n, res;
string s;
vector<int> a;
int dp[MAX][2]; //i번째의 상태가 state일 때 최댓값
int dfs(int idx, int state){
if(idx==n) return 0;
int &ret = dp[idx][state];
if(ret!=-1) return ret;
if(state){
ret = max(ret, a[idx]+dfs(idx+1, s[idx+1]-'0'));
}else{
if(s[idx+1]=='1'){
ret = max(ret, dfs(idx+1, s[idx+1]-'0'));
ret = max(ret, a[idx]+dfs(idx+1, s[idx+1]-'0'-1));
}else{
ret = max(ret, dfs(idx+1, s[idx+1]-'0'));
}
}
return ret;
}
int main(){
fast_io
int tt; cin >> tt;
while (tt--) {
cin >> n >> s;
a = vector<int> (n);
for(int i=0;i<n;i++) cin >> a[i];
memset(dp, -1, sizeof(dp));
cout << dfs(0, s[0]-'0') << '\n';
}
}
137 D. Problem with Random Tests(upsolving)
다음에 풀어 보려고 한다 ㅠㅠ 못건드린 문제다
137 E. FTL(upsolving)
나는 대회 중에는 이걸 잡았다.
냅색 테크닉으로 할 수 있을 것 같았기 떄문이다.
그런데 반례 찾기가 어려웠다.
마치 백준에서 유명한 라면사기 문제처럼 반례가 잘 안보이는 문제였다.
이런 문제는 뇌절하기가 참 쉽다.(뭔가 엄밀하게 생각하는 것도 좋을 것 같다 )
일단 내가 틀린 반례는 다음과 같다.
1
2
3
4
5
6
3 19
4 29
11 2
ans : 67
output : 77
무조건 둘을 같이 쏴야 이득이라고 생각했는데 충전시간이 짧은걸 쏘고 다른게 충전 되는동안 다시 충전해서 같이 쏘는 식으로 하는게 더 짧을 수 있다는 생각을 못했다.
이것은 한번에 계산하는게 아니라 1차적으로 같이 뎀지 넣어서 최솟값을 구하고 따로 최솟값을 구했던 것을 이용하여 구한다.
말이 좀 이상하다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
#define fast_io cin.tie(NULL); ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll INF = 1e16;
ll p1, p2, t1, t2, HP, S;
ll dp[5001], dp2[5001];
int main(){
fast_io
cin >> p1 >> t1;
cin >> p2 >> t2;
cin >> HP >> S;
if(t1==t2){
ll dam = p1+p2-S;
cout << ((HP+dam-1)/dam)*t1;
return 0;
}
for(int i=1;i<=HP;i++){
dp[i] = INF;
dp2[i] = INF;
}
for(int i=0;i<=HP;i++){
for(int j=0;i+j<=HP;j++){
if(i+j==0) continue;
ll time = max(t1*i, t2*j);
ll dmg = i*p1+j*p2-(i+j-(i&&j))*S; // dp[]에 댐지를 최대로 넣을수있는 상태를 저장
dmg = min(dmg, HP);
dp[dmg] = min(dp[dmg], time);
}
}
for(ll i=0;i<HP;i++){
for(ll j=0;j<=HP;j++){
if(dp[j]==INF) continue;
ll dmg = min(HP, i+j);
dp2[dmg] = min(dp2[dmg], dp2[i]+dp[j]);
}
}
cout << dp2[HP];
}
요즘 너무 못해서 참 힘들다… 그래도 버티고 하다보면 늘어가는 CP지식!이 되었으면 좋겠다.
못한다고 해서 그만둘것도 아닌데 찡찡대는 것은 그만해야겠다.!!