I am dosa.

코드포스 - 점수가 계속 하락 중

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를 저장하는 스택을 만들어 이를 해결했다.

#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보다 먼저나옴)

  1. 2가 몇개 들어가는지 구한다.
  2. 내가 가진 수의 개수(i의 개수)에 2의 몇승 까지 들어갈 수 있는지 check한다.

아래 코드는 이 두가지 논리 중에 아랫부분만 썼다.

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문만 빼면 답이다 ㅠㅠ)

#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가 더 크다.

137 A. Password(0:03)

조합론 문제였다.
안쓰인 것 중 2개를 고르고 4자리 중 다시 2자리를 고르면 된다.
배열을 입력받은 것을 안쓰는게 낚시다.

137 B. Permutation Value(0:12)

1 n 2 n-1 3 n-2 .. 순으로 출력하면 된다.

#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풀이다.

#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)

나는 대회 중에는 이걸 잡았다.
냅색 테크닉으로 할 수 있을 것 같았기 떄문이다.
그런데 반례 찾기가 어려웠다.
마치 백준에서 유명한 라면사기 문제처럼 반례가 잘 안보이는 문제였다.
이런 문제는 뇌절하기가 참 쉽다.(뭔가 엄밀하게 생각하는 것도 좋을 것 같다 )
일단 내가 틀린 반례는 다음과 같다.

3 19
4 29
11 2

ans : 67
output : 77

무조건 둘을 같이 쏴야 이득이라고 생각했는데 충전시간이 짧은걸 쏘고 다른게 충전 되는동안 다시 충전해서 같이 쏘는 식으로 하는게 더 짧을 수 있다는 생각을 못했다.
이것은 한번에 계산하는게 아니라 1차적으로 같이 뎀지 넣어서 최솟값을 구하고 따로 최솟값을 구했던 것을 이용하여 구한다.
말이 좀 이상하다.

#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지식!이 되었으면 좋겠다.
못한다고 해서 그만둘것도 아닌데 찡찡대는 것은 그만해야겠다.!!

Leave a comment

2024

D&C Optimization

3 minute read

분할정복을 이용한 다이나믹 프로그래밍 최적화

Back to top ↑

2023

Back to top ↑

2022

Greedy

2 minute read

백준 18186번 라면사기(large) 문제풀이

SCC

2 minute read

백준 4196번 도미노 문제풀이

LCA

2 minute read

백준 3176번 도로 네트워크 문제풀이

2-SAT

2 minute read

백준 16367번 TV Show Game 문제풀이

Hashing

2 minute read

백준 21162번 뒤집기 K 문제풀이

Tree DP

1 minute read

백준 1949번 우수 마을 문제풀이

Trie

1 minute read

Trie 자료구조 이해하기

Merge Sort

1 minute read

merge sort를 이용하여 inversion 개수세기

Segment Tree

2 minute read

백준 11505 구간 곱 구하기 문제풀이

BFS

1 minute read

백준 2206 벽 부수고 이동하기 문제풀이

기하

1 minute read

백준 2166 다각형의 면적 문제풀이

이분탐색

1 minute read

백준 12015 가장 긴 증가하는 부분 수열2 문제풀이

누적 합

1 minute read

백준 10986 나머지합 문제풀이

Stack

1 minute read

스택 구현하기 ========== 자료구조의 기본이라고 하면 스택 과 큐가 있다 백준 10828번에서 마주친 스택

정렬1

1 minute read

매우매우 많은 정렬이 있지만 그중 가장 안 어려운 3가지를 공부해보았다.

Back to top ↑