How We Coding

Codeforces Round #515 (Div. 3)

PS/Code Force2018. 10. 16. 22:04

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


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

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



A.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#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; 
}
cs


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

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

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



B.

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
#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; 
}
cs


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

>> 히터를 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. 

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 <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;
}
 
 
cs


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

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



D.



E.



F.



'PS > Code Force' 카테고리의 다른 글

Codeforces Round #506 (Div. 3) // rated  (0) 2018.08.30
Codeforces Round #496 (Div. 3)  (0) 2018.08.12
Codeforces Round #498 (Div. 3)  (0) 2018.08.12
Codeforces Round #501 (Div. 3) // Rated  (0) 2018.08.02

Codeforces Round #506 (Div. 3) // rated

PS/Code Force2018. 8. 30. 00:16

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


Problems :  http://codeforces.com/contest/1029

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



A. Many Equal Substrings


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
#include <stdio.h>
 
int main()
{
    int n, k;
    int cnt=0, idx=0;
    char *s, t[55];
    scanf("%d%d%s", &n, &k, t);
 
    printf("%s", t);
 
    s = t+n-1;    
    for(int i=0; i<n-1; i++) {
        int ok=1;
        for(int j=0; s[j]; j++)
            if(s[j] != t[j])
                ok = 0;
        cnt++;
        s--;
        if(ok) idx = cnt;
    }
   
    for(int i=1; i<k; i++)
        printf("%s", t+idx);
    puts("");
    return 0;
}
 
cs


>> input 으로 4 4 abab 를 넣으면 output 으로  ababababab 가 나와야 한다.

>> 함정이 있는 문제. 

>> 최대로 서브스트링을 만들 수 있는 길이를 구한다음, 처음 문자열을 출력하고, 나머지 서브스트링만 k-1번 출력하였다.



B. Creating the Contest


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 <stdio.h>
 
int a[200005];
 
int main()
{
    int n;
    int s=0, e=1;
    int ans=0;
    scanf("%d", &n);
    
    for(int i=0; i<n; i++)
        scanf("%d", a+i);
 
    int tmp=1;
    for(int i=0; i<n-1; i++) {
        if(a[i]*2 >= a[i+1])
            tmp++;
        else {
            if(ans < tmp) ans = tmp;
            tmp = 1;
        }
    }
 
    if(ans < tmp) ans = tmp;
    printf("%d\n", ans); 
    return 0;
}
 
cs


>> 조건을 만족하는 배열의 최대 길이? 를 찾는 문제.

>> a[i]*2 >= a[i+1] 가 조건인데, 문제를 a[s]*2 >= a[e] 로 잘못 이해해서 한번 틀렸다..(내 점수..ㅜ)



C. Maximal Intersection (Ref)


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 <cstdio>
 
const int N = 300005;
 
int L[N], R[N];
int preL[N], sufL[N];
int preR[N], sufR[N];;
 
int Max(int a, int b)
{
    return a > b ? a : b;
}
 
int Min(int a, int b)
{
    return a < b ? a : b;
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for(int i=0; i<n; i++) 
        scanf("%d%d", L+i, R+i);
 
    preL[0] = sufL[n] = 0;
    preR[0] = sufR[n] = 1e9;
    
    for(int i=0; i<n; i++) {
        preL[i+1] = Max(preL[i], L[i]);
        preR[i+1] = Min(preR[i], R[i]);
        sufL[n-1-i] = Max(sufL[n-i], L[n-1-i]);
        sufR[n-1-i] = Min(sufR[n-i], R[n-1-i]);
    }
 
    int ans=0;
    for(int i=0; i<n; i++) 
        ans = Max(ans, Min(preR[i], sufR[i+1])-Max(preL[i], sufL[i+1]));
 
    printf("%d\n", ans); 
    return 0;
}
 
cs


>> 많이 틀려서 해설보고 제출했다..

>> pSum 처럼 prefixL과 suffixL, prefixR, 과 suffixR 을 만든 다음 minR - MaxL 이 정답이 된다.



>> 아래는 해설.

Intersection of some segments [l1,r1],[l2,r2],…,[ln,rn] is [maxi=1nli;mini=1nri]. If this segment has its left bound greater than its right bound then the intersection is empty.

