ABC393個人的備忘録

存在しないものを追い求めた男の備忘録です

コンテスト概要

AtCoder Beginner Contest 393

開催日:2025年2月15日 21:00-22:40

A - Poisonous Oyster

考察

やろうと思えばスマートな解法も出来そうだが、どうせ４パターンしかないので全部書く。
食べた牡蠣を勘違いしていないかだけ注意。

提出

A.cpp

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

int main(){
    string x,y;
    cin >> x >> y;

    if(x == "fine" && y == "fine") cout << "4" << endl;
    if(x == "fine" && y == "sick") cout << "3" << endl;
    if(x == "sick" && y == "fine") cout << "2" << endl;
    if(x == "sick" && y == "sick") cout << "1" << endl; 
}

B - A..B..C

考察

どうせ制約が100なので三重ループを回す。

制約がデカければBを固定してACを探したりすれば何とかなるかな？

提出

B.cpp

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

int main(){
    string s;
    cin >> s;

    int len = s.length();

    int ans  = 0;
    for(int i=0;i<len;i++){
        if(s[i] != 'A') continue;
        for(int j=i+1;j<len;j++){
            if(s[j] != 'B')continue;
            for(int k=j+1;k<len;k++){
                if(s[k] != 'C')continue;

                //差が同じならカウント
                if(j-i == k-j)ans++;
            }
        }
    }

    cout << ans << endl;    
}

C - Make it Simple

考察

専門用語(?)が並んでややこしそうだが、要するに

〇同じ頂点を指している
〇同じペアがすでに結ばれてる

このような辺だけを順に撤去すればよい。

提出

C.cpp

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

int main(){
    int n,m;
    cin >> n >> m;

    //頂点同士が結ばれているかを確認する用
    map<pair<int,int>,bool>mp;
    int ans  = 0;
    for(int i=0;i<m;i++){
        int x,y;
        cin >> x >> y;

        //調べやすいよう大小関係を整える。
        if(x > y) swap(x,y);
        
        if(x == y) ans++;//同じ頂点ならいらない
        else if(mp[{x,y}]) ans++;//すでに結ばれているならいらない
        else mp[{x,y}] = true;//そうでないなら辺を結ぶ
    } 

    cout << ans << endl;
}

D - Swap to Gather

考察

めんどくさそうなのでいったんEに行ったのが間違いだった。
まず集合させるべき「１」を決める。
この時、ある「１」と基準の「１」の間にある「０」の数が移動させる回数になる。
これをすべての「１」について行いトータルの回数を出す。
もちろん毎回数えるとTLEなので累積和をあらかじめ調べておく。

右からの累積和を間違えたせいで40分近く無駄にする羽目に。

提出

D.cpp

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

int main(){
    int n;
    string s;
    cin >> n >> s;

    vector<ll>op (0);//'1'と'1'の間の'0'の数をまとめる。
    ll cnt = 0;
    bool che = false;
    for(auto x:s){
        if(x == '1'){
            if(che){
               op.push_back(cnt);
            }else che = true;
            cnt = 0;
        }else cnt++;
    }    

    if(op.size() == 0){
        cout << "0" << endl;
        return 0;
    }

    ll k = op.size();
    ll sum = 0;
    for(auto x:op){
        sum += k*x;
        k--;
    }

    k = op.size();
    vector<ll>lf (k+1,sum);

    int a = k,b = 1;
    
    for(int i=1;i<k+1;i++){
        lf[i] = lf[i-1];
        lf[i] -= op[i-1] * a;
        a--;
    }

    sum = 0;
    for(int i=0;i<k;i++){
        sum += b * op[i];
        b++;
    }
    vector<ll>rg (k+1,sum);
    b=k;
    for(int i=k-1;i > -1;i--){
        rg[i] = rg[i+1];
        rg[i] -= op[i] * b;
        b--;
    }
    
    ll ans = (1LL<<60);
    for(int i=0;i<k+1;i++){
        ans = min(ans,lf[i] + rg[i]);
    }

    cout << ans <<endl;
}

E - GCD of Subset

考察

各数字ごとに約数を列挙しておいて、約数の登場回数をメモしておけばAの約数のうちK回以上登場しているものを出力すればOK。

なんだが、約数列挙が時間かかりすぎでTLE。高速に出来る方法はないかと模索するもうまくいかず。結局大幅な時間ロス。

完全なる取捨選択ミス。

結果

ABCD　4完　87:04

順位　4879位
パフォーマンス　709

感想

入水後1発目に茶パフォですか...
完全にやらかしてしまった。

とりあえず水パフォの問題をしっかりと復習しなければ...