Codeforces Round #392 (Div. 2)

Codeforces Round #392 (Div. 2): http://codeforces.com/contest/758

드디어 나에게도 이런 날이...

A. Holiday Of Equality

모든 숫자를 가장 큰 수로 맞추기 위해 더해줘야 하는 값을 계산하는 문제

#include <cstdio>
#include <algorithm>
using namespace std;
int v[101];
int main() {
    int n;
    scanf("%d",&n);
    int mx=0;
    for(int i=0; i<n; i++) {
        scanf("%d", &v[i]);
        mx=max(v[i],mx);
    }
    int ans=0;
    for(int i=0; i<n; i++) {
        ans+=(mx-v[i]);
    }
    printf("%d", ans);
    return 0;
}

B. Blown Garland

전구가 4개 있는데, 4개 단위마다 1개씩 전구가 있어야 한다.

그런데 그 중 전구 몇개는 꺼져있다고 한다.

꺼지기 전 전구 상태가 위에서 말한 조건을 무조건 만족하고,

모든 색깔의 전구는 반드시 적어도 1개는 켜져있다고 한다.

그냥 4개씩 계속 같은 형태로 나올 수밖에 없다.

상당히 빠르게 캐치해서 코딩을 했는데 약간 시간이 걸렸다.

#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
int chg(char c) {
    if(c=='R') return 1;
    else if(c=='B') return 2;
    else if(c=='Y') return 3;
    else if(c=='G') return 4;
    else return 0;
}
int cnt[101], ans[5];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
 
    int ansi=0;
    int n=s.size();
    for(int i=0; i<n; i+=4) cnt[chg(s[i])]++;
    for(int i=1; i<=4; i++) if(cnt[i]) ansi=i;
    ans[ansi]=cnt[0];
 
    memset(cnt,0,sizeof(cnt));
    ansi=0;
    for(int i=1; i<n; i+=4) cnt[chg(s[i])]++;
    for(int i=1; i<=4; i++) if(cnt[i]) ansi=i;
    ans[ansi]=cnt[0];
 
    memset(cnt,0,sizeof(cnt));
    ansi=0;
    for(int i=2; i<n; i+=4) cnt[chg(s[i])]++;
    for(int i=1; i<=4; i++) if(cnt[i]) ansi=i;
    ans[ansi]=cnt[0];
 
    memset(cnt,0,sizeof(cnt));
    ansi=0;
    for(int i=3; i<n; i+=4) cnt[chg(s[i])]++;
    for(int i=1; i<=4; i++) if(cnt[i]) ansi=i;
    ans[ansi]=cnt[0];
 
    for(int i=1; i<=4; i++) printf("%d ", ans[i]);
 
    return 0;
}

C. Unfair Poll

다들 풀고 지나갔는데, 나만 한참동안 못풀어서 너무 우울했던 문제...

그런데 아는 사람중에 백준님빼고 나만 맞음. ㄷㄷ

이런 문제는 계산하면 99%틀리게 되어있다.

그렇게 생각하고 무식하게 다 해보기로 생각했다.

아 근데.. 코드가 너무.. ㅠㅠㅠㅠ

1등 C번 코드가 나랑 알고리즘은 정확히 같은데 너무너무 간결하게 짰다.

보고 배우자!