Removing some segment i makes the original sequence equal to [l1,r1],…,[li−1,ri−1],…[li+1,ri+1],…,[ln,rn]. That can be split up to a prefix of length i−1 and a suffix of length n−i. Intersections for them can be precalced separately and stored in some partial sum-like arrays. Finally, you have to iterate over the position of the removed segment and calculate the intersection of prefix and suffix without this segment.

Overall complexity: O(n).



- 세그트리로도 될 것 같다. (된다.)


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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <stdio.h>
 
int n, ans;
int segL[1<<20];
int segR[1<<20];
int sIdx = 1<<19;
 
int Max(int a, int b)
{
    return a > b ? a : b;
}
 
int Min(int a, int b)
{
    return a < b ? a : b;
}
 
int maxL(int L, int R, int nodeN, int nodeL, int nodeR)
{
    int a, b;
    int mid = (nodeL+nodeR)/2;
    if(R < nodeL || nodeR < L) return 0;
    if(L <= nodeL && nodeR <= R) return segL[nodeN];
    a = maxL(L, R, nodeN*2, nodeL, mid);
    b = maxL(L, R, nodeN*2+1, mid+1, nodeR);
    return Max(a, b);
}
 
int minR(int L, int R, int nodeN, int nodeL, int nodeR)
{
    int a, b;
    int mid = (nodeL+nodeR)/2;
    if(R < nodeL || nodeR < L) return 1e9;
    if(L <= nodeL && nodeR <= R) return segR[nodeN];
    a = minR(L, R, nodeN*2, nodeL, mid);
    b = minR(L, R, nodeN*2+1, mid+1, nodeR);
    return Min(a, b);
}
 
int main()
{
    int s, e;
    scanf("%d", &n);
    for(int i=0; i<n; i++) 
        scanf("%d%d", segL+sIdx+i, segR+i+sIdx);
 
    s = sIdx>>1;
    e = sIdx;
 
    while(s) {
        for(int i=s; i<e; i++) {
            segL[i] = Max(segL[i<<1], segL[(i<<1)+1]); 
            segR[i] = Min(segR[i<<1], segR[(i<<1)+1]);
        }
        e = s;
        s = e>>1;
    }
    
    for(int i=0; i<n; i++) {
        int mL = Max(maxL(0, i-1, 1, 0, sIdx-1), maxL(i+1, n-1, 1, 0, sIdx-1)); 
        int mR = Min(minR(0, i-1, 1, 0, sIdx-1), minR(i+1, n-1, 1, 0, sIdx-1)); 
        ans = Max(ans, mR-mL);
    }
    printf("%d\n", ans);
    return 0;
}
 
cs




D.




E.




F.





'PS > Code Force' 카테고리의 다른 글

Codeforces Round #515 (Div. 3)  (0) 2018.10.16
Codeforces Round #496 (Div. 3)  (0) 2018.08.12
Codeforces Round #498 (Div. 3)  (0) 2018.08.12
Codeforces Round #501 (Div. 3) // Rated  (0) 2018.08.02

Codeforces Round #496 (Div. 3)

PS/Code Force2018. 8. 12. 00:43

Codeforces Round #496 (Div. 3) : http://codeforces.com/contest/1005



A.


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
#include <stdio.h>
 
int a[1002];
int cnt[1002];
 
int main()
{
    int n, ans=0;
    scanf("%d", &n);
 
    for(int i=0; i<n; i++)
        scanf("%d", a+i);
    a[n] = 1;
    
    int tmp=1;
    for(int i=1; i<=n; i++){
        if(a[i] == 1) {
            cnt[ans++] = tmp;
            tmp = 1;
        }
        else
            tmp++;
    }
 
    printf("%d\n", ans);
    for(int i=0; i<ans; i++)
        printf("%d ", cnt[i]);
    puts("");
    
    return 0;
}
 
cs


>> 1의 갯수 세기.



B.


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
#include <stdio.h>
#include <string.h>
 
int main()
{
    int sIdx, tIdx;
    char s[200005], t[200005]; 
    scanf("%s%s", s, t);
 
    sIdx = strlen(s);
    tIdx = strlen(t);
 
    sIdx--; tIdx--;
    while(sIdx >= 0 && tIdx >= 0) {
        if(s[sIdx] == t[tIdx]) {
            sIdx--; tIdx--;
        }
        else
            break;
    }
    printf("%d\n", sIdx+tIdx+2);
    return 0;
}
 
 
cs


