Motsu_xe 競プロのhogeやfuga

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

ABC166 解説

Eが簡単すぎてガチで引いて調子が崩れた(言い訳)。Fで大破滅しました…。かなり嫌な気持ちです。結果は96:40 598位。

コンテストページ

A - A?C

思考

やるだけオブザイヤー2020ノミネート。

実装例

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

int main(){
    string s;
    cin>>s;
    puts(s=="ABC"?"ARC":"ABC");
}

コンテスト中のACコード

B - Trick or Treat

思考

一度でも出現したら対象から外れるので、boolの配列を持って出現をチェックします。

実装例

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

int main(){int n,k,d,a;
    cin>>n>>k;
    vector<bool> v(n,true);
    for(int i{};i<k;++i){
        cin>>d;
        for(int j{};j<d;++j){
            cin>>a;
            --a;
            v[a]=false;
        }
    }
    int ans{};
    for(int i{};i<n;++i) if(v[i]) ++ans;
    cout<<ans<<endl;
}

コンテスト中のACコード

C - Peaks

思考

道の両端で、真に高くはない方が対象から外れるというだけでB問題と同じです。

実装例

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

int main(){
    int n,m,a,b;
    cin>>n>>m;
    vector<int> h(n);
    vector<bool> g(n,true);
    for(auto&i:h) cin>>i;
    for(int i{};i<m;++i){
        cin>>a>>b;
        --a,--b;
        if(h[a]<=h[b]) g[a]=false;
        if(h[a]>=h[b]) g[b]=false;
    }
    int c{};
    for(int i{};i<n;++i) if(g[i]) ++c;
    cout<<c<<'\n';
}

コンテスト中のACコード

D - I hate Factorization

思考

Xが5乗数として非負のものの和か差になっているかを考えればよい。(C+1)^5-C^5=5C^4+..\geq 5C^4なので、A\gt 1000とかだと明らかに差も和も該当しない。なのでA\leq 1000なるものだけ考えておけばよい。1000以下の非負整数Cについて連想配列mpでmp[C^5]=Cとしておいて、AかBを固定すれば簡単にチェックできる。

実装例

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

int main(){
    ll x;
    cin>>x;
    unordered_map<ll,int> mp;
    for(int i{1000};i--;){
        ll c{1};
        for(int j{};j<5;++j) c*=i;
        if(mp[c+x])
            return cout<<mp[c+x]<<" "<<i<<endl,0;
        if(mp[x-c])
            return cout<<mp[x-c]<<" "<<-i<<endl,0;
        mp[c]=i;
    }
}

コンテスト中のACコード

E - This Message Will Self-Destruct in 5s

思考

i\lt jとするとA_i+A_j=j-i\Leftrightarrow A_i+i=j-A_jとなっていればよい。よって連想配列j-A_jの個数を保存しながら、配列を右から舐めていって、数えていけばいい。D問題のが100倍むずいだろD問題でちょっとめんどい解法使ってたからDのがむずい気がしたけど、そうでもないかも、でもEのがやっぱ簡単だとは思う。遅刻しなければFAが…って言おうとしたけど、まあ2分切れたかは怪しいな。

実装例

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

int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    for(auto&i:a) cin>>i;
    unordered_map<int,int> mp;
    ll ans{};
    ifr(i,n){
        ans+=mp[a[i]+i];
        mp[i-a[i]]++;
    }
    cout<<ans<<endl;
}

コンテスト中のACコード

F - Three Variables Game

思考

まずA+B+C\neq 2のとき、少ない方から多い方に、同じなら適当に移すことで達成できるなら達成できるし、失敗するようなら失敗する。これを示す。
A+B+C=0のときはどうやっても無理。
A+B+C=1のときは、全ての操作が、選択肢が1つ以下なので、OK。
A+B+C\geq 3のとき。もし初期状態で0が2つあって、初手でその2つが選ばれた場合は無理。初手でその2つが選ばれなければ、0は1つになる。よって全て初期状態で0が1つ以下の場合に帰着される。定めた移し方では、0の数は増えることはない増えるとしたら0が0個のときだけなので、常に0は1つ以下となり、必ず失敗しない。
よって示された。
あとはA+B+C=2のときを考えればいい。状態は(A,B,C)=(0,1,1),(1,0,1),(1,1,0),(2,0,0),(0,2,0),(0,0,2)の6つしかあり得ないので、どの状態に遷移可能かDPすればいい。実際の操作の復元は、可能な操作をDPの結果から遡っていけばいい。ところでいい感じの実装ありますか??破滅しました。

