競プロ参加記023 AtCoder Beginner Contest 183 (ABC183)

2020/11/16 19:03 E問題をyoutubeの解説動画見て通したので、追記しました。

はじめに
A – ReLU
B – Billiards
C – Travel
D – Water Heater
E – Queen on Grid
F – Confluence
おわりに

はじめに

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A,B,C,D,Fの5完でした。
ABCのF問がコンテスト中に解けたの初ですね…。結構解いてる方が多かったので、難易度低め問題と思いますが良かったです。
B問が数学基礎問題だったのですが、考察に一番時間がかかりました。(数学の勉強をやり直したい＞＜)

A – ReLU

A - ReLU

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

数式をif文に直す問題です。
そのまま、実装しましょう。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int x;
    cin>>x;
    
    if(x<0) cout<<"0"<<endl;
    else cout<<x<<endl;
}

B – Billiards

B - Billiards

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

難しかったです。
x座標の移動が、abs(sx-gx)移動します。
ここでy座標の移動は、反射する前はsy、反射後はgyです。
反射までに移動する距離をaとしたとき、以下の式で表せられます。

sy:gy=a:abs(sx-gx)-a
a*gy=sy*abs(sx-gx)-sy*a
a*(gy+sy)=sy*abs(sx-gx)
a=sy*abs(sx-gx)/(gy+sy)

ここで計算した値はsxからの移動距離なため、gxとsxの位置関係から、計算した値を足すor引くした値が答えになります。

#include<bits/stdc++.h>

using namespace std;

int main(){
    double sx,sy,gx,gy;
    cin>>sx>>sy>>gx>>gy;

    double d=sy*abs(sx-gx)/(gy+sy);
    double ans=sx;
    if(sx<gx) ans+=d;
    else ans-=d;

    printf("%.12f\n",ans);

}

C – Travel

C - Travel

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

N=8しかないので、全探索しても8!=40320通りと余裕があります。
C++ならnext_permutationを使えば、順列が全通り生成できます。これを使って全探索しましょう。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int N,K;
    cin>>N>>K;
    int T[N+1][N+1];

    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            cin>>T[i][j];
        }
    }

    int ans=0;
    int perm[]={1,2,3,4,5,6,7,8};
    do{
        if(perm[0]==1){
            int c=0;
            int idx=1;
            int n=perm[0];
            do{
                c+=T[n][perm[idx%N]];
                n=perm[idx%N];
                idx++;
            }while(n!=perm[0]);
            //cout<<c<<endl;
            if(c==K) ans++;
        }
    }while(next_permutation(perm,perm+N));
    cout<<ans<<endl;
}

D – Water Heater

D - Water Heater

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

ある範囲の合計値を求め。それらがWを超えているかを求める問題です。
範囲の合計値が出てきたら、とりあえず”いもす”で殴ればOKかと思います。
いもすは、それぞれの範囲の
範囲の初めに+値、範囲の終わり+1に-値
をしたものに累積和を取る方法です。

#include<bits/stdc++.h>

using namespace std;

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

    long long dat[200001]={0};

    for(int i=0;i<N;i++){
        int S,T;
        long long P;
        cin>>S>>T>>P;
        dat[S]+=P;
        dat[T]-=P;
    }

    for(int i=0;i<200001;i++){
        if(i!=0) dat[i]+=dat[i-1];
        if(dat[i]>W){
            cout<<"No"<<endl;
            return 0;
        }
    }

    cout<<"Yes"<<endl;
}

E – Queen on Grid

E - Queen on Grid

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解説放送を見ました。

AtCoder Beginner Contest 183

DPで解けそうですが、何マスも進めるという操作が厄介です。
結論としては、累積和を更新しながらDPをします。

貰うDPを横移動だけ考えた場合
(i,j)=(i,j-1)+(i,j-2)+….+(i,0)
と言えます。この右側の式が累積和になっており、dpテーブルを更新するついでに更新します。
縦移動、斜め移動も同じように考えればOKです。

