Codeforces Round #496 (Div. 3)

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

A.

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

>> 1의 갯수 세기.

B.

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

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

C.

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

>> lower_bound를 이용한 이진탐색

D.

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

>> DP

E1.

E2.

F.