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

AtCoder Beginner Contest 197（Sponsored by Panasonic）の解説記事です。なんか暇だったので久々に解説記事を書いてみました。2100点(51:37)67位でした。

A - Rotate

思考

最初長さ3に気づかず、for文要求してね？って思った。

実装例

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

int main(){
    string s;
    cin>>s;
    cout<<s[1]<<s[2]<<s[0]<<'\n';
}

コンテスト中のACコード

B - Visibility

思考

自分のいるところから、#に当たるまで移動して数えれば良いです。

実装例

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

int main(){
    int h,w,x,y;
    cin>>h>>w>>x>>y;--x,--y;
    vector<string> s(h);
    for(auto&c:s) cin>>c;
    int ans{1};
    for(int i{x-1};i>=0;--i){
        if(s[i][y]=='#') break;
        ++ans;
    }
    for(int i{x+1};i<h;++i){
        if(s[i][y]=='#') break;
        ++ans;
    }
    for(int j{y-1};j>=0;--j){
        if(s[x][j]=='#') break;
        ++ans;
    }
    for(int j{y+1};j<w;++j){
        if(s[x][j]=='#') break;
        ++ans;
    }
    cout<<ans<<'\n';
}

コンテスト中のACコード

C - ORXOR

思考

区間の分け方は, 仕切り(N-1)個を入れるかどうかの $2^{N-1}$ 通りなので, bit全探索で計算すれば間に合います。

実装例

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

int main(){
    unsigned n;
    cin>>n;
    vector<unsigned> a(n);
    for(auto&i:a) cin>>i;
    unsigned ans{UINT32_MAX};
    for(int b{};b<(1<<(n-1));++b){
        unsigned x{}, tmp=a[0];
        for(int i{};i<(n-1);++i){
            if((b>>i)&1){
                x^=tmp;
                tmp=a[i+1];
            }
            else{
                tmp|=a[i+1];
            }
        }
        chmin(ans, x^tmp);
    }
    cout<<ans<<'\n';
}

コンテスト中のACコード

D - Opposite

思考

0番目の点とN/2番目の点の中点が中心になります。中心からみて $\frac{2\pi}N$ 回転させたところにあるので, 回転行列考えて

$\begin{align*} \begin{pmatrix} x_1 \\ y_1 \\ \end{pmatrix} = \begin{pmatrix} \cos\frac{2\pi}N & -\sin\frac{2\pi}N \\ \sin\frac{2\pi}N & \cos\frac{2\pi}N \\ \end{pmatrix} \left( \begin{pmatrix} x_0 \\ y_0 \\ \end{pmatrix} - \begin{pmatrix} \frac{x_0+x_{N/2}}2 \\ \frac{y_0+y_{N/2}}2 \\ \end{pmatrix} \right) + \begin{pmatrix} \frac{x_0+x_{N/2}}2 \\ \frac{y_0+y_{N/2}}2 \\ \end{pmatrix} \end{align*}$
を計算すれば良い。

実装例

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

int main(){
    int n;
    long double x,y,X,Y,cx,cy,r,pi=3.14159265*2;
    cin>>n>>x>>y>>X>>Y;
    cx=(x+X)/2;cy=(y+Y)/2;
    r=sqrt((x-cx)*(x-cx)+(y-cy)*(y-cy));
    cout<<setprecision(20)<<(cx+(x-cx)*cos(pi/n)-(y-cy)*sin(pi/n))<<" "
    <<(cy+(x-cx)*sin(pi/n)+(y-cy)*cos(pi/n))<<'\n';
}

コンテスト中のACコード

E - Traveler

思考

(なんで色にしたんだろう)
広義単調増加に回収していくので、Cの値ごとに座標をまとめて、小さい方から訪れることを考えます。同じ値を回収する順番ですが、まず一番右のを回収してから、一番左のを回収するか、その逆以外は考える必要がありません(無駄なので)。ですから、Cの値ごとに、C以下を全部回収するのにかかる時間を、最終位置が一番左の時と最終位置が一番右の時とで分けて管理しておけば良いです。
オーバーフローに気をつけよう(1敗)。

実装例*1

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

int main(){
    int n;
    cin>>n;
    vector<vector<int>> v(n);
    for(int i{},x,c;i<(n);++i){
        cin>>x>>c;
        v[--c].push_back(x);
    }
    ll l{},cl{},r{},cr{};
    ll nl{},ncl{},nr{},ncr{};
    for(int i{};i<(n);++i){
        if(v[i].empty()) continue;
        sort(v[i].begin(),v[i].end());
        nl=v[i].front();
        nr=v[i].back();
        ncl=min(abs(l-nr)+nr-nl+cl, abs(r-nr)+nr-nl+cr);
        ncr=min(abs(l-nl)+nr-nl+cl, abs(r-nl)+nr-nl+cr);
        l=nl,r=nr,cl=ncl,cr=ncr;
    }
    cout<<min(cl+abs(l),cr+abs(r))<<'\n';
}

コンテスト中のACコード

F - Construct a Palindrome

思考

回文と言うのは、外側から攻めるか、中心から攻めるかだと思うのですが、計算量に余裕がありそうなので、中心全探索とかかなーと思って無駄な時間を過ごします。
外側から、同じ文字のときに1個ずつ進めるみたいなことをしたいなと思うと、まず(1,N)のペアから、1とNから生えている同じ文字の辺を辿って、みたいなことを連鎖的にやって、同じ頂点のペアor辺で繋がれた頂点のペアが現れれば、そこを中心とする回文になっています。よってpairをkeyとするBFSをすれば良いです(ただ奇数長と偶数長があるので、打ち切るタイミングに気をつけましょう)。

実装例*2

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

int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<pair<int,char>>> e(n);
    bool v[1000][1000]={};
    for(int i{},a,b;i<(m);++i){
        char c;
        cin>>a>>b>>c;--a,--b;
        v[a][b]=v[b][a]=true;
        e[a].emplace_back(b,c);
        e[b].emplace_back(a,c);
    }
    using ti = tuple<int,int,int>;
    priority_queue<ti, vector<ti>, greater<>> pq;
    vector<vector<bool>> cc(n,vector<bool>(n,false));
    pq.emplace(0,0,n-1);
    int ans{INT_MAX};
    while(!pq.empty()){
        auto[c,i,I]=pq.top();pq.pop();
        if(ans<=2*c) break;
        if(i==I){
            chmin(ans, 2*c);
            break;
        }
        if(v[i][I]){
            chmin(ans,2*c+1);
            continue;
        }
        for(auto[j,cj]:e[i]) for(auto[J,cJ]:e[I]) if(cj==cJ){
            if(cc[j][J]) continue;
            cc[j][J]=true;
            pq.emplace(c+1, j, J);
        }
    }
    cout<<(ans==INT_MAX?-1:ans)<<'\n';
}