본문으로 바로가기

Codeforces Round #393 (Div. 2) (8VC Venture Cup 2017 - Final Round Div. 2 Edition): http://codeforces.com/contest/760


system에서 나가지 않은걸 다행으로 생각하면서...

bs만 나오면 벌벌떠는 습관을 고쳐야 함을 다시 한번 깨달은 코포셋


A. Petr and a calendar

아 일단 달력나오면 너무 싫다. ㅠㅠ

m월에 1일이 d일에 시작할 때, 해당 월은 몇 주까지 필요한지 맞춰야 하는 문제

A번 문제는 테케만 봐도 무슨 문제인지 아는데, 이건 뭔 말인지 조금 알아보는데 오래걸렸음;;

1
2
3
4
5
6
7
8
9
10
#include <cstdio>
using namespace std;
int month[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int main() {
    int m,d;
    scanf("%d%d",&m,&d);
    int sum = d+month[m];
    printf("%d", (sum+5)/7);
    return 0;
}
cs



B. Frodo and pillows

orange4glace님이 그러는데, 프로도가 호빗에 해당하는지 몰랐다고 한다. ㅋㅋㅋㅋ

프로도가 호빗이란건 상식인걸까? ㅋㅋㅋ


근데 이 문제... ㄷㄷ

무쟈게 틀렸다.


계속 왜틀렸는지 몰라서 끙끙거리다가

결국 D를 보다가 나중에 다시 B로 돌아와서 겨우 풀었는데

내가 무슨 문제에서 빠트린 조건이 있나 보려고

구글번역기 키고 넣어봤더니...

아니 세상에.. 호빗에게 적어도 1개의 베개가 필요하다니 ㅠㅠㅠㅠ

아놔......................................


이것만 아니었어도 레이팅이 2점 떨어질일은 없었는데 ㅠ

아쉽다.

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
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
ll n,m,k;
ll chk(ll z) {
    ll ret = 0;
    ll a = max(1-k+z,1LL), b=max(z-n+k,1LL);
    ll alen,blen;
    if(a==1LL) {
        alen=z;
        ret+=k-z;
    } else alen=k;
    if(b==1LL) {
        blen=z;
        ret+=n-k+1-z;
    } else blen=n-k+1;
 
    ret+=(a+z)*alen/2+(b+z)*blen/2-z;
    return ret;
}
int main() {
    scanf("%lld %lld %lld",&n,&m,&k);
    ll lo=1LL, hi=m;
    if(m==1return 0&puts("1");
    if(n==1return 0&printf("%lld\n",m);
    while(lo<hi) {
        ll mid = (lo+hi)>>1;
        if(chk(mid)<=m) lo=mid+1;
        else hi=mid;
    }
    printf("%lld\n", lo-1ll);
    return 0;
}
cs

저번에 처음 탑코더 볼때에도 삼분탐색이 나왔었는데,

이번에는 이분탐색...


근데 이분탐색 돌릴때마다 시스템에서 나갈까봐 너무 조마조마하다.

특히 이번에 탑코더 삼분탐색문제는 +2를 안해서 틀렸는데,

정수에 대한 값을 3분탐색할 때에는 아래와 같이 코딩해야 한다는 깨달음을 얻었다. ㅠㅠ

1
2
3
4
5
6
for(int i=0; i<1000; i++) {
    long long midl = (l*2+r)/3;
    long long midr = (l+r*2 +2)/3;
    if(chk(somthing)) l=midl;
    else r=midr;
}
cs


오늘 이분탐색은 sgc109님이 캠프때 알려줬던 형식대로 썼다.

확실히 나는 저 방법이 제일 맞는 것 같다. ^^ (sgc님 ㄱㅅ)



C. Pavel and barbecue

일단 아직 못봤다.

B풀다가 자꾸 틀려서 D를 봤기 때문...



D. Travel Card

문제를 1시간 넘게 봤는데도 이해를 못했다.

아니 대체 왜 103에서 20루블을 쓰냐고... ㅠㅠㅠㅠ

나는 이전 input에서 특정 시간에 티켓을 샀으면 그 이후부터 티켓이 적용되는 줄 알았다.

나중에 orange4glace님께 들어보니 46에서 90분짜리 티켓을 샀다고 해서 그게 135분까지 지속되는건 아니고,

103을 고려할때에는 다시 처음부터 하나씩 들여다 봐야 한다고 했다.

그래서 13(처음)일 때 90분짜리 티켓을 사면 102분까지 유효하니까 103에서는 1trip용 티켓을 20루블에 사야한다고 함 ㅠ


문제 딱 보자마자 min({f(x-a)+20, f(x-90)+50, f(x-1440)+120}); 형태의 DP가 떠올랐는데,

문제를 이해하지 못해서 결국 손도 못댔다.


아ㅏㅏㅏㅏㅏ 나 이거 풀 수 있는데ㅔㅔㅔㅔㅔㅔ ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

이따가 동근이 만나고 와서 풀어봐야겠다.



E. Nikita and stack

자~ 나중에 풀어보자 ㅋ



F. Bacterial Melee

콘테중에 솔브한 사람이 한명밖에 없던 문제... 어렵나보다.



# 최종 스코어 # (Rank: 1053/3224) -2




2점 떨어져서 아쉽긴 하지만,

그래도 시스템 채점에서 안나간게 어디냐...

특히 이번에 B번은 시스템에서 거의 나갈 수 없게

프리테스트 아주 꼼꼼하게 해줘서 좋았던 것 같다.


smu님은 다시 blue를 회복했고,

갓오렌지님도 D를 솔브하시면서 상승세에 돌입한거 같았다. :D


이제 코포가 9일 있다가 다시 열리는 듯 한데,

그 전까지 캠프문제좀 풀고

밀린 코포 문제들도 좀 풀어야겠다.


오늘 밀린 코포 일기 4개나 썼네.. 이제 밀리지 말아야지.