ABC159 解説 - Motsu_xe 競プロのhogeやfuga

んー今回は割と簡単だったと思うのですが、Fにちょっと手間取りましたかね…。結果は64:10 175位でした。まあ大コケはしてないのでまあよしとしましょう。

A - The Number of Even Pairs

思考

和が偶数になるのは、偶+偶か奇+奇のときなので、答えは $\binom{n}{2}+\binom{m}{2}$ となります。

実装例

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

int main(){
    int n,m;
    cin>>n>>m;
    cout<<n*(n-1)/2+m*(m-1)/2<<endl;
}

コンテスト中のACコード

B - String Palindrome

思考

与えられた条件通りチェックするで普通に間に合います。とはいえ1,2つ目の条件から3つ目は導かれるので、1,2つ目の条件さえ確認すれば良いです。文字列長がかなり短いので定数倍も気にせず適当に実装すればそれでOKです。

実装例

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

int main(){
    string s,t,u,v;
    cin>>s;
    int n=s.length();
    t=s;
    u=v=s.substr(0,n/2);
    reverse(t.begin(),t.end());
    reverse(v.begin(),v.end());
    puts(u==v&&s==t?"Yes":"No");
}

コンテスト中のACコード

C - Maximum Volume

思考

こんなん $\left(\frac{L}{3}\right)^3$ 以外ありえんやろ！笑*1

実装例

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

int main(){
    double l;
    cin>>l;
    cout<<setprecision(20)<<(l/3.0)*(l/3.0)*(l/3.0)<<endl;
}

コンテスト中のACコード

D - Banned K

思考

まず除かない場合を考えます。これはA問題と大体同じで、整数 $i$ の書かれたボールの個数を $C_i$ とでもすると $\sum_{i=1}^{N}\binom{C_i}{2}$ となります。次に $i$ の書かれたボールを除く場合を考えると、 $\binom{C_i}{2}-\binom{C_i-1}{2}$ だけ減ることがすぐにわかるので、そのまま実装すれば良い。*2

実装例

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

int main(){
    int n;
    cin>>n;
    vector<ll> a(n),c(n+1);
    for(auto&i:a) cin>>i,++c[i];
    ll ans{};
    for(int i=1;i<=n;++i) ans+=c[i]*(c[i]-1)/2;
    for(int i=0;i<n;++i) cout<<ans-c[a[i]]*(c[a[i]]-1)/2+(c[a[i]]-1)*(c[a[i]]-2)/2<<endl;
}

コンテスト中のACコード

E - Dividing Chocolate

思考

Hが異様に小さいので、横方向の切れ目は全通り試しても $2^{H-1}\leq 512$ 通りである。縦方向の切れ目は端からKを超えない範囲で貪欲に取っていけば良いです。一回あたり $O(HW)$ でできるので、全体で $O(2^HHW)$ となります。場合によってはどう縦方向に切っても、条件を満たせない横方向の切り方が存在し、これを考慮しなくて1WA出しました。

実装例

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

int main(){
    int h,w,k;
    cin>>h>>w>>k;
    vector<string> s(h);
    for(auto&c:s) in>>c;
    int ANS=INT_MAX;
    for(int b=0;b<(1<<(h-1));++b){
        vector<vector<int>> v;
        vector<int> t(1,0);
        int ans{};
        for(int i=0;i<h-1;++i){
            if((b>>i)&1){
                ++ans;
                v.emplace_back(move(t));
                t.assign(1,i+1);
            }
            else{
                t.emplace_back(i+1);
            }
        }
        v.emplace_back(move(t));
        int n=v.size();
        vector<int> cnt(n);
        bool F{};
        for(int j=0;j<w;++j){
            bool f=false;
            vector<int> tmp(n);
            for(int l=0;l<n;++l){
                for(auto i:v[l]) if(s[i][j]=='1') ++tmp[l];
                if(tmp[l]>k){
                    F=true;
                    break;
                }
                if(cnt[l]+tmp[l]>k) f=true;
            }
            if(F) break;
            if(f) ++ans,cnt.swap(tmp);
            else fr(l,n) cnt[l]+=tmp[l];
        }
        if(F) continue;
        ANS=min(ans,ANS);
    }
    cout<<ANS<<endl;
}

コンテスト中のACコード

F - Knapsack for All Segments

思考

最初連続部分列だと思ってラクショーって言ってました、全然違うわ。基本的に部分和問題を解けばいいのですが、1つの合計がSとなる部分列」を複数回カウントする必要があります。部分列を $x_1,...,x_k$ とすると、この部分列は $x_1*(N-x_k+1)$ 回カウントされます。ここで部分和問題に一工夫なのですが、部分列の1個目として $A_i$ を入れるとき、 $i$ 個入れることにして、部分列のk個目(最後)として $A_i$ を入れるとき、 $(N-i+1)$ 入れることにすれば良いです。

実装例

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

struct modint; //いつもの

int main(){
    int n,s;
    cin>>n>>s;
    vector<int> a(n);
    for(auto&i:a) cin>>i;
    vector<modint> dp(s+1);
    modint ans{};
    dp[0]=1;
    for(int i=0;i<n;++i){
        if(a[i]<=s){
            for(int j=s;j>a[i];--j) dp[j]+=dp[j-a[i]];
            dp[a[i]]+=i+1;
            ans+=dp[s]*(n-i);
            dp[s]=0;
        }
    }
    cout<<ans<<endl;
}

コンテスト中のACコード

終わりに

F問題でなんとなく、最初と最後をよしなにするんだろうなぁとは思ったものの、細部をうまくすることが全然できなくて困ってしまいました。どう細部を詰めるかについてあまり記事で書けてないんですが、そこ書くのとても難しいです。記事の実力が上がりません。厳しい。まあ久しぶりにそれなりに時間を残して全完できたので、それなりに記事をかけました。毎回これをしたい。

*1:真面目にやるなら1個固定して二次関数なので真ん中、固定外して、みたいな感じでしょうか？

*2:この差分は $C_i-1$ ですが、まあ別にそのままでもいいでしょう。