Motsu_xe 競プロのhogeやfuga

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

ABC168 解説

かなりグダグダだったけど、今回のセットで全完できたのは結構偉いと思います。2100点(95:00)34位でした。

コンテストページ

A - ∴ (Therefore)

思考

pythonとかなら楽だったなと思いながら、愚直に実装。

実装例

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

int main(){
    int n;
    cin>>n;
    n%=10;
    if(n==3) cout<<"bon";
    else if(n==0 or n==1 or n==6 or n==8) cout<<"pon";
    else cout<<"hon";
    cout<<'\n';
}

コンテスト中のACコード

B - ... (Triple Dots)

思考

場合わけしてやるだけ、Aより楽じゃね?

実装例

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

int main(){
    int k;
    string s;
    cin>>k>>s;
    if(s.length()>k) cout<<s.substr(0,k)<<"..."<<'\n';
    else cout<<s<<'\n';
}

コンテスト中のACコード

C - : (Colon)

思考

気合で、2つの針のなす角を求めれば、余弦定理でできる。なす角は、12の向きからの時計回りの角度を求めて、差をよしなにすれば良い(よく考えるとよしなにしないでそのまま突っ込んでもcosの値に影響はない)。

実装例

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

int main(){
    double a,b,h,m,H,M;
    constexpr double pi=3.14159265358979;
    cin>>a>>b>>h>>m;
    H=h*pi/6+m*pi/360;
    M=m*pi/30;
    cout<<setprecision(20)<<sqrt(a*a+b*b-2*a*b*cos(H-M))<<'\n';
}

コンテスト中のACコード

D - .. (Double Dots)

思考

1からDFSして行けば最短経路がわかるので、DFSしながら手前の点を書き込んでいけば良い。

実装例

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

int main(){
    int n,m;
    cin>>n>>m;
    vector<int> e[100000];
    for(int i{};i<m;++i){
        int a,b;
        cin>>a>>b;
        --a,--b;
        e[a].emplace_back(b);
        e[b].emplace_back(a);
    }
    queue<int> q;
    q.push(0);
    vector<int> ans(n,-1);
    ans[0]=0;
    while(!q.empty()){
        int i=q.front();q.pop();
        for(auto&j:e[i]) if(ans[j]<0){
            ans[j]=i+1;
            q.push(j);
        }
    }
    cout<<"Yes"<<'\n';
    for(int i{1};i<n;++i) cout<<ans[i]<<'\n';
}

コンテスト中のACコード

E - ∙ (Bullet)

思考

仲の悪い条件を整理すると、0除算とかを一旦考えないことして適当に考えると

\begin{align*}
A_i*A_j+B_i*B_j=0&\Leftrightarrow A_i*A_j=-B_i*B_j\\
&\Leftrightarrow \frac{A_i}{B_i}=-\frac{B_j}{A_j}\\
&\Leftrightarrow \frac{A_i}{B_i}=-\frac1{\frac{A_j}{B_j}}
\end{align*}
となる。なのでA_i:B_iと言う比が重要であることがわかる。ここで、A_i=B_i=0のものは誰が相手でも仲が悪いので、無視して、最後にその数だけ足せば良い。よってA_i\neq0\lor B_i\neq 0と考えて良い。重要なのは比なので、(A_i,B_i)を比が変わらない様に、互いに素で、A_i>0\lor(a_i,B_j)=(0,1)となるようにとりなおすことにする。これは同じ比の(A_i,B_i)に対して一意に定まる。
mapなどを利用して、(a,b)(b,-a)(符号などは適切に変換する)の数をそれぞれX,Yとすると、これらのX+Y個の選び方は2^X+2^Y-1で、他のものの選び方とは独立している。よってこれらを適切に掛け算すれば良い。

実装例

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

struct modint; //いつもの
modint pwr(ll,ll) //mod累乗

int main(){
    ll n,a,b,d,c{};
    using P=pair<ll,ll>;
    map<P,int> v0,v1;
    cin>>n;
    for(int i{};i<n;++i){
        cin>>a>>b;
        if(a or b){
            d=gcd(a,b);
            a/=d;b/=d;
        }
        else{
            ++c;
            continue;
        }
        if(a<0) a=-a,b=-b;
        else if(a==0 and b<0) b=-b;
        v0[make_pair(a,b)]++;
        swap(a,b);
        b=-b;
        if(a<0) a=-a,b=-b;
        else if(a==0 and b<0) b=-b;
        v1[make_pair(a,b)]++;
    }
    map<P,bool> v;
    modint s{1};
    for(auto&[p,y]:v0){
        if(v[p]) continue;
        P q(p.second,p.first);
        q.second=-q.second;
        if(q.first<0) q.first=-q.first,q.second=-q.second;
        else if(q.first==0 and q.second<0) q.second=-q.second;
        v[q]=true;
        s*=pwr(2,y)+pwr(2,v1[p])-1;
    }
    cout<<s+c-1<<'\n';
}

コンテスト中のACコード

F - . (Single Dot)

思考

いい性質が全然なさそうで、行ける場所をDFSなりBFSなりで全探索する以外できそうもないです。よく考えると、座標圧縮してやることで、O(NM)個くらいしか考える必要がないので、気合入れて実装すれば通ります。

実装例

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

template<class T> void cc(vector<T> a,unordered_map<T,int>& nm,vector<int>& c){ //座標圧縮(aが座圧前、nmが前->後、cが後->前
    sort(a.begin(),a.end());
    fr(i,a.size()){
        if(i<a.size()-1&&a[i]==a[i+1]) continue;
        nm[a[i]]=c.size();
        c.emplace_back(a[i]);
    }
}

int main(){
    int n,m;
    cin>>n>>m;
    vector<int> a(n),b(n),c(n),d(m),e(m),f(m),v(2*n+m+1),h(n+2*m+1);
    for(int i{};i<n;++i){
        cin>>a[i]>>b[i]>>c[i];
        v[i]=a[i];
        v[i+n]=b[i];
        h[i]=c[i];
    }
    for(int i{};i<m;++i){
        cin>>d[i]>>e[i]>>f[i];
        v[i+n*2]=d[i];
        h[i+n]=e[i];
        h[i+n+m]=f[i];
    }
    unordered_map<int,int> nmv,nmh;
    vector<int> V,H;
    cc(v,nmv,V);cc(h,nmh,H);
    auto lv=vector(V.size(),vector<bool>(H.size()));
    auto lh=vector(V.size(),vector<bool>(H.size()));
    for(int i{};i<n;++i){
        a[i]=nmv[a[i]];
        b[i]=nmv[b[i]];
        c[i]=nmh[c[i]];
        for(int I=a[i];I<b[i];++I) lv[I][c[i]]=true;
    }
    for(int i{};i<m;++i){
        d[i]=nmv[d[i]];
        e[i]=nmh[e[i]];
        f[i]=nmh[f[i]];
        for(int J=e[i];J<f[i];++J) lh[d[i]][J]=true;
    }
    ll ans{};
    int X=nmv[0],Y=nmh[0];
    stack<pair<int,int>> st;
    st.emplace(X,Y);
    int limv=V.size()-1,limh=H.size()-1;
    if(X==limv or Y==limh) return puts("INF"),0;
    auto vis=vector(limv,vector<bool>(limh));
    while(!st.empty()){
        auto[x,y]=st.top();st.pop();
        if(vis[x][y]) continue;
        vis[x][y]=true;
        ans+=(ll)(V[x+1]-V[x])*(H[y+1]-H[y]);
        if(x==0 and !lh[x][y]) return puts("INF"),0;
        if(y==0 and !lv[x][y]) return puts("INF"),0;
        if(x+1==limv and !lh[x+1][y]) return puts("INF"),0;
        if(y+1==limh and !lv[x][y+1]) return puts("INF"),0;
        if(x>0 and !vis[x-1][y] and !lh[x][y]) st.emplace(x-1,y);
        if(y>0 and !vis[x][y-1] and !lv[x][y]) st.emplace(x,y-1);
        if(x+1<limv and !vis[x+1][y] and !lh[x+1][y]) st.emplace(x+1,y);
        if(y+1<limh and !vis[x][y+1] and !lv[x][y+1]) st.emplace(x,y+1);
    }
    cout<<ans<<'\n';
}

コンテスト中のACコード

終わりに

タイトルが面白くていい感じですね。問題としても気合が結構要る感じで、†競技プログラミング†って感じがしました。楽しい。


スポンサードリンク