12/8に開催されてこともあり、クリスマス回になっています。Dが緑問みたいですが、水くらいありそう…。(多分、本番出てたら解けてないです。というか実際、1日寝かせました。)
A – Christmas Eve Eve Eve
A - Christmas Eve Eve Eve
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
ifで分けるだけでもいいのですが、24,23…と数字が減るたびに” Eve”が末尾に増えると考え、for文で解きました。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
int D;
cin>>D;
cout<<"Christmas";
for(int i=D;i<25;i++){
cout<<" Eve";
}
cout<<endl;
}
ちなみに、A問題は基本forを使わずに解けるようになっているらしいです。そのため、forをA問題で使う場合、想定外の解法の可能性があります。
B – Christmas Eve Eve
B - Christmas Eve Eve
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
問題の通り実装します。
今回、入力から和を計算する際に最大も計算し、最後に入力の和から最大/2を引いて答えとしました。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
int N;
cin>>N;
int mx=0;
int sm=0;
for(int i=0;i<N;i++){
int A;
cin>>A;
sm+=A;
mx=max(mx,A);
}
cout<<sm-mx/2<<endl;
}
C – Christmas Eve
C - Christmas Eve
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
最大と最小を除いた、k-2本以外の木の高さhiがhmax<=hi<=hminにないような選び方が最適解の候補になります。(中に選んでいない木があるなら、最高と最低を寄せれるため)
こういった選び方はN-K+1通りしかないため、全通りの中で最小を取ればOKです。
具体的には、hiをソートし、K-2飛ばしの2点間の差の最小を取ればOKです。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
int N,K;
cin>>N>>K;
int h[N];
for(int i=0;i<N;i++){
cin>>h[i];
}
sort(h,h+N);
int mn=INT_MAX;
for(int i=0;i<N;i++){
if(i+K-1>=N) break;
int diff=h[i+K-1]-h[i];
mn=min(mn,diff);
}
cout<<mn<<endl;
}
D – Christmas
D - Christmas
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
強敵でした…。
レベルNのバーガをF(N)としたとき、F(N+1)のバーガはB+F(N)+P+F(N)+Bと表せれます。
この時、パティの個数をP(N)、バーガーの枚数をG(N)としたとき、P(N+1)のパティの個数はP(N)*2+1、G(N+1)のバーガーの個数はG(N)*2+3と表せられます。
実は上の式から、Xの値で条件分けすることでパティの個数を求めることができます。レベルNのバーガーの下からX枚のパティの数をPx(N,X)とした場合、
Px(N,1) = 0 -> 一番下はBのため Px(N,2～G(N)) = Px(N-1,X-1) -> レベル-1のバーガの途中までなため、レベル-1バーガを見ないと分からない。 Px(N,G(N)+1) = P(N-1) -> レベル-1のバーガのパティすべてが含まれる。 Px(N,G(N)+2) = P(N-1)+1 -> 上に加えてPが一つ増える。 Px(N,G(N)+3～2*G(N)+1) = P(N-1)+1+Px(N-1,X-G(N)-2) -> 上に加えて、レベル-1バーガの途中を調べる Px(N,2*G(N)+2) = 2*P(N-1)+1 -> 2つのレベル-1バーガのパティと、1つのPが含まれる Px(N,2*G(N)+3) = 2*P(N-1)+1 -> 最後はBなので関係ない
の7パターンに分かれます。
これら条件分けを丁寧にコーディングすればACとなります。
#include<bits/stdc++.h>
using namespace std;
int main(){
long long N,X;
cin>>N>>X;
long long PB[N+1];
long long P[N+1];
PB[0]=1;
P[0]=1;
for(int i=1;i<=N;i++){
PB[i]=PB[i-1]*2+3;
P[i]=P[i-1]*2+1;
}
long long ans=0;
for(int i=N;i>=0;i--){
//BXPXB
if(3+PB[i-1]+PB[i-1]<=X){
ans+=P[i-1]+P[i-1]+1;
break;
}
else if(2+PB[i-1]+PB[i-1]<=X){
ans+=P[i-1]+P[i-1]+1;
break;
}
else if(2+PB[i-1]<X){
ans+=P[i-1]+1;
X-=2+PB[i-1];
}
else if(1+PB[i-1]<X){
ans+=P[i-1]+1;
break;
}
else if(1+PB[i-1]<=X){
ans+=P[i-1];
break;
}
else if(1<X){
X-=1;
}
else break;
}
cout<<ans<<endl;
}
なにか法則性があるのかと思っていましたが、思っていたより力技な問題でした。
コメント