How We Coding

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

티스토리툴바