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

AtCoder Beginner Contest 199（Sponsored by Panasonic）の解説記事です。私は2100点(75:34)106位でした。

A - Square Inequality

思考

オーバーフローなどが起きない制約であることだけ気をつけると、やるだけです。

実装例

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

int main(){
    int a,b,c;
    cin>>a>>b>>c;
    puts(a*a+b*b<c*c?"Yes":"No");
}

コンテスト中のACコード

B - Intersection

思考

$A\leq x \leq B$ は $A\leq x$ かつ $x\leq B$ であることと同値です。

また $A\leq x$ かつ $A'\leq x$ は $max(A,A')\leq x$ と同値です。

同様に考えると、

「任意の $i$ について $A_i\leq x\leq B_i$ 」
$\Leftrightarrow$ 「任意の $i$ について $A_i\leq x$ かつ $x\leq B_i$ 」
$\Leftrightarrow$ 「 $\max\{A_i\}\leq x$ かつ $x\leq \min\{B_i\}$ 」
$\Leftrightarrow$ 「 $\max\{A_i\}\leq x\leq \min\{B_i\}$ 」

となるので、 $\max\{A_i\}, \min\{B_i\}$ の大小にだけ気をつければ良い。

実装例

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

int main(){
    int n;
    cin>>n;
    vector<int> a(n),b(n);
    int A=INT_MIN, B=INT_MAX;
    for(auto&i:a) cin>>i,chmax(A,i);
    for(auto&i:b) cin>>i,chmin(B,i);
    if(A>B) cout<<0<<'\n';
    else cout<<B-A+1<<'\n';
}

コンテスト中のACコード

C - IPFL

思考

クエリ2を愚直にやると1クエリに $\Theta(N)$ かかってしまい間に合いませんが、前半と後半を入れ替える操作は、前半と後半を別々に管理しておけば、今入れ替わっているかどうかだけ覚えておけば、クエリ1にもクエリ2にも対応することができます。

実装例

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

int main(){
    int n,q;
    string s[2];
    cin>>n>>s[0]>>q;
    s[1]=s[0].substr(n);
    s[0]=s[0].substr(0,n);
    bool f=false;
    for(int i{},t,a,b;i<(q);++i){
        cin>>t>>a>>b;
        if(t==1){
            --a,--b;
            if(f) swap(s[1-a/n][a%n],s[1-b/n][b%n]);
            else swap(s[a/n][a%n],s[b/n][b%n]);
        }
        else{
            f=!f;
        }
    }
    if(f) cout<<s[1]<<s[0]<<'\n';
    else cout<<s[0]<<s[1]<<'\n';
}

コンテスト中のACコード

D - RGB Coloring 2

思考

塗り分けを全パターン考えると $3^N$ 通りあり、これは間に合いません。
隣あっている2つの頂点の色が別であるものだけ考えれば良いので、1つの頂点について色を決めたら、隣の頂点については2通りしか色を考えなくていいことがわかります。サイズ $S$ の連結成分について高々 $3\cdot2^{S-1}$ 通りだけ考えて、各連結成分についてのパターンの数をかけてやればいいことがわかります。

実装例

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

vector<vector<int>> e;
vector<int> c;
ll ans{1}, tmp;

void rec(vector<int>&g, int i=0){
    if(i==g.size()){
        ++tmp;
        return;
    }
    bool K[3]={};
    for(auto&j:e[g[i]]) if(j<g[i]){
        K[c[j]]=true;
    }
    for(int j{};j<(3);++j){
        if(!K[j]){
            c[g[i]]=j;
            rec(g,i+1);
        }
    }
}

int main(){
    int n, m;
    cin >> n >> m;
    e.resize(n);
    dsu d(n);
    c.assign(n,-1);
    for(int i{},a,b;i<(m);++i){
        cin>>a>>b;
        --a,--b;
        if(a>b) swap(a,b);
        e[a].push_back(b);
        e[b].push_back(a);
        d.merge(a,b);
    }
    for(auto g:d.groups()){
        sort(begin(g),end(g));
        tmp=0;
        rec(g);
        ans*=tmp;
    }
    cout<<ans<<'\n';
}

コンテスト中のACコード

E - Permutation

思考

各条件を考えるとき、重要なのは $a_1,a_2,\ldots,a_{X_i}$ の集合であって、順番は関係ありません。よって $S\subset\{1,2,\ldots,N\}$ に対して、

$\mathrm{dp}_S=$ (最初の $|S|$ 項の集合が $S$ である場合の数)

と定めると、 $X_i=|S|$ であるものについて、条件を満たしているか考えると、うまく遷移を作ることができ, $O( (N+M)2^N)$ *1とかで解くことができます。

実装例

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

int main(){
    int n,m;
    cin >> n >> m;
    vector<ll> dp(1<<n);
    vector<vector<int>> Y(n), Z(n);
    for(int i{},x,y,z;i<(m);++i){
        cin>>x>>y>>z;
        Y[x].push_back(y);
        Z[x].push_back(z);
    }
    dp[0]=1;
    vector<int> p;
    for(int b{};b<(1<<n)-1;++b){
        p.assign(n+1,0);
        for(int i{};i<(n);++i){
            p[i+1]=p[i]+((b>>i)&1);
        }
        bool f=true;
        for(int j{};j<(Y[p[n]].size());++j){
            if(p[Y[p[n]][j]]>Z[p[n]][j]){
                f=false;
                break;
            }
        }
        if(!f) continue;
        for(int i{};i<(n);++i){
            if(((b>>i)&1)==0){
                dp[b|(1<<i)]+=dp[b];
            }
        }
    }
    cout<<dp[(1<<n)-1]<<'\n';
}

コンテスト中のACコード

F - Graph Smoothing

思考

$k$ 回の操作後に頂点 $1,2,\ldots,N$ に書かれている数の期待値( $E_i$ )がわかっている時, $k+1$ 回の操作後に頂点 $1,2,\ldots,N$ に書かれている数の期待値を考えます。
これは辺 $(X_i,Y_i)$ が選ばれた時、頂点 $X_i,Y_i$ はともに $\frac{E_i+E_j}2$ が期待値であり、それ以外の頂点 $l$ は、 $E_l$ が期待値となります。全ての辺が一様に選ばれることに注意すると、これから、 $k+1$ 回の操作後の期待値は、 $k$ 回の操作後の期待値を並べたベクトルに、行列をかけてやることで求まることがわかります。よって行列累乗によって、十分高速に求めることができます。

実装例

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

using mint = modint1000000007;

template<class T> struct mat;\\行列のライブラリ

int main(){
    int n,m,k;
    cin >> n >> m>> k;
    vector<vector<mint>> a(n,vector<mint>(1));
    int tmp;
    for(auto&i:a){
        cin>>tmp;
        i[0]=tmp;
    }
    mint iv=mint(m).inv(), iv2=iv/2;
    vector<vector<mint>> e(n,vector<mint>(n));
    for(int i{},x,y;i<(m);++i){
        cin>>x>>y;
        --x,--y;
        for(int i{};i<(n);++i){
            if(i!=x and i!=y){
                e[i][i]+=iv;
            }
        }
        e[x][x]+=iv2;
        e[x][y]+=iv2;
        e[y][x]+=iv2;
        e[y][y]+=iv2;
    }
    for(auto v:(mat<mint>(e).pow(k)*mat<mint>(a)).v){
        cout<<v[0].val()<<'\n';
    }
}

コンテスト中のACコード

終わりに

Panasonicさん、いつもお世話になっております(2回目)。

*1:もうちょっと早い