Motsu_xe 競プロのhogeやfuga

Motsu_xeが競技プログラミングに関する何かを適当に書き連ねるブログになるはずです。

ABC154 解説

結果は26:24 12位でした。サクサク解けていい感じなんだけど、これ遅刻しなけりゃ9位だった…これもミリシタって奴が悪いんだ、イベント終了が21時だったんや…。

コンテストページ

A - Remaining Balls

思考

文字列はstring型でそのまんま比較できるのでやるだけです。

実装例

#include<bits/stdc++.h>
using namespace std;

int main(){
    string s,t,u;
    int a,b;
    cin>>s>>t>>a>>b>>u;
    if(s==u) --a;
    if(t==u) --b;
    cout<<a<<" "<<b<<endl;
}

コンテスト中のACコード

B - I miss you...

思考

全ての文字を同じ文字で書き換えるのだから、文字数以外の情報は不要ですね。Sの文字数だけxを出力すれば良いです。ところでタイトルはどういう意味なんでしょう、xに書き換えたりちょっと闇を感じますね。

実装例

#include<bits/stdc++.h>
using namespace std;

int main(){
    string s;
    cin>>s;
    for(size_t i{};i<s.length();++i) cout<<'x';
    cout<<endl;
}

コンテスト中のACコード

C - Distinct or Not

思考

重複があるかどうかはsetにぶち込んで、sizeを見ればいいことはよく知られています。

実装例

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n,a;
    cin>>n;
    set<int> st;
    for(int i{};i<n;++i){
        cin>>a;
        st.insert(a);
    }
    puts(st.size()==n?"YES":"NO");
}

コンテスト中のACコード

こちらはなんとなく書いた一行コードです(いらない)。

print('YNEOS'[int(input())!=len(set(input().split()))::2])

D - Dice in Line

思考

期待値の線型性から、それぞれのダイスの期待値の和を足せばいいです。それぞれのダイスの期待値は\frac{p[i]+1}{2}であるから、単純に連続するK個のダイスでp[i]の総和が一番でかいものを考えればいいです。これは尺取りみたいな感じでやる、いつもの奴です。

実装例

#include<bits/stdc++.h>
using namespace std;

int main(){
    int k,n;
    cin>>n>>k;
    vector<int> p(n);
    for(auto&i:p) in>>i;
    int s{},ans;
    for(int i{};i<k;++i) s+=p[i]+1;
    ans=s;
    fr(i,n-k) s-=p[i],s+=p[i+k],ans=max(ans,s);
    cout<<setprecision(20)<<ans/2.0<<endl;
}

コンテスト中のACコード

E - Almost Everywhere Zero

思考

ほとんどいたるところゼロ、この場合有限列だから、ゼロが一個もなくてもほとんどいたるところゼロですよね()。まあどうでもいい話は置いておきましょう。基本的にはK箇所ゼロでないところを選んで、それぞれ1〜9で埋めるので、\binom{hoge}{K}9^Kみたいな感じにすれば良さそうです。あとは桁を上から見ていって適当に桁DPっぽいことをすればいいです。桁を上から見ていって、今まで何桁非零の値があったかを管理して行きます。今見ている桁が0であれば、次の桁に進みます。非零のとき、例えば3のとき、その桁が0,1,2であれば、それ以下の桁は自由に変えられるので、なんやかんやしてO(1)で計算します。そして3で固定して、次の桁に進みます。もしも固定した非零の桁がK以上になったら、あとは全部0なので、答えを1だけ増やして終了です。

実装例

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

ll comb(ll a,ll b){
    if(a<0||b<0||a<b) return 0;
    ll c{1};
    for(int i{};i<b;++i) c*=a-i;
    for(int i{1};i<=b;++i) c/=i;
    return c;
}

int main(){
    string n;
    int k;
    cin>>n>>k;
    ll ans{},p[]={1,9,81,729};
    int m=n.length(),cnt{k};
    for(int i{};i<m;++i){
        if(n[i]-'0'){
            ans+=comb(m-i-1,cnt)*p[cnt];
            if(cnt) ans+=comb(m-i-1,cnt-1)*p[cnt-1]*(n[i]-'1');
            --cnt;
            if(!cnt){
                ++ans;
                break;
            }
        }
    }
    cout<<ans<<endl;
}

コンテスト中のACコード

F - Many Many Paths

思考

高校数学や競プロの一般知識としてf(r,c)=\binom{r+c}{r}です。またg(R,C)=\sum_{r=0}^{R}\sum_{c=0}^{C}f(r,c)とすれば、\sum_{r=r_1}^{r_2}\sum_{c=c_1}^{c_2}f(r,c)=g(r_2,c_2)-g(r_2,c_1-1)-g(r_1-1,c_2)+g(r_1-1,c_1-1)となることもよく使いますね(2次元累積和でよく使うテクニックです)。
後はg(R,C)さえ高速に計算できればいいのですが、ただこの問題2次元累積和を普通に計算すると、それなりによしなにしてもO(RC)くらいかかってしまい、全然間に合いません。ここでよくあることなのですが、コンビネーション関連の和は割といい感じに閉じた形でかけることが多いので、†Wolfram Alpha†に投げるといい感じです。試しに投げてみるとこんな感じ*1になって、いつものコンビネーション計算だけで終わります。

実装例

#include<bits/stdc++.h>
using namespace std;

struct modint;
struct COMB{} comb; //O(N)の前計算でO(1)でコンビネーション計算をする。

modint g(int n,int m){
    return (comb(n+m+2,n+2)*(n+2)-m-1)/(m+1);
}

int main(){
    int r1,c1,r2,c2;
    cin>>r1>>c1>>r2>>c2;
    cout<<g(r2,c2)-g(r1-1,c2)-g(r2,c1-1)+g(r1-1,c1-1)<<endl;
}

コンテスト中のACコード

終わりに

まあテンポよく解けてよかったです。特に桁DPっぽいことは苦手なので、バグらせずに実装できてよかったです。後は遅刻さえしなければ10位以内も夢じゃないですねー。

*1:特殊文字のせいでリンクバグるからこれで許して https://www.wolframalpha.com/input/?i=sum+[i%3D0+to+n]+sum+[j%3D0+to+m]+binom(i%2Bj%2Ci)&lang=ja


スポンサードリンク