종료 5분 남기고 겨우 제출한 코드.

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cassert>
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> vvll;
typedef pair<ll,ll> pll;
const ll inf = 0x3f3f3f3f3f3f3f3f;
vvll cnt(201, vector<ll>(201,0ll));
vvll rcnt(201, vector<ll>(201,0ll));
ll getser(int n, int m, int x, int y, vvll& cnt) {
    return cnt[x-1][y-1];
}
pll getmnmx(int n, int m, int x, int y, vvll& cnt) {
    ll mx=0, mn=inf;
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            mx = max(mx, cnt[i][j]);
            mn = min(mn, cnt[i][j]);
        }
    }
    return pll(mn,mx);
}
ll count_forward(int n, int m, int x, int y, vvll& cnt, int s, ll lim) {
    for(int i=s; i<n; i++) {
        for(int j=0; j<m; j++) {
            cnt[i][j]++;
            lim--;
            if(lim==0ll) return -1;
        }
    }
    return (n-s)*m;
}
ll count_backward(int n, int m, int x, int y, vvll& cnt, ll lim) {
    for(int i=n-2; i>=0; i--) {
        for(int j=0; j<m; j++) {
            cnt[i][j]++;
            lim--;
            if(lim==0ll) return -1;
        }
    }
    return (n-1)*m;
}
void plus(int n, int m, vvll &cnt, vvll &rcnt) {
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            cnt[i][j]+=rcnt[i][j];
        }
    }
}
void print(ll ser, pll mnmx) {
    printf("%lld %lld %lld\n", mnmx.second, mnmx.first, ser);
}
int main() {
    ll n,m,k,x,y;
    scanf("%lld%lld%lld%lld%lld",&n,&m,&k,&x,&y);
 
    if(n==1) {
        ll ret = count_forward(n,m,x,y,cnt,0,k);
        if(ret<0) {
            print(getser(n,m,x,y,cnt), getmnmx(n,m,x,y,cnt));
            return 0;
        }
 
        ll d=0ll;
        k-=ret;
        d+=ret;
 
        ll mul = k/d+1;
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                cnt[i][j]*=mul;
            }
        }
        k%=d;
        if(k==0) {
            print(getser(n,m,x,y,cnt), getmnmx(n,m,x,y,cnt));
            return 0;
        }
 
        ret = count_forward(n,m,x,y,cnt,0,k);
        if(ret<0) {
            print(getser(n,m,x,y,cnt), getmnmx(n,m,x,y,cnt));
            return 0;
        } else {
            k-=ret;
            d+=ret;
        }
 
    }
 
    ll ret = count_forward(n,m,x,y,cnt,0,k);
    if(ret<0) {
        print(getser(n,m,x,y,cnt), getmnmx(n,m,x,y,cnt));
        return 0;
    } else k-=ret;
    ret = count_backward(n,m,x,y,cnt,k);
    if(ret<0) {
        print(getser(n,m,x,y,cnt), getmnmx(n,m,x,y,cnt));
        return 0;
    } else k-=ret;
 
    ll d=0ll;
    ret = count_forward(n,m,x,y,rcnt,1,k);
    if(ret<0) {
        plus(n,m,cnt,rcnt);
        print(getser(n,m,x,y,cnt), getmnmx(n,m,x,y,cnt));
        return 0;
    } else {
        k-=ret;
        d+=ret;
    }
    ret = count_backward(n,m,x,y,rcnt,k);
    if(ret<0) {
        plus(n,m,cnt,rcnt);
        print(getser(n,m,x,y,cnt), getmnmx(n,m,x,y,cnt));
        return 0;
    } else {
        k-=ret;
        d+=ret;
    }
 
    ll mul = k/d+1;
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            rcnt[i][j]*=mul;
        }
    }
    k%=d;
    if(k==0) {
        plus(n,m,cnt,rcnt);
        print(getser(n,m,x,y,cnt), getmnmx(n,m,x,y,cnt));
        return 0;
    }
 
    ret = count_forward(n,m,x,y,rcnt,1,k);
    if(ret<0) {
        plus(n,m,cnt,rcnt);
        print(getser(n,m,x,y,cnt), getmnmx(n,m,x,y,cnt));
        return 0;
    } else {
        k-=ret;
        d+=ret;
    }
    ret = count_backward(n,m,x,y,rcnt,k);
    if(ret<0) {
        plus(n,m,cnt,rcnt);
        print(getser(n,m,x,y,cnt), getmnmx(n,m,x,y,cnt));
        return 0;
    } else {
        k-=ret;
        d+=ret;
    }
    return 0;
}

아래 코드는 unofficially 1등 한 W4yneb0t님 코드

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long in;
typedef vector<in> VI;
typedef vector<VI> VVI;
in n,m,rk;
in q(in x, in y){
    in k=rk;
    if(n==1){
        in c=k/m;
        k%=m;
        if(k>y)
            ++c;
        return c;
    }
    in tr=2*(n-1)*m;
    in c=k/tr;
    k%=tr;
    if(x!=0 && x!=n-1)
        c*=2;
    forn(i,n-1){
        if(i==x && k>y)
            ++c;
        k-=m;
    }
    for(in i=n-1;i>0;--i){
        if(i==x && k>y)
            ++c;
        k-=m;
    }
    return c;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    in x,y;
    cin>>n>>m>>rk>>x>>y;
    --x;
    --y;
    in mx=q(0,0);
    if(n>1){
        mx=max(mx,q(1,0));
        mx=max(mx,q(n-2,0));
    }
    in mn=q(0,m-1);
    if(n>1){
        mn=min(mn,q(n-1,m-1));
    }
    cout<<mx<<" "<<mn<<" "<<q(x,y)<<endl;
    return 0;
}

당연히 이 문제 풀고 나서는 뻗어버렸다.

저거 코딩이 너무 하드했음 ㅠㅠ

# 최종 스코어 # (Rank: 560/4990) +113

지금 이 코포 보고 좀 지나서 글을 쓴건데,

캠프 거의 끝나갈 때 쯤에 이렇게 제일 높은 레이팅을 찍으니까

여러모로 기분이 넘넘 좋았다 ㅠㅠ

거진 1년을 1500점도 넘지도 못하고 있었는데...

아무튼 이것만으로도 상당히 만족한다.

좀 더 열심히 해야지