実装例

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

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,A,B,C;
    cin>>n>>A>>B>>C;
    string ans;
    ans.reserve(n);
    if(A+B+C==2){
        auto v=vector(n+1,vector(6,false));
        if(!A+!B+!C==1){
            if(!A) v[0][0]=true;
            if(!B) v[0][1]=true;
            if(!C) v[0][2]=true;
        }
        else{
            if(A) v[0][3]=true;
            if(B) v[0][4]=true;
            if(C) v[0][5]=true;
        }
        vector<string> s(n);
        for(int i{};i<n;++i){
            cin>>s[i];
            if(s[i]=="AB"){
                if(v[i][0]) v[i+1][1]=true;
                if(v[i][1]) v[i+1][0]=true;
                if(v[i][2]) v[i+1][3]=v[i+1][4]=true;
                if(v[i][3] or v[i][4]) v[i+1][2]=true;
            }
            if(s[i]=="AC"){
                if(v[i][0]) v[i+1][2]=true;
                if(v[i][2]) v[i+1][0]=true;
                if(v[i][1]) v[i+1][3]=v[i+1][5]=true;
                if(v[i][3] or v[i][5]) v[i+1][1]=true;
            }
            if(s[i]=="BC"){
                if(v[i][1]) v[i+1][2]=true;
                if(v[i][2]) v[i+1][1]=true;
                if(v[i][0]) v[i+1][4]=v[i+1][5]=true;
                if(v[i][4] or v[i][5]) v[i+1][0]=true;
            }
            bool F{};
            for(int j{};j<6;++j) F=F||v[i+1][j];
            if(!F) return puts("No"),0;
        }
        for(int j{};j<6;++j) if(v[n][j]){
            cout<<"Yes"<<'\n';
            int t=j;
            stack<char> ans;
            for(int i{n};i--;){
                if(s[i]=="AB"){
                    if(t==0) ans.push('B'),t=1;
                    else if(t==1) ans.push('A'),t=0;
                    else if(t==2){
                        if(v[i][3]) ans.push('B'),t=3;
                        else ans.push('A'),t=4;
                    }
                    else if(t==3) ans.push('A'),t=2;
                    else if(t==4) ans.push('B'),t=2;
                }
                if(s[i]=="AC"){
                    if(t==0) ans.push('C'),t=2;
                    else if(t==2) ans.push('A'),t=0;
                    else if(t==1){
                        if(v[i][3]) ans.push('C'),t=3;
                        else ans.push('A'),t=5;
                    }
                    else if(t==3) ans.push('A'),t=1;
                    else if(t==5) ans.push('C'),t=1;
                }
                if(s[i]=="BC"){
                    if(t==1) ans.push('C'),t=2;
                    else if(t==2) ans.push('B'),t=1;
                    else if(t==0){
                        if(v[i][4]) ans.push('C'),t=4;
                        else ans.push('B'),t=5;
                    }
                    else if(t==4) ans.push('B'),t=0;
                    else if(t==5) ans.push('C'),t=0;
                }
            }
            while(!ans.empty()) cout<<ans.top()<<'\n',ans.pop();
            return 0;
        }
        assert(false);
    }
    for(int i{};i<n;++i) {
        string s;
        cin>>s;
        if(s=="AB"){
            if(A<B){
                ++A;--B;
                ans+='A';
            }
            else{
                ++B;--A;
                ans+='B';
            }
        }
        if(s=="BC"){
            if(B<C){
                ++B;--C;
                ans+='B';
            }
            else{
                ++C;--B;
                ans+='C';
            }
        }
        if(s=="AC"){
            if(C<A){
                ++C;--A;
                ans+='C';
            }
            else{
                ++A;--C;
                ans+='A';
            }
        }
        if(A<0||B<0||C<0) return puts("No"),0;
    }
    cout<<"Yes"<<'\n';
    for(auto&c:ans) cout<<c<<'\n';
}

コンテスト中のACコード

終わりに

Fで適当こきすぎて、実装が破滅して終了しました。これどうやったらきれいに書けるの???


スポンサードリンク