音ゲーの問題があると聞いて、A～Eを解いてみました。
A – ハンバーガー(Hamburger)
A – ハンバーガー(Hamburger) (atcoder.jp)
足りない数は、肉ならN*1-a、パンならN*2-b、トッピングならN*3-cです。
ただ、計算結果が0未満である場合、十分足りているということなので0を出力する必要があります。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int a,b,c,N;
cin>>a>>b>>c;
cin>>N;
cout<<max(0,N*1-a)<<" "<<max(0,N*2-b)<<" "<<max(0,N*3-c)<<endl;
}
B – ビットマニア(BITMANIA)
B – ビットマニア(BITMANIA) (atcoder.jp)
お目当ての問題。弐寺のパクリ音ゲーの問題。
譜面から各レーンの1重トリルの最大の長さを算出し、各指を適切に配置した時にフルコンが取れるかを求める問題。
各指の配置は1重トリルに耐えられるものから順に、1重トリルの最大の長さが大きいレーンに割り当てていくのが最適です。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N;
int a[10];
cin>>N;
for(int i=0;i<10;i++){
cin>>a[i];
}
string s[N];
for(int i=0;i<N;i++){
cin>>s[i];
}
int tor[7]={0};
for(int i=0;i<7;i++){
int c=0;
for(int j=0;j<N;j++){
if(s[j][i]=='X') c++;
else c=0;
tor[i]=max(tor[i],c);
}
}
sort(tor,tor+7);
sort(a,a+10);
int i=6,j=9;
while(1){
//cout<<i<<","<<j<<","<<a[j]<<","<<tor[i]<<endl;
if(a[j]>=tor[i]){
i--,j--;
}
else j--;
if(i==-1){
cout<<"YES"<<endl;
return 0;
}
if(j==-1){
cout<<"NO"<<endl;
return 0;
}
}
}
C – 紅茶(Tea)
整数の組の詳細がないというふざけた問題です。
スタートは(1,1)です。(m,1)があるとき、(m,1),(m-1,2),(m-2,3)….,(1,m)とm=1になるまで並べ、次は(m+1,1)と並べます。
このとき、m=1,m=2,m=3の場所はレイジー・ケーター数(以下、RK)と一致します。（オンライン整数列大辞典のリスト – WikipediaのA00124より)
よって、k番目の(m,n)が知りたい場合、
RKのi番目とi+1番目の間にkがくるようなiを求める。 l=k-RKのi番目とすれば、求めたい列は (i-l,1+l)となる。
(m,n)が何番目か知りたい場合、
(m,n)を(m+n-1,1)と考え、m+n-1番目のRKを求める。 m+n-1番目のRKにn-1を足したものが答え。
となります。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
void findmn(int ij,int *m,int *n){
int c=1;
for(int i=1;;i++){
if(c<=ij&&ij<c+i){
//out<<c<<","<<i<<","<<ij<<endl;
*m=i-(ij-c+1)+1;
*n=ij-c+1;
break;
}
c+=i;
}
}
int main(){
int i,j;
cin>>i>>j;
int ni,mi,nj,mj;
findmn(i,&mi,&ni);
findmn(j,&mj,&nj);
//cout<<mi<<","<<ni<<"---"<<mj<<","<<nj<<endl;
int an=ni+nj,am=mi+mj;
int ans=an-1;
am+=an-1;
an=1;
int c=1;
for(int i=1;i<am;i++) c+=i;
ans+=c;
cout<<ans<<endl;
}
D – 虫歯(Cavity)
このコンテストの最難問かと思います。
K<=50なので、二分木の葉の数が最大2^50≒10^15となります。
何となく、工夫しないと計算量が大変になりそうな予感がします。
治療した場合どうなるか考える
ある歯を治療した場合、どの範囲に影響があるでしょうか？
まず範囲の左端から考えます。
左側にある、同じ深さの頂点はq-1個ある。 この頂点が2倍ずつ増えていくので、q-1、2(q-1)個、4(q-1)個...(2^(K-p-1))(q-1)個になる。 左端は、この個数+1個の場所にあるので、q-1+1、2(q-1)+1、4(q-1)+1...(2^(K-p-1))(q-1)+1になる。
続いて右端も同じように
右側にある、同じ深さの頂点は(2^p)-q個ある。 この頂点が2倍ずつ増えていくので、(2^p)-q、2((2^p)-q)個、4((2^p)-q)個...(2^(K-p-1))((2^p)-q)個になる。 右端は、この個数でその深さにある頂点の個数を引けばいいので、1-((2^p)-q)、2-(2((2^p)-q))、4-(4((2^p)-q))...2^K((2^(K-p-1))((2^p)-q))となる。
これで、治療した歯がある深さに与える範囲が分かるようになりました。
※深さkに対して、k<pの場合その深さには影響を与えないものとする(その深さkの下に対する影響のため)
範囲を求める
“治療した歯がある深さに与える範囲”が分かったので、k=0～Kの各深さに関して、治療した歯が与える影響外の歯の数をカウントすれば良さそう…ですが、冒頭で述べたように深さ=50のときの歯の数が大きすぎて、範囲を単純にカウントするとTLEします。
こういうときは、mapなどに影響を与える区切りだけを入れておいて、区切りごとに見ていくことで高速化します。具体的には、
左端=l,右端=rの場合、 map[l]++ map[r+1]-- をする。こうすることで区切りを左端から見ていってimosっぽいことをする(変数xにmapの中身を足していって、xが0である区間が答え。この区間の長さは、区間同士の距離でO分かる)ことで、O(N)で影響外の歯の数が分かる。
こういうの多分、イベントソートというらしいです。
上記考えを纏めることで1353msでACしました。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
long long K;
long long N;
cin>>K>>N;
long long p[N],q[N];
for(int i=0;i<N;i++){
cin>>p[i]>>q[i];
}
long long ans=0;
for(long long k=0;k<=K;k++){
map<long long,long long> m;
for(int i=0;i<N;i++){
if(p[i]>k) continue;
long long pl=(1ll<<(k-p[i]))*(q[i]-1)+1;
long long mi=(1ll<<k)-(1ll<<(k-p[i]))*((1ll<<(p[i]))-q[i]);
//cout<<i<<","<<k<<"---"<<pl<<","<<mi<<endl;
m[pl]+=1;
m[mi+1]-=1;
}
if(m.empty()){
ans+=(1ll<<k);
//cout<<k<<"!!!"<<ans<<endl;
continue;
}
auto it=m.begin();
long long C=it->second;
ans+=it->first-1;
long long bef=it->first;
it++;
while(it!=m.end()){
long long pq=it->first;
long long c=it->second;
//cout<<pq<<","<<c<<endl;
if(C==0){
ans+=pq-bef;
}
C+=c;
it++;
bef=pq;
}
if(bef<=(1ll<<k)){
ans+=(1ll<<k)-bef+1;
}
//cout<<k<<"!!!"<<ans<<endl;
}
cout<<ans<<endl;
}
注意点は”1ll<<“の”ll”が抜けるとオーバーフローでWAします。
(llを付けないと、intと認識されちゃう)
E – お気に入りの数2(Favorite Number2)
E – お気に入りの数2(Favorite Number2) (atcoder.jp)
正直Dより簡単です。
全ての遷移を行いたいので、
- nまでx+1する
- x以上の中で、まだ遷移していないsqrt(x)があるなら、そこまでx+1してsqrtする
※このとき、そんなsqrtがなければ-1 - x=2に戻ってくれば終了
とするのが良いです。
これを実装します。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
long long n;
cin>>n;
long long ans=n-2;
if(n==2){
cout<<"0"<<endl;
return 0;
}
set<long long> s;
for(long long a=2;a<=sqrt(n);a++){
s.insert(-a*a);
}
while(1){
long long a=-*(s.begin());
if(a<n){
cout<<"-1"<<endl;
return 0;
}
//cout<<n<<","<<a<<","<<ans<<endl;
ans+=a-n+1;
n=sqrt(a);
if(n==2) break;
s.erase(s.begin());
}
cout<<ans<<endl;
}
コメント