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; }
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; }
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"); }
こちらはなんとなく書いた一行コードです(いらない)。
print('YNEOS'[int(input())!=len(set(input().split()))::2])
D - Dice in Line
思考
期待値の線型性から、それぞれのダイスの期待値の和を足せばいいです。それぞれのダイスの期待値はであるから、単純に連続する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; }
E - Almost Everywhere Zero
思考
ほとんどいたるところゼロ、この場合有限列だから、ゼロが一個もなくてもほとんどいたるところゼロですよね()。まあどうでもいい話は置いておきましょう。基本的にはK箇所ゼロでないところを選んで、それぞれ1〜9で埋めるので、みたいな感じにすれば良さそうです。あとは桁を上から見ていって適当に桁DPっぽいことをすればいいです。桁を上から見ていって、今まで何桁非零の値があったかを管理して行きます。今見ている桁が0であれば、次の桁に進みます。非零のとき、例えば3のとき、その桁が0,1,2であれば、それ以下の桁は自由に変えられるので、なんやかんやしてで計算します。そして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; }
F - Many Many Paths
思考
高校数学や競プロの一般知識としてです。またとすれば、となることもよく使いますね(2次元累積和でよく使うテクニックです)。
後はg(R,C)さえ高速に計算できればいいのですが、ただこの問題2次元累積和を普通に計算すると、それなりによしなにしてもくらいかかってしまい、全然間に合いません。ここでよくあることなのですが、コンビネーション関連の和は割といい感じに閉じた形でかけることが多いので、†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; }
終わりに
まあテンポよく解けてよかったです。特に桁DPっぽいことは苦手なので、バグらせずに実装できてよかったです。後は遅刻さえしなければ10位以内も夢じゃないですねー。