>> 뒤에서부터 비교해나가기.



C.


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
#include <cstdio>
#include <algorithm>
using namespace std;
 
int a[120001];
bool check[120001];
int b[35];
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for(int i=0; i<n; i++)
        scanf("%d", a+i);
 
    sort(a, a+n);
 
    for(int i=0; i<31; i++) 
        b[i] = 1<<i;
 
    int ans=0;
    for(int i=0; i<n; i++) {
        for(int k=0; k<31; k++) {
            if(b[k] > a[i]) {
                auto it = lower_bound(a, a+n, b[k]-a[i]);
                if(*it == b[k]-a[i] && it-a != i)
                    check[i] = check[it-a] = 1;
            }
        }
    }
 
    for(int i=0; i<n; i++)
        if(!check[i])
            ans++;
 
    printf("%d\n", ans);
    return 0;
}
 
cs


>> lower_bound를 이용한 이진탐색



D.


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
#include <stdio.h>
 
int d[200005];
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int go(char *s, int idx)
{
    int sum=0;
    int *ret = &d[idx];
    if(*ret != -1) return *ret;
 
    *ret = 0;
    for(int i=idx; s[i]; i++) {
        sum += (s[i]-'0');
        if(sum % 3 == 0) {
            *ret = max(*ret, go(s, i+1)+1);
            break;
        }
        *ret = max(*ret, go(s, i+1));
    }
    return *ret;
}
 
int main()
{
    char s[200005];
    scanf("%s", s);
 
    for(int i=0; s[i]; i++)
        d[i] = -1;
 
    printf("%d\n", go(s, 0));
    return 0; 
}
 
 
cs


>> DP


E1.



E2.



F.



'PS > Code Force' 카테고리의 다른 글

Codeforces Round #515 (Div. 3)  (0) 2018.10.16
Codeforces Round #506 (Div. 3) // rated  (0) 2018.08.30
Codeforces Round #498 (Div. 3)  (0) 2018.08.12
Codeforces Round #501 (Div. 3) // Rated  (0) 2018.08.02

Codeforces Round #498 (Div. 3)

PS/Code Force2018. 8. 12. 00:30

Codeforces Round #498 (Div. 3) : http://codeforces.com/contest/1006



A.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
 
int main()
{
    int n, k;
    scanf("%d", &n);
 
    for(int i=0; i<n; i++) {
        scanf("%d", &k);
        if(k%2 == 0) k--;
        printf("%d ", k);
    }
    puts("");
    return 0;
}
 
cs




B. 


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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
struct P { int i, d; };
 
bool cmp(P a, P b)
{
    return a.d > b.d;
}
 
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
 
    vector<P> v;
    for(int i=0; i<n; i++) {
        int a;
        scanf("%d", &a);
        v.push_back((P){i, a});
    }
    
    sort(v.begin(), v.end(), cmp);
    
    int sum=0;
    vector<int> ans;
    for(int i=0; i<k; i++) {
        sum += v[i].d;
        ans.push_back(v[i].i);
    }
    
    sort(ans.begin(), ans.end());
    ans[ans.size()-1] = n-1;
 
    printf("%d\n", sum);
    
    printf("%d ", ans[0]+1);
    for(int i=1; i<ans.size(); i++)
        printf("%d ", ans[i]-ans[i-1]);
    puts("");
    return 0; 
}
 
 
cs




C.


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
#include <cstdio>
 
typedef long long int lli;
 
int a[200005];
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for(int i=0; i<n; i++) 
        scanf("%d", a+i);
 
    int s=0, e=n-1;
    lli sSum=a[s], eSum=a[e];
    int sIdx=-1, eIdx=-1;
 
    while(s < e) {
        if(sSum == eSum) {
            sIdx = s; eIdx = e;
        }
        if(sSum <= eSum) {
            sSum += a[++s];
        }
        else
            eSum += a[--e];
    }
 
    lli ans=0LL;
    if(sIdx != -1) {
        for(int i=0; i<=sIdx; i++)
            ans += a[i];
    }
    printf("%lld\n", ans);
    return 0;
}
 
 
cs


>> Two Pointers



D.




E. 


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
#include <cstdio>
#include <vector>
using namespace std;
 
int cnt[200005];
vector<int> g[200005];
 
