AtCoder Beginner Contest 145
はい。
https://atcoder.jp/contests/abc145
ooox-- 884(+4) 微増。C問題まではそこそこスムーズでした。D問題も気づくべきだったなー、という感じです。
A - Circle
PyPy3
n=int(input()) print(n**2)
rの2乗ですね。
B - AtCoderでじゃんけんを
PyPy3
n=int(input()) s=input() print("Yes" if len(s)%2==0 and s[:len(s)//2]==s[len(s)//2:] else "No")
偶数長の文字列を半分に分けて比較を。
C - Attack Survival
PyPy3
import itertools def sol(): n=int(input()) d=list(itertools.permutations([i for i in range(n)])) w=[] for i in range(n): x,y=map(int,input().split()) w.append((x,y)) ans=chk=0 for i in d: for j in range(len(i)-1): ans+=((w[i[j]][0]-w[i[j+1]][0])**2+(w[i[j]][1]-w[i[j+1]][1])**2)**0.5 print(ans/len(d)) if __name__=="__main__": sol()
何らかで順列を、経路を列挙して全て足して割ると平均が求まると思います。
D - Knight
C++14
#include<bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;++i) #define per(i,n) for(int i=n-1;i>=0;--i) #define sc1(a) scanf("%d",&a) #define sc2(a,b) scanf("%d %d",&a,&b) #define sc3(a,b,c) scanf("%d %d %d",&a,&b,&c) #define sl1(a) scanf("%lld",&a) #define sl2(a,b) scanf("%lld %lld",&a,&b) #define sl3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c) #define PI 3.1415926535897932 const int MAX=710000; 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 x,y,ans=0; sc2(x,y); if ((x+y)%3!=0 || x>(x+y)/3*2 || y>(x+y)/3*2){ printf("0\n"); return 0; } ans=COM((x+y)/3,min(x,y)-(x+y)/3); printf("%d\n",ans%MOD); return 0; }
x+yが3の倍数でなかったり、 max(x,y)>(x+y)/3*2
だったりすると移動出来ないマスです。(x+y)/3*2は移動回数です。座標0,0から開始して、+2,+1 か +1,+2 しどちらかだけを繰り返し続けても2倍より2倍よりは大きくならないはずだからです。
移動パターンはおそらく上みたいな感じのはずです。n回目で移動出来るマスが右上がり斜めに並びます。左端から考えるとx+1,y+2のみで移動してきて1通り。1つずれるとx+1,y+2をn-1回とx+2,y+1を1回、これがn回の移動中に1回x+2,y+1を選択なのでnC1。なので移動先の座標が決まれば組合せの数で解が求められるはずです。
E - All-you-can-eat
PyPy3
n,t=map(int,input().split()) dp=[0]*(t+3005) ans=chk=0 w=[] for i in range(n): a,b=map(int,input().split()) w.append((a,b)) w.sort() for i in w: for j in range(t-1,-1,-1): dp[j+i[0]]=max(dp[j+i[0]],dp[j]+i[1]) ans=max(ans,dp[j+i[0]]) print(ans)
aの値が最大のモノを最後にする必要があることに気づかなくて解説を読みました。これおそらくは (制限値-1) + a
みたいな問題にまた合うことがあったらその時はソートを忘れないように。
DPテーブルは1次元配列で余裕を持った大きさにしましたがt+3000でも行けるのかな?t番目の要素、t-1分に追加する最大が3000分なので。
制限時間内に注文していれば食べ終わり時間がはみ出すことはあり得るのですが、 あくまでも追加注文出来るのは制限時間-1の時までのはずなのでループをそこから回して最大値になる状態を探しました。