Codeforces Round #515 (Div. 3)

### Codeforces Round #515 (Div. 3)  ###

Problem: http://codeforces.com/contest/1066

Tutorial: http://codeforces.com/blog/entry/62419

A.

#include <cstdio>
#include <vector>
using namespace std;
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int L, v, l, r;
        scanf("%d%d%d%d", &L, &v, &l, &r);
 
        int ans = L/v;
        ans -= r/v;
        ans += (l-1)/v;
        printf("%d\n", ans);
    }
    return 0; 
}

>> 문제를 이해하기가 어려웠지만, 테케의 힌트를 통해 이해할 수 있었다.

>>  lanterns 이 뭔진 모르겠지만, v 간격으로 있는데, 구간 [L, R] 에 있는 것은 제외해야한다.

>> (전체 갯수) - (R을 포함하는 구간까지의 갯수) + (L-1 을 포함하는 구간까지의 갯수) 가 정답이 된다.

B.

#include <cstdio>
 
int h[1001];
 
int main()
{
    int n, r;
    scanf("%d%d", &n, &r);
 
    int ans=0;
    for(int i=0; i<n; i++) 
        scanf("%d", h+i);
    
    // [pos-r+1, pos+r-1]
    int cur = n-r;
    while(n > 0) {
        bool turn=0;
        for(int i=cur; i<n; i++) {
            if(i >= 0 && h[i]) {
                cur = i-r-r+1;
                n = i;
                ans++;
                turn = 1;
                break;
            }
        }
        if(!turn) { ans=-1; break; }
        if(cur+r <= 0) break;
    }
 
    printf("%d\n", ans);
    return 0; 
}

>> 대회 시간중에는 풀지 못한 문제.

>> 히터를 pos 위치에서 키면 히터가 켜지는 범위는 [pos-r+1, pos+r-1] 이 된다.

>> 여기서 14라인 이후 n은 n번째부터는 확실하게 히터가 켜진 상태라고 정의하였다.

>> 그렇다면 n-1번째까지 켜지게 하기 위해서는 n-r 번째 부터 확인을 해야한다. (15번 라인)

>> 다음으로 i번째 히터를 켰다고 가정하면, i번째 이후로는 모두 히터가 켜져있다고 생각하면 된다. n = i;

>> 현재 i-r+1 번째까지도 히터는 켜져 있는 상태. i-r+1 을 n'이라고 생각하면 n'-r번째. 즉, i-r-r+1 번째에 히터가 있으면 베스트다.

>> 하지만, [i-r-r+1, i-r+1) 구간까지 히터가 없다면, [i-r+1, i) 까지의 히터를 켜서라도 [i-r-r+1, i-r+1) 구간에 히터의 영향을 받게 해야한다.

>> 맨 우측부터, cur+r 까지는 히터의 영향을 받은 구간이므로, 이 값이 0이면 모두 히터의 영향을 받는 상태.

C. 

#include <cstdio>
#include <vector>
#include <map>
using namespace std;
 
int deq[500000];
 
int Min(int a, int b)
{
    return a < b ? a : b;
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    char cmd;
    int id, L, R;
    L = R = 250000;
    map<int, int> mii;
 
    while(tc--) {
        scanf(" %c%d", &cmd, &id);
 
        if(cmd == 'L') {
            deq[L] = id;
            mii[id] = L--; 
        }
        else if(cmd == 'R') {
            deq[++R] = id;
            mii[id] = R;
        }
        else { // '?'
            int idx = mii[id];
            int ans = idx-L-1;
            ans = Min(ans, R-idx);
            printf("%d\n", ans);
        }
    }
    return 0;
}
 
 

>> 덱과 맵을 이용하여 해결했다. 간이덱을 만들긴 했지만, 실질적으로 덱을 위한 배열은 없어도 됐다.

>> 6, 27, 31 라인 삭제 후 32라인을 mii[id] = ++R; 로 수정해도 된다.

D.

E.

F.