AtCoder Beginner Contest 132
はい。
https://atcoder.jp/contests/abc132
oooox- 1020(+40)でした。たまたま相性?が良かったです。
A - Fifty-Fifty
PyPy3
s=list(input()) s.sort() print(["No","Yes"][s[0]==s[1] and s[2]==s[3] and s[1]!=s[2]])
ソートして比較しました。がYesになるパターン数が3通りしかないようでそのまま比較でもいいようです。入力の文字の出現回数を数えるとかは面倒だと思います。
B - Ordinary Number
PyPy3
n=int(input()) p=[int(i) for i in input().split()] ans=0 for i in range(2,n): chk=[p[i-2],p[i-1],p[i]] chk.sort() if chk[1]==p[i-1]: ans+=1 print(ans)
PythonならA<B<CとかA>B>Cとかで書けましたね。
C - Divide the Problems
PyPy3
n=int(input()) d=[int(i) for i in input().split()] d.sort() print(d[n//2]-d[n//2-1])
ソートして中央で分けて分ける境界が同じ値でなければいい気がしたけどもC問題だし何か見落とししてるのではないかとやや不安で提出した。罠は特にありませんでした。
D - Blue and Red Balls
C++14
#include<bits/stdc++.h> using namespace std; const long long MAX=510000; const long long 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 (long long 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(); long long n,k,ans=0ll; scanf("%lld %lld",&n,&k); for (long long i=1;i<=k;i++) { if (i>1) { ans=(COM(n+1-k,i)*COM(k-1,i-1))%MOD; } else { ans=COM(n+1-k,i); } printf("%lld\n",ans%MOD); } return 0; }
サンプル1を見て赤の端か内側のドコかに青が入ることをイメージします。N-K個の赤いボールの端と内側のドコかはN-K+1箇所です。N-K+1箇所の内でi箇所を選んで青いボールを入れます。i箇所に入れるボールを用意するためにはK個あるボールの内側K-1箇所のなかからi-1箇所を選びます。
i箇所に入れるボールの組合せを数えることに気づいてなかったりでWAしました。もったいない。。。
E - Hopscotch Addict
PyPy3
from collections import deque import sys input = sys.stdin.readline def sol(): n,m=map(int,input().split()) d={} for i in range(m): u,v=map(int,input().split()) if u in d: d[u].append(v) else: d[u]=[v] s,t=map(int,input().split()) ans=0 w=deque([0,s]) tmp=[[0,0,0] for i in range(n+1)] ans=1 n*=3 while n: x=w.pop() if x==0: ans+=1 n-=1 w.appendleft(0) elif x in d: for j in d[x]: if ans%3==0 and j==t: print(ans//3) exit() if tmp[j][ans%3]==0: w.appendleft(j) tmp[j][ans%3]=1 print(-1) if __name__=="__main__": sol()
先頭でsys.stdinするのは入力データが大きい時には結構な違いが出るようです。けんけんぱの移動を幅優先でシミュしました。但し、3の倍数で見て同じ周期のトコへの移動は捨てています。「けんけん」で移動出来た頂点に「けんけんぱけんけん」で移動する意味はないので。