AtCoder Beginner Contest 034

atcoder

はい。
https://beta.atcoder.jp/contests/abc034

A - テスト

Python2

x,y=map(int,raw_input().split())
print 'Better' if x<y else 'Worse'

x,y比較で。

B - ペア

Python2

n=int(raw_input())
print n-1 if n%2==0 else n+1

偶数なら1小さい人と、奇数なら1大きい人と。

C - 経路

C++14

#include<bits/stdc++.h>
using namespace std;
//部分点解法 
int main(){
    int w,h;
    int mod=1000000007;
    scanf("%d %d",&w,&h);
    int b[2][w];
    b[1][0]=1;
    for (int i=0;i<w;i++)  b[0][i]=1;
    for (int i=1;i<h;i++) for (int j=1;j<w;j++) {
        b[1][j]=(b[0][j]+b[1][j-1])%mod;
        b[0][j]=b[1][j];
    }

    printf("%d\n",b[1][w-1]);
    return 0;
}

C++14

#include<bits/stdc++.h>
using namespace std;
//満点解法 
const int MAX=510000;
const int MOD=1000000007;
 
long long fac[MAX], finv[MAX], inv[MAX];
 
void COMinit() {
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    for (int i=2;i<MAX;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(int n,int 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(){
    COMinit();
    int w,h,ans=0;
    scanf("%d %d",&w,&h);
    ans=COM(h+w-2,h-1);
    printf("%d\n",ans);
    return 0;
}

部分点解法はhwの配列で、と思ってたんですけど大きいケースでは配列が無理すぎてセグフォしてるっぽかったし、そもそもhwじゃなくて2wで十分だったのでそれで部分点。配列サイズは小さくしてもループ自体はhwくらい回すのでTLEは解決できず。

満点解法は配列でひたすら更新して作り出す配列[h][w]の値が数学的に求まるというのでそれで。nCkの(h+w-2)C(h-1)で求められるとのこと。nCkは逆元とかフェルマーの小定理とかは全くわからず無理だったので、
http://drken1215.hatenablog.com/entry/2018/06/08/210000
から写しました。