Kyuride Kagamiz Programming Contest (Easy)

音ゲーの問題があると聞いて、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)

C – 紅茶(Tea) (atcoder.jp)

整数の組の詳細がないというふざけた問題です。
スタートは(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)

D – 虫歯(Cavity) (atcoder.jp)

このコンテストの最難問かと思います。
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;
}

コメント

タイトルとURLをコピーしました