はい。
https://atcoder.jp/contests/abc117
A - Entrance Examination
#include<bits/stdc++.h>
using namespace std;
#define sc2(a,b) scanf("%d %d",&a,&b)
int main(){
int t,x;
sc2(t,x);
printf("%.10lf\n",1.0/x*t);
return 0;
}
t,x=map(int,input().split())
print("{0:.10}".format(t/x))
問題文読んでサンプルのとおりに計算する。
B - Polygon
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
#define sc1(a) scanf("%d",&a)
int main(){
int n,m;
sc1(n);
vector <int> l(n);
rep(i,n) sc1(l[i]);
sort(l.begin(),l.end());
int t=accumulate(l.begin(),l.end(),0);
printf("%s\n",t-l[n-1]>l[n-1]?"Yes":"No");
return 0;
}
input()
l=[int(i) for i in input().split()]
print(["No","Yes"][max(l)<sum(l)-max(l)])
一番長い辺とその他全ての辺の長さをどうにか計算して判定。
C - Streamline
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++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)
int main(){
int n,m,ans=0;
sc2(n,m);
vector <int> a(m);
vector <int> b;
rep(i,m) sc1(a[i]);
sort(a.begin(),a.end());
rep(i,m-1) b.push_back(a[i+1]-a[i]);
sort(b.begin(),b.end());
rep(i,m-n) ans+=b[i];
printf("%d\n",ans);
return 0;
}
n,m=map(int,input().split())
l=[int(i) for i in input().split()]
l.sort()
ans=[0]
for i in range(m-1):
ans.append(l[i+1]-l[i])
ans.sort()
for i in range(n-1):
if len(ans)==1: break
ans.pop()
print(sum(ans))
とりあえずソートする。それぞれ隣との区間を求める。区間もソートする。使えるコマが一つ増えるごとに大きい区間を省略できる。大きい区間を省略した後の総和が解になる。
D - XXOR
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
d=[0]*41
t=[0]*41
p=2**40
x=0
y=1
ans=0
for i,j in enumerate(bin(k)[::-1]):
if j=="b": break
if j=="1": d[i]=1
for i in a:
for j,k in enumerate(bin(i)[::-1]):
if k=="b": break
if k=="1": t[j]+=1
for i in range(40,-1,-1):
if d[i]==1 and t[i]>n//2-(n+1)%2:
y=0
elif d[i]==1 and t[i]<=n//2:
x+=p
elif y==0 and t[i]<=n//2:
x+=p
p//=2
for i in a:
ans+=x^i
print(ans)
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
#define sl1(a) scanf("%lld",&a)
#define sl2(a,b) scanf("%lld %lld",&a,&b)
long long dp[60][2],w[60];
int cnt[60],kk[60];
int main(){
long long n,k;
sl2(n,k);
w[0]=1;
for(int i=1;i<60;i++) w[i]=w[i-1]*2;
long long k1=k;
rep(j,60) {
if (k1&1) kk[j]+=1;
k1=k1>>1;
}
for (long long i=0;i<n;i++) {
long long a;
sl1(a);
rep(j,60) {
if (a&1) cnt[j]+=1;
a=a>>1;
}
}
int f=0;
for(int i=58;i>=0;i--) {
if (f==1) f++;
else if (f==0 && kk[i]==1) f=1;
if (kk[i]==1) dp[i][0]=dp[i+1][0]+(w[i]*((n-cnt[i])*1ll));
else if (kk[i]==0) dp[i][0]=dp[i+1][0]+(w[i]*(cnt[i]*1ll));
long long y=max(cnt[i]*1ll,(n-cnt[i]*1ll))*w[i];
if (f==1) dp[i][1]=(w[i]*(cnt[i]*1ll));
else if (f>1) dp[i][1]=(dp[i+1][1]+y);
if (f>1 && kk[i]==1) dp[i][1]=max(dp[i][1],dp[i+1][0]+(cnt[i]*1ll*w[i]));
}
printf("%lld\n",max(dp[0][0],dp[0][1]));
return 0;
}
Pythonは嘘解法してます。
Kを2進数にして1が立っている桁を調べておく。Aの数を全部1が立っている桁を調べて個数をカウントする。桁が大きい方から見る。
XをK以下にするためにはKより先に1は立てられない。Kだけで1が立つ桁が発生したら後は自由。Kの以降の桁が全て0、Xの以降の桁が全て1でもXは必ずKより小さくなる。
Xで1を立てたいのはAで数えた中で1が立ってる個数がn/2より少ないもの。個数がn/2ぴったりのときは立てても立てなくてもXORで出てくる数は変わらないのですけど、XをK以下にする条件に不利になるので立てない方針でいいと思います。
C++は真面目に桁DPしてます。
DPテーブルをどう用意するかに悩んで時間がかかり解説記事などをググって解決しました。
上記ではdp[i][0]はKと同じビットの立て方でXORがいくつになるかを見ています。dp[i][1]はKより小さい数でいくつになるかを見ています。Kより小さい数であるということは、一つ手前の桁までは同じでも大丈夫ですが、dp[i][0]では立っているがdp[i][1]では立っていないという一度発生すれば必ず小さいです。一度小さくなったら解の桁ではどんなビットの立て方をしてもK以上になることはありません。なんとかDP配列をよしなに更新すると解が求まるはずです。