AtCoder Beginner Contest 187(ABC187)

ABC

A – Large Digits

A – Large Digits (atcoder.jp)

問題文通り実装します。
Aにしては実装が少し重い気がします。

#include<bits/stdc++.h>
//#include<atcoder/all>

using namespace std;
//using namespace atcoder;

int main(){
    int A,B;
    cin>>A>>B;
    cout<<max(A/100+A/10%10+A%10,B/100+B/10%10+B%10)<<endl;
}

B – Gentle Pairs

B – Gentle Pairs (atcoder.jp)

傾きとは、xが1増えるごとにyはいくつ増えるか？というものです。
数式的には、

傾き=ある2点のyの差/ある2点のxの差

となります。これが1より小さいかを見ていけば良いので

ある2点のyの差/ある2点のxの差 <= 1
ある2点のyの差 <= ある2点のxの差

となります。-1に関しては？となりますが、

-(ある2点のyの差/ある2点のxの差) >= -1  ※yの差が負になるので-が付く
ある2点のyの差/ある2点のxの差 <= 1

となるため、1以下だけで問題ありません。

#include<bits/stdc++.h>
//#include<atcoder/all>

using namespace std;
//using namespace atcoder;

int main(){
    int N;
    cin>>N;

    int x[N],y[N];
    for(int i=0;i<N;i++){
        cin>>x[i]>>y[i];
    }

    int ans=0;
    for(int i=0;i<N;i++){
        for(int j=i+1;j<N;j++){
            int xd=abs(x[i]-x[j]);
            int yd=abs(y[i]-y[j]);
            if(yd<=xd) ans++;
        }
    }

    cout<<ans<<endl;
}

C – 1-SAT

C – 1-SAT (atcoder.jp)

!のつく文字列と、つかない文字列を別々で管理し。両方の中で一致するものを探索すればOKです。

#include<bits/stdc++.h>
//#include<atcoder/all>

using namespace std;
//using namespace atcoder;

int main(){
    int N;
    cin>>N;

    set<string> s1,s2;

    for(int i=0;i<N;i++){
        string s;
        cin>>s;
        if(s[0]=='!'){
            s=s.substr(1,s.size()-1);
            s2.insert(s);
        }
        else s1.insert(s);
    }

    auto it=s1.begin();
    while(it!=s1.end()){
        if(s2.find(*it)!=s2.end()){
            cout<<*it<<endl;
            return 0;
        }
        it++;
    }

    cout<<"satisfiable"<<endl;
}

D – Choose Me

D – Choose Me (atcoder.jp)

演説を行わない場合、
高橋氏の票=0 青木氏の票=Asum
になります。
ここで1番目の町で演説を行った場合、それぞれの票は
高橋氏の票=B1+A1 青木氏の票=Asum-A1
となります。相対的に考えると、高橋氏の票がA1*2+B1だけ増えます。

“最小”の数が知りたいので、相対の増加量であるAi*2+Biが大きい順に貪欲にすれば良さそうです。

#include<bits/stdc++.h>
//#include<atcoder/all>

using namespace std;
//using namespace atcoder;

int main(){
    int N;
    cin>>N;

    multiset<long long> mx;
    long long sum=0;
    for(int i=0;i<N;i++){
        long long A,B;
        cin>>A>>B;
        sum+=A;
        mx.insert(A+A+B);
    }

    auto it=mx.rbegin();
    int ans=0;
    while(it!=mx.rend()){
        sum-=*it;
        ans++;
        if(sum<0){
            cout<<ans<<endl;
            break;
        }
        it++;
    }
}

E – Through Path

E – Through Path (atcoder.jp)

毎回毎回更新するとNGです。
木であるため、ti=1にしてもti=2にしても、ある頂点を境に区間更新されそうです。
区間更新を効率的に行うアルゴリズムを使うと良さそうです。今回はimosっぽく解きました。

具体的には適当な頂点を根として、最後は根から葉に向かってimosを計算していくようにします。
こう考えた場合、区間更新が根を通らない場合は、区間更新の入り口の頂点に+xiすればOKです。問題は区間更新が根を通る場合です。
(図で書くと分かりやすいですが、根から葉に向かってimosすると更新してはいけない頂点まで更新されます)
解決としては全頂点に+xiを行い、区間更新されない部分の入り口を-xiすればいいです。これにより、区間更新される部分だけが+xiされます。

#include<bits/stdc++.h>
//#include<atcoder/all>

using namespace std;
//using namespace atcoder;