vector<int> order;
int oIdx[200005];
 
int dfs(int s)
{
    int ret=1;
    oIdx[s] = order.size();
    order.push_back(s);
 
    for(int i=0; i<g[s].size(); i++) {
        int next = g[s][i];
        cnt[next] = dfs(next);
        ret += cnt[next];
    }
    return ret;
}
 
int main()
{
    int n, q;
    scanf("%d%d", &n, &q);
 
    for(int i=2; i<=n; i++) {
        int p;
        scanf("%d", &p);
        g[p].push_back(i);
    }
 
    cnt[1] = dfs(1);
 
    while(q--) {
        int u, k;
        scanf("%d%d", &u, &k);
        if(cnt[u] < k) puts("-1");
        else printf("%d\n", order[oIdx[u]+k-1]);
    }
    return 0;
}
 
 
cs


>> DFS order



F.


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
50
51
52
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
 
typedef long long int lli;
 
int n, m, half;
lli k, ans;
lli g[21][21];
 
map<lli, int> d[21][21];
 
void goHalf(int r, int c, lli xr, int cnt)
{
    xr = xr^g[r][c];
    if(cnt == half) {
        d[r][c][xr]++;
        return ;
    }
    
    if(r+1 < n) goHalf(r+1, c, xr, cnt+1);
    if(c+1 < m) goHalf(r, c+1, xr, cnt+1); 
}
 
void goEnd(int r, int c, lli xr, int cnt)
{
    if(cnt == (n+m-2-half)) {
        ans += d[r][c][xr^k]; // a^b^b = k^b = a
        return ;
    }
 
    if(r-1 >= 0) goEnd(r-1, c, xr^g[r][c], cnt+1);
    if(c-1 >= 0) goEnd(r, c-1, xr^g[r][c], cnt+1);
}
 
int main()
{
    scanf("%d%d%lld", &n, &m, &k);
 
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            scanf("%lld", &g[i][j]);
 
    half = (n+m-2)/2;
    goHalf(0, 0, 0, 0);
    goEnd(n-1, m-1, 0, 0);
   
    printf("%lld\n", ans);
    return 0;
}
 
cs


>> Meet in the Middle

'PS > Code Force' 카테고리의 다른 글

Codeforces Round #515 (Div. 3)  (0) 2018.10.16
Codeforces Round #506 (Div. 3) // rated  (0) 2018.08.30
Codeforces Round #496 (Div. 3)  (0) 2018.08.12
Codeforces Round #501 (Div. 3) // Rated  (0) 2018.08.02

Codeforces Round #501 (Div. 3) // Rated

PS/Code Force2018. 8. 2. 18:28

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


### Rated : 1275 >> 1380  ###


< Solved > : 4 out of 7 ( A, B, C, E1)


A. Points in Segments


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 <cstdio>
 
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
 
    int seg[101]={0};
 
    while(n--) {
        int l, r;
        scanf("%d%d", &l, &r);
        
        for(int i=l; i<=r; i++)
            seg[i] = 1;
    }
 
    int ans=0;
    for(int i=1; i<=m; i++)
        if(!seg[i])
            ans++;
    printf("%d\n", ans);
 
    for(int i=1; i<=m; i++)
        if(!seg[i])
            printf("%d ", i);
    puts("");
    return 0;
}
cs



B. Obtaining the String


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
50
51
52
53
54
55
#include <cstdio>
#include <vector>
using namespace std;
 
int main()
{
    int n;
    scanf("%d", &n);
 
    char s[55];
    char t[55];
    scanf("%s%s", s, t);
 
    int check[30]={0};
    for(int i=0; s[i]; i++) {
        check[s[i]-'a']++;
        check[t[i]-'a']--;
    }
 
    for(int i=0; i<26; i++) {
        if(check[i]) {
            puts("-1");
            return 0;
        }
    }
 
    vector<int> ans; 
    
    for(int i=0; i<n; i++) {
        while(s[i] != t[i]) {
            for(int k=i; k<n; k++) {
                if(s[k] == t[i]) {
                    char tmp = s[k-1];
                    s[k-1] = s[k];
                    s[k] = tmp;
                    ans.push_back(k);
                    break;
                }
            }
        }
    }
 
    int size = ans.size();
    if(size > 10000) puts("-1");
    else {
        printf("%d\n", size);
        for(int i=0; i<size; i++)
            printf("%d ", ans[i]);
        puts("");
    }
        
    return 0;
}
 
 
cs