累積和のテーブルに関して、横、縦、斜めでそれぞれ違う配列で持って更新していきましょう。
(同じ配列で更新すると、累積の結果が四角形の区間の和とかになってしまいます。今回ほしい累積は一直線の和です。）

#include<bits/stdc++.h>

using namespace std;

int main(){
    int H,W;
    long long mod=1000000007;
    cin>>H>>W;

    string S[H];

    for(int i=0;i<H;i++){
        cin>>S[i];
    }

    long long dp[H][W];
    long long y[H][W];
    long long xy[H][W];
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            dp[i][j]=0;
            y[i][j]=0;
            xy[i][j]=0;
        }
    }
    xy[0][0]=1;
    y[0][0]=1;
    dp[0][0]=1;

    for(int i=0;i<H;i++){
        long long x[W];
        for(int j=0;j<W;j++) x[j]=0;
        if(i==0) x[0]=1;
        for(int j=0;j<W;j++){
            if(i==0&&j==0) continue;
            if(S[i][j]=='#') continue;
            if(i!=0) dp[i][j]+=y[i-1][j];
            if(j!=0) dp[i][j]+=x[j-1];
            if(i!=0&&j!=0) dp[i][j]+=xy[i-1][j-1];
            dp[i][j]%=mod;
            if(j!=0) x[j]+=x[j-1]+dp[i][j];
            else x[j]=dp[i][j];
            if(i!=0) y[i][j]+=y[i-1][j]+dp[i][j];
            else y[i][j]=dp[i][j];
            if(i!=0&&j!=0) xy[i][j]+=xy[i-1][j-1]+dp[i][j];
            else xy[i][j]=dp[i][j];
            x[j]%=mod;
            y[i][j]%=mod;
            xy[i][j]%=mod;
            //cout<<dp[i][j]<<" ";
        }
        //cout<<endl;
    }

    cout<<dp[H-1][W-1]%mod<<endl;
}

F – Confluence

F - Confluence

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

問題文を見た感じ、UnionFindな感じがします。
ただ単純にUnionFindで解くと、”生徒 x と合流している生徒(生徒 x を含む)のうち、クラス y に属している生徒の数”の処理がやっかいです。
今回は、UnionFindの親に子が属するクラスの個数を保持するmultimapを追加し、その値を返すようにしました。

#include<bits/stdc++.h>

using namespace std;

map<int,int> css[200001];

struct dsu {
  public:
    dsu() : _n(0) {}
    dsu(int n) : _n(n), parent_or_size(n, -1) {}

    int merge(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);

        parent_or_size[x] += parent_or_size[y];
        auto it=css[y].begin();
        while(it!=css[y].end()){
          css[x][it->first]+=it->second;
          it++;
        }
        parent_or_size[y] = x;
        return x;
    }

    bool same(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }

    int leader(int a) {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0) return a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    int size(int a) {
        assert(0 <= a && a < _n);
        return -parent_or_size[leader(a)];
    }

    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(
            std::remove_if(result.begin(), result.end(),
                           [&](const std::vector<int>& v) { return v.empty(); }),
            result.end());
        return result;
    }

  private:
    int _n;
    // root node: -1 * component size
    // otherwise: parent
    std::vector<int> parent_or_size;
};

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

    for(int i=1;i<=N;i++){
        int C;
        cin>>C;
        css[i][C]++;
    }

    dsu d(N+1);

    for(int i=0;i<Q;i++){
        int qu,x,y;
        cin>>qu>>x>>y;
        if(qu==1){
            d.merge(x,y);
        }
        else{
            int l=d.leader(x);
            cout<<css[l][y]<<endl;
        }
    }
}

UnionFind(dsu)のコードはatcoderのライブラリのものですが、merge時にcss変数(子の属するクラスの個数)にもmerge処理を行うよう追加しています。