int main(){
    long long N;
    cin>>N;

    vector<long long> v[N+1];
    long long a[N],b[N];
    for(long long i=0;i<N-1;i++){
        cin>>a[i+1]>>b[i+1];
        v[a[i+1]].push_back(b[i+1]);
        v[b[i+1]].push_back(a[i+1]);
    }

    long long d[N+1];
    for(long long i=0;i<N+1;i++) d[i]=-1;

    queue<long long> qv,qn;
    qv.push(1);
    qn.push(1);
    while(!qv.empty()){
        long long nv=qv.front();
        long long nn=qn.front();
        qv.pop();
        qn.pop();
        d[nv]=nn;
        for(long long i=0;i<v[nv].size();i++){
            long long t=v[nv][i];
            if(d[t]==-1){
                qv.push(t);
                qn.push(nn+1);
            }
        }
    }

    long long all=0;
    long long ans[N+1];
    for(long long i=0;i<N+1;i++) ans[i]=0;

    long long Q;
    cin>>Q;
    for(long long i=0;i<Q;i++){
        long long t,ai,x;
        cin>>t>>ai>>x;
        long long n1,n2;
        if(t==1){
            n1=a[ai];
            n2=b[ai];
        }
        else{
            n1=b[ai];
            n2=a[ai];
        }
        if(d[n1]>d[n2]){
            ans[n1]+=x;
        }
        else{
            all+=x;
            ans[n2]-=x;
        }
    }

    qv.push(1);
    qn.push(ans[1]);
    long long che[N+1];
    for(long long i=0;i<N+1;i++) che[i]=-1;
    while(!qv.empty()){
        long long nv=qv.front();
        long long nn=qn.front();
        qv.pop();
        qn.pop();
        ans[nv]=nn+all;
        che[nv]=1;
        for(long long i=0;i<v[nv].size();i++){
            long long t=v[nv][i];
            if(che[t]==-1){
                qv.push(t);
                qn.push(nn+ans[t]);
            }
        }
    }

    for(long long i=1;i<=N;i++){
        cout<<ans[i]<<endl;
    }
}

最小のwhileで木構造の深さを計算し、根を通るかどうかの判定に使います。
次のforでimosの前準備をします。更新区間に根がある場合は、all変数に+xiしておき、更新されない区間を-xiします。
最後のwhileでimosの計算を行います。計算の際、allによる下駄を履かせていきます。

atcoderには珍しく実装が重めだと感じました。

F – Close Group

F – Close Group (atcoder.jp)

グラフが連結されている頂点同士は同じ色を塗る、グラフが連結されていない頂点同士は違う色を塗る…と考えると、この問題は彩色問題に置き換えることができます。
具体的には、各頂点同士に辺を張っているN頂点のグラフから、Ai-Biである辺を取り除いたものに対して、色を塗るには何色必要か考えればよいです。

指数時間アルゴリズム入門 (slideshare.net)

エデュ解にも書かれてますが、O((2^N)*N)で解けるアルゴリズムがあります。
…が、このスライドの内容が分からない…。

彩色数を求めるアルゴリズム – Learning Algorithms (hatenablog.com)

もう少し調べてみると、C++でずばりのコードを書いてる方がいました。
今回はこれを使って解いてみます。

#include<bits/stdc++.h>
//#include<atcoder/all>

using namespace std;
//using namespace atcoder;

//https://kokiymgch.hatenablog.com/entry/2018/01/27/235959
unsigned long xor128() {
        static unsigned long x = 123456789, y = 362436069, z = 521288629, w = 88675123;
        unsigned long t = (x ^ (x << 11));
        x = y; y = z; z = w;
        return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}
int RandomPrime() {
        auto prime = [&](int n) {
                for (int i = 2; i * i <= n; i ++) if (n % i == 0) return false;
                return true;
        };
        int modulo = 1000000000;
        modulo += (int) (xor128() % 100000000);
        while (!prime(modulo)) modulo ++;
        return modulo;
}
int ChromaticNumber(const vector<vector<bool>> &tmpg) {
        int n = tmpg.size();
        if (n == 0) return 0;
        vector<int> g(n);
        for (int i = 0; i < n; i ++) {
                for (int j = 0; j < n; j ++) {
                        if (tmpg[i][j]) {
                                g[i] |= (1 << j);
                        }
                }
        }
        int all = 1 << n;
        vector<int> a(all), s(all);
        a[0] = 1;
        int modulo = RandomPrime();
        for (int i = 1; i < all; i ++) {
                int j = __builtin_ctz(i);
                a[i] = a[i - (1 << j)] + a[(i - (1 << j)) & ~g[j]];
                if (a[i] >= modulo) a[i] -= modulo;
        }
        for (int i = 0; i < all; i ++) {
                s[i] = ((n - __builtin_popcount(i)) & 1 ? -1 : 1);
        }
        for (int k = 1; k < n; k ++) {
                long long sum = 0;
                for (int i = 0; i < all; i ++) {
                        long long cur = ((s[i] * (long long) a[i]) % modulo);
                        s[i] = (int) cur;
                        sum += cur;
                }
                if (sum % modulo != 0) return k;
        }
        return n;
}

int main(){
    int N,M;
    cin>>N>>M;

    vector<vector<bool>> v;
    for(int i=0;i<=N;i++){
        vector<bool> vt;
        for(int j=0;j<=N;j++) vt.push_back(true);
        v.push_back(vt);
    }

    for(int i=0;i<M;i++){
        int A,B;
        cin>>A>>B;
        v[A][B]=false;
        v[B][A]=false;
    }

    cout<<ChromaticNumber(v)-1<<endl;


}

ChromaticNumberにはN*Nのvectorを渡します。
vectorの中身は頂点(i,j)に辺がある場合はtrue、ない場合はfalseを詰めます。

彩色問題を解くアルゴリズムの理解と実装は宿題ですね…。

コメント

タイトルとURLをコピーしました