C. Songs Compression


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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
struct P { int b, s; };
typedef long long int lli;
 
 
bool cmp(P a, P b)
{
    return (a.b-a.s) > (b.b-b.s);
}
 
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
 
    vector<P> v;
    lli sum=0LL;
    for(int i=0; i<n; i++) {
        int b, s;
        scanf("%d%d", &b, &s);
        v.push_back((P){b, s});
        sum += b;
    }
 
    sort(v.begin(), v.end(), cmp); 
    
    int ans=0;
    for(int i=0; i<n; i++) {
        if(sum > m) {
            ans++;
            sum = sum - (v[i].b-v[i].s);
        }
        else
            break;
    }
    
    if(ans == n && sum > m) ans = -1;
    printf("%d\n", ans);
    return 0;
}
 
 
cs



E!. Stars Drawing (Easy Edition)


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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <cstdio>
#include <vector>
using namespace std;
 
struct P { int r, c, n; };
 
int n, m;
char g[1005][1005];
bool check[1005][1005];
 
int di[]={1, 0, -1, 0};
int dj[]={0, 1, 0, -1};
 
bool safe(int r, int c)
{
    return (0 < r && r <= n) && (0 < c && c <= m);
}
 
int main()
{
    scanf("%d%d", &n, &m);
 
    for(int i=1; i<=n; i++)
        scanf("%s", g[i]+1);
 
    vector<P> ans;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            if(g[i][j] == '*') {
                int size = 1;
                while(1) {
                    bool ok = 1;
                    for(int k=0; k<4; k++) {
                        int ni = i+di[k]*size;
                        int nj = j+dj[k]*size;
                        if(!safe(ni, nj) || g[ni][nj] != '*') {
                            ok = 0;
                            break;
                        }
                    }
                    if(ok) {
                        for(int k=0; k<4; k++) {
                            int ni = i+di[k]*size;
                            int nj = j+dj[k]*size;
                            check[ni][nj] = 1;
                        }    
                        check[i][j] = 1;
                        size++;
                    }
                    else {
                        if(size > 1) {
                            ans.push_back((P){i, j, size-1});
                        }
                        break;
                    }
                }
            }
        }
    }
    
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            if((check[i][j] == 1 && g[i][j] == '.') || (check[i][j] == 0 && g[i][j] == '*')) {
                puts("-1");
                return 0;
            }
        }
    }
 
    int sz = ans.size();
    printf("%d\n", sz);
    for(int i=0; i<sz; i++) 
        printf("%d %d %d\n", ans[i].r, ans[i].c, ans[i].n);
 
    return 0;
}
 
cs


>> '*' 을 찾으면 이 좌표 기준 상하좌우에 '*' 가 몇바퀴 나오는지, 이런 방식으로 구현했다. 

>> 시간복잡도는 O(n^3) 정도 되는것 같다.


-------------


D 는 웬지 시간만 조금 더 있었으면 할 수 있었을 거 같았는데, 핵당한 유저들이 많았다. E1 먼저 풀길 잘한듯..


E2 에서는 E1 코드를 그대로 제출했더니, pretest 43 에서 TLE...


F 얼필 봤을때, 할만해 보였는데, 시간 없었다...ㅜㅜ




### Tutorial : http://codeforces.com/blog/entry/60949 ###


< Solution >


A.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> cnt(m + 2);
    for (int i = 0; i < n; ++i) {
        int l, r;
        cin >> l >> r;
        ++cnt[l];
        --cnt[r + 1];
    }
    for (int i = 1; i <= m; ++i)
        cnt[i] += cnt[i - 1];
    
    vector<int> ans;
    for (int i = 1; i <= m; ++i) {
        if (cnt[i] == 0)
            ans.push_back(i);
    }
cs


>> O(n+m) 풀이.

>> 쉽게 생각하면, L 번째에 1을 증가시키고, R+1 번째에 -1을 한다. 

>> 그러고 난 다음 L 부터 R+1 까지의 pSum 을 구하면 [L, R] 까지는 1이되고, R+1 번째는 0이 되서 원하는 답을 구할 수 있게 된다.



