AtCoder Beginner Contest 034
はい。
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
から写しました。