AtCoder Beginner Contest 066 by C

AtCoder Beginner Contest 066 について
C言語での回答

atcoder.jp

できたもの
A
B
C

できなかったもの
D

問題A

#include <stdio.h>

int max(int a, int b){
    return a > b ? a : b;
}

int main(void){
    int a,b,c;
    scanf("%d %d %d", &a,&b,&c);
    int max_num = max(a,max(b,c));

    printf("%d",a+b+c-max_num);

    return 0;
}

3つから2つ選んで足した時に合計額が一番小さい金額を答える問題。
1番大きい（高い）金額をmax関数を実装してやって求め、3つの合計から引くことで求まります。
逐一比較したり条件分岐するよりスマートだよね←

問題B

#include <stdio.h>
#include <string.h>

int main(void){
    char s[201];
    int i,j;
    scanf("%s", s);
    int size = strlen(s);

    int max;
    int k;
    for(i=size-1;i>0;i--){
        int count = 0;
        if(i%2==1){
            continue;
        }

        for(j=0;j<i/2;j++){
            if(s[j]==s[j+(i/2)]){
                count++;
            }
        }
        if(count==(i/2)){
            max = i;
            break;
        }
    }

    printf("%d", max);
    
    return 0;
}

iをsize-1から1ずつ減らすことは末尾の文字を消すことに相当します。
偶文字列となるのは当該の文字列の長さが偶数の時だけなので、偶数の時を考えます。
偶文字列であれば、文字列の前半分と後ろ半分が一致するはずなので、そこを比較します。
文字列の長さをi+1としたときに、前半分は0~(i/2)-1、後ろ半分はi/2~iなので、うまくループするように添え字を調整。
一致した時はcountを増やし、countの数と文字列の半分が一致した時が答え。

問題C

#include <stdio.h>

int main(void){
    int n,a,i,j;
    int b[200001],b_tmp[200001];
    scanf("%d", &n);

    int k1 = 0, k2 = 0;
    for(i=0;i<n;i++){
        scanf("%d", &a);
        if(n%2==0){
            if(i%2==0){
                b[(n/2)+k1] = a;
                k1++;
            }
            else{
                b[(n/2)-(k2+1)] = a;
                k2++;
            }
        }
        else{
            if(i%2==0){
                b[(n/2)-k1] = a;
                k1++;
            }
            else{
                b[(n/2)+(k2+1)] = a;
                k2++;
            }
        }
    }

    for(i=0;i<n-1;i++){
        printf("%d ", b[i]);
    }
    printf("%d", b[n-1]);

    return 0;
}

最初は配列に入れて、別の配列に移しなおしてまた逆に入れるという風にしてたんですが、まあTLE。
というわけで入力時に入る座標めがけて入れてしまえばO(n)なのででそうしました。
最後にいれた数字はb[0]、その一つ前はb[n-1]、更にその一つ前はb[1]…といった様に入るので、うまいこと添え字を変えて実装。
今回は入力時から決まった位置に入れてやりましたが、入力時は順番に受け取り、出力時に工夫するパターンもあるようです。

問題D

#include <stdio.h>

#define MOD 1000000007

long long fac[100010],finv[100010],inv[100010];

void COMint(){
    int i;
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(i=2;i<100010;i++){
        fac[i] = fac[i-1]*i%MOD;
        inv[i] = MOD-inv[MOD%i]*(MOD/i)%MOD;
        finv[i] = finv[i-1]*inv[i]%MOD;
    }
}

long long COM(long long n, long long k){
    if(n<k){
        return 0;
    }
    if(n<0||k<0){
        return 0;
    }
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}

int main(void){
    COMint();
    int n,i,l,x;
    int a[100010]={0};
    scanf("%d", &n);

    for(i=1;i<=n+1;i++){
        scanf("%d", &x);
        if(a[x]==0){
        	a[x]=i;
        }
        else{
        	l=i-a[x]-1;
        }
    }
  
    for(i=1;i<=n+1;i++){
        long long ans = (COM(n-1,i)+2*COM(n-1,i-1)-COM(n-l-1,i-1)+COM(n-1,i-2)+MOD)%MOD;
        printf("%lld\n", ans);
    }
    
    return 0;
}

なぜか答えが一致せず、かなり悩みましたが、原因はaの初期化忘れでした。
初期化大事。
解説からnCrを使うとのことだったので、例の関数を引っ張ってきました。
詳しくは042-D参照。
atcodeeeeer.hatenablog.com

後半の一致するものを調べる方法はまだちょっと理解してません。
ちなみに最初2重ループで重複を調べようとしたらn=10^5のO(n^2)なので当然TLEでした。

本日の教訓：初期化は大事（大事な事なので2回(ry）

解けなかった原因

重複する場合の除外方法が思い付かなかった（nCrともろもろの工夫）