B.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<int> ans;
    for (int i = 0; i < n; ++i) {
        if (s[i] == t[i]) continue;
        int pos = -1;
        for (int j = i + 1; j < n; ++j) {
            if (s[j] == t[i]) {
                    pos = j;
                    break;
            }
        }
        if (pos == -1) {
            cout << -1 << endl;
            return 0;
        }
        for (int j = pos - 1; j >= i; --j) {
            swap(s[j], s[j + 1]);
            ans.push_back(j);
        }
    }
cs


>> O(n^2)

>> 솔루션은 그위치를 찾은다음 i번째까지 거꾸로 스왑해나가는 풀이.

>> 반면에, 내 풀이는 한번스왑하면 다시 그곳을 찾아서 반복하는 것으로 좀 비효율적인 풀이다. (구현이 어렵지 않고, 시간이 시간인지라 이런식으로 해버렸다....ㅜㅜ)



C. 


>> O(blogs) because of sort.

>> 솔루션과 풀이거 거의 비슷하다.



E1. 


>> Um...



'PS > Code Force' 카테고리의 다른 글

Codeforces Round #515 (Div. 3)  (0) 2018.10.16
Codeforces Round #506 (Div. 3) // rated  (0) 2018.08.30
Codeforces Round #496 (Div. 3)  (0) 2018.08.12
Codeforces Round #498 (Div. 3)  (0) 2018.08.12

[POJ/1182] 먹이 사슬

PS/etc.2018. 7. 25. 14:09

### Union Find ###


- Union-Find 는 같은 그룹을 관리하는 자료구조.


[1182] 먹이사슬 : http://poj.org/problem?id=1182


- 이 문제의 경우, 같은 종류인지만 판단하는 것이 아니라 "먹는다" 라는 관계가 포함되어 있다.


- 각 동물 i에 대해 3개의 요소 i-A, i-B, i-C 를 만들어 3*n 개의 요소로 Union-Find 를 만든다.

- i-X 는 i가 종류 x인 경우를 표현한다.


- t == 1 : X Y가 같은 종류로, [X-A, Y-A] [X-B, Y-B] [X-C, Y-C] 의 3개의 페어를 유니온한다.

>> 모순이 발생하는지 확인하려면, [X-A, Y-B] 가 유니온 되어 있는지 확인하면 된다.


- t == 2 : X 가 Y를 먹는다. [X-A, Y-B] [X-B, Y-C] [X-C, Y-A] 의 3개의 페어를 유니온한다. 

>> 모순이 발생하는지 확인하려면, [X-A, Y-A] 가 유니온 되어 있는지 확인하면 된다.

referenced by 노란책.

<소스코드>

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <stdio.h>
 
int n, k;
int p[500001*3];
 
int safe(int x)
{
    return (0 <= x && x < n);
}
 
int find(int x)
{
    return p[x] = p[x] == x ? x : find(p[x]);
}
 
int same(int x, int y)
{
    x = find(x);
    y = find(y);
    return x == y;
}
 
void Union(int x, int y)
{
    x = find(x);
    y = find(y);
    p[x] = y;
}
 
int main()
{
    int ans=0;
    scanf("%d%d", &n, &k);
 
    for(int i=1; i<=n*3+1; i++) 
        p[i] = i;
 
    while(k--) {
        int t, x, y;
        scanf("%d%d%d", &t, &x, &y);
        x--; y--; // [0, n)
 
        if(!safe(x) || !safe(y)) ans++;  
        else {
            if(t == 1) { // x == y
                if(same(x, y+n) || same(x, y+2*n)) ans++;
                else {
                    Union(x, y);
                    Union(x+n, y+n);
                    Union(x+2*n, y+2*n);
                }
            }
            else { // x > y
                if(same(x, y) || same(x, y+2*n)) ans++;
                else {
                    Union(x, y+n);
                    Union(x+n, y+2*n);
                    Union(x+2*n, y);
                }
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}
 
cs


>> 예를들어 설명하면, N=100 인 경우를 생각해보자.

1) 1과 2가 같은 종류라면, Union(1, 2), Union(101, 102), Union(201, 202) 가 진행된다.

2) 1이 2를 잡아먹는다면, Union(1, 102], Union(101, 202), Union(201, 2) 가 진행된다.


1) t == 1 은 x 와 y가 같은 종류인지 묻는 상태.

>> same(x, y*n) 은 x가 y를 잡아먹는 관계인지 확인.

>> same(x, y*2*n) 은 y가 x를 잡아먹는 관계인지 확인하는 케이스이다. (58라인 참고)


2) t==2 인경우는 x가 y를 잡아먹는지 묻는 상태.

>> same(x, y) 는 x가 y와 같은 종류인지 확인

>> same(x, y+2*n) 은 y가 x를 잡아먹는지 확인

'PS > etc.' 카테고리의 다른 글

[POJ/2431] Expedition  (0) 2018.06.27
[카카오 코드 / 예선] 카카오프렌즈 컬러링북  (0) 2018.05.04
<3-1> 나열하기 - 경우의 수  (0) 2018.03.06

[RUNNINGMEDIAN] 변화하는 중간 값

PS/종만북2018. 7. 20. 01:58

[RUNNINGMEDIAN] 변화하는 중간 값 : https://algospot.com/judge/problem/read/RUNNINGMEDIAN


### 우선순위 큐 (힙) ###


<소스코드>


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
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
typedef long long int lli;
const lli MOD = 20090711LL; 
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int n, b;
        lli a;
        scanf("%d%lld%d", &n, &a, &b);
 
        lli ai = 1983LL;
        lli ans = ai;
        priority_queue<lli> minH, maxH;
        maxH.push(ai);
        for(int i=1; i<n; i++) {
            ai = (1LL*ai*a+b)%MOD; 
            
            if(i&1) minH.push(-ai);
            else maxH.push(ai);
           
            if(-minH.top() < maxH.top()) {
                int a = maxH.top(); maxH.pop();
                int b = -minH.top(); minH.pop();
                maxH.push(b);
                minH.push(-a);
            }
            ans = (ans + maxH.top()) % MOD;
       }
        printf("%lld\n", ans);
    }
    return 0;
}
 
cs


>> 맥스힙에는 중간값 기준으로 중간값 포함, 그보다 작은 것들을, 민힙에는 중간값보다 큰 녀석들이 들어가게 된다. 


'PS > 종만북' 카테고리의 다른 글

[DICTIONARY] 고대어 사전  (0) 2018.05.22
[BOGGLE] 보글게임  (0) 2018.04.30
[MATCHORDER] 출전 순서 정하기  (0) 2018.04.20
[NUMBERGAME] 숫자게임  (0) 2018.04.17
[POLY] 폴리오미노  (0) 2018.04.16

<5-9> 전체탐색 - 마법의 숫자 (NumberMagicEasy)

PS/Topcoder training2018. 7. 16. 12:50

### 전체탐색 ###


### SRM 484 Div2 Level 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
#include <string>
using namespace std;
 
class NumberMagicEasy {
public:
    int theNumber(string answer) {
        int card[4][8] = {{1, 2, 3, 4, 5, 6, 7, 8},
                         {1, 2, 3, 4, 9, 10, 11, 12},
                         {1, 2, 5, 6, 9, 10, 13, 14},
                         {1, 3, 5, 7, 9, 11, 13, 15}};
        
        int cnt=0;
        int check[17]={0};
        for(int i=0; i<4; i++) {
            if(answer[i] == 'Y') {
                cnt++;
                for(int k=0; k<8; k++) 
                    check[card[i][k]]++;
            }
            else {
                for(int k=0; k<8; k++) 
                    check[card[i][k]]--;
            }
        }
       
        for(int i=1; i<=16; i++) {
            if(cnt == check[i])
                return i;
        }
        return 0;
    }
};
 
cs


>> 정답이 있는 카드들에 대한 교집합 - 정닶이 없는 카드에 대해 차집합

>> 정답 카드의 갯수만큼 카운트된 숫자가 정답이 된다.

'PS > Topcoder training' 카테고리의 다른 글

<5-8> 전체탐색 - 미로 만드는 사람 (MazeMaker)  (0) 2018.07.16
<8-8> 수학 - 둥근 모양의 국가들 (CirclesCountry)  (0) 2018.07.16
<8-4> 그리디 - 배치 시스템 (BatchSystem)  (0) 2018.07.16
<8-1> 탐색범위 한정 - 다양한 색상의 상자와 공 (ColorfulBoxesAndBalls)  (0) 2018.07.14
<7-5> DP - 악수 (HandShaking)  (0) 2018.07.04

<5-8> 전체탐색 - 미로 만드는 사람 (MazeMaker)

PS/Topcoder training2018. 7. 16. 12:26

### 전체탐색 ###


### SRM 433.5 Div2 Level 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <vector>
#include <queue>
#include <string>
using namespace std;
 
int rSize, cSize;
int visited[51][51];
 
struct P { 
    int r, c; 
    P(int r, int c) : r(r), c(c) {}
};
 
bool safe(int r, int c)
{
    return (0 <= r && r < rSize) && (0 <= c && c < cSize);
}
 
class MazeMaker {
public:
    int longestPath(vector <string> maze, int startRow, int startCol, vector <int> moveRow, vector <int> moveCol) {
        rSize = maze.size();
        cSize = maze[0].size();
               
        P cur(startRow, startCol);
        visited[startRow][startCol] = 1;
        
        queue<P> q;
        q.push(cur);
 
        while(!q.empty()) {
            int curR = q.front().r;
            int curC = q.front().c; q.pop();
 
            int sz = moveRow.size();
            for(int k=0; k<sz; k++) {
                int nr = curR + moveRow[k];
                int nc = curC + moveCol[k];
                if(safe(nr, nc) && maze[nr][nc] == '.' && !visited[nr][nc]) {
                    P tmp(nr, nc);
                    q.push(tmp);
                    visited[nr][nc] = visited[curR][curC]+1;
                }
            }
        }
        int ans = 0;
        for(int r=0; r<rSize; r++) {
            for(int c=0; c<cSize; c++) {
                if(maze[r][c] == '.' && visited[r][c] == 0) return -1;
                if(maze[r][c] == '.' && ans < visited[r][c]) {
                    ans = visited[r][c];
                }
            }
        }
        return ans-1;
    }
};
 
cs


>> 방문할 수 있는 모든 곳을 탐색. 방문을 못한 곳이 있으면 -1; 모두 방문했다면, 방문한 곳중 가장 먼 곳이 정답.

'PS > Topcoder training' 카테고리의 다른 글

<5-9> 전체탐색 - 마법의 숫자 (NumberMagicEasy)  (0) 2018.07.16
<8-8> 수학 - 둥근 모양의 국가들 (CirclesCountry)  (0) 2018.07.16
<8-4> 그리디 - 배치 시스템 (BatchSystem)  (0) 2018.07.16
<8-1> 탐색범위 한정 - 다양한 색상의 상자와 공 (ColorfulBoxesAndBalls)  (0) 2018.07.14
<7-5> DP - 악수 (HandShaking)  (0) 2018.07.04

<8-8> 수학 - 둥근 모양의 국가들 (CirclesCountry)

PS/Topcoder training2018. 7. 16. 11:15

### 수학 ###


### SRM 443 Div2 Level 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
#include <vector>
using namespace std;
 
double dist(int x1, int y1, int x2, int y2)
{
    return (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1);
}
 
class CirclesCountry {
public:
    int leastBorders(vector <int> X, vector <int> Y, vector <int> R, int x1, int y1, int x2, int y2) {
        
        int ans=0;
        for(int i=0; i<X.size(); i++) {
            double d1 = dist(X[i], Y[i], x1, y1);
            double d2 = dist(X[i], Y[i], x2, y2);
            double r = (double)R[i]*R[i];
            if(d1 < r) ans++;
            if(d2 < r) ans++;
            if(d1 < r && d2 < r) ans -= 2;
        }
        return ans;
    }
};
cs


>>> 기본 아이디어는 시작 좌표와 목표 좌표가 둥근성에 포함되어 있으면 카운트.

>>> 예외처리 : 같은 성에 동시에 포함되어 있으면 카운트하면 안된다.

'PS > Topcoder training' 카테고리의 다른 글

<5-9> 전체탐색 - 마법의 숫자 (NumberMagicEasy)  (0) 2018.07.16
<5-8> 전체탐색 - 미로 만드는 사람 (MazeMaker)  (0) 2018.07.16
<8-4> 그리디 - 배치 시스템 (BatchSystem)  (0) 2018.07.16
<8-1> 탐색범위 한정 - 다양한 색상의 상자와 공 (ColorfulBoxesAndBalls)  (0) 2018.07.14
<7-5> DP - 악수 (HandShaking)  (0) 2018.07.04

티스토리툴바