ABC374振り返り

A - Takahashi san 2(diff11)

https://atcoder.jp/contests/abc374/tasks/abc374_a
後ろ3文字をみて"san"になっていたらYes,なっていないならNoを出力する
提出コード

//略
int main(){
    string s;
    cin >> s;
    int n = s.size();
    bool judge = true;
    if(s[n-1] != 'n')judge = false;
    if(s[n-2] != 'a')judge = false;
    if(s[n-3] != 's')judge = false;
    if(judge)Yes;
    else No;
    return 0;
}

B - Unvarnished Report(diff28)

https://atcoder.jp/contests/abc374/tasks/abc374_b
$S == T$のとき、$|S| != |T|$のとき、そうでない時の処理を考える
まず$S == T$のときは問題文に書かれているように0を出力

$|S| != |T|$のときは0から$min(|S|,|T|)$までの範囲に$S_i$ $!=$ $T_i$の場所があればi+1を出力。これ忘れてて1ペナした...
もしそこまで見て$S_i != T_i$ となるiがなければ$min(|S|,|T|)+1$を出力する

そうでない時は、0から$|S|$までで$S_i!=T_i$となるi+1を出力する

提出コード　もっと綺麗に実装できそう

//略
int main(){
    string s,t;
    cin >> s >> t;
    if(s == t)cout << 0 << endl;
    else if(s.size() != t.size()){
        int id = -1;
        int size = min((int)s.size(),(int)t.size());
        for(int i = 0;i < size;i++){
            if(s[i] != t[i]){
                id = i;
                break;
            }
        }
        if(id == -1){
            cout << min((int)s.size(),(int)t.size())+1 << endl;;

        }
        else cout << id+1 << endl;
        return 0;
    }
    else{
        int id = 0;
        for(int i = 0;i < s.size();i++){
            if(s[i] != t[i]){
                id = i;
                break;
            }
        }
        cout << id+1 << endl;
        return 0;
    }

}

C - Separated Lunch(diff226)

https://atcoder.jp/contests/abc374/tasks/abc374_c
この制約はbit全探索
提出コード

int main(){
    int n;
    cin >> n;
    vector<int> k(n);
    ll sum = 0;
    rep(i,n) {
        cin >> k[i];
        sum += k[i];
    }
    ll ans = INF;
    for(int i = 0;i < (1<<n);i++){
        ll suma = 0;
        for(int j = 0;j < n;j++){
            if(i & (1<<j)){
                suma += k[j];
            }
        }
        ll sumb = sum-suma;
        ll cnt = max(suma,sumb);
        ans = min(ans,cnt);
    }
    cout << ans << endl;
    return 0;
}

D - Laser Marking(diff694)

https://atcoder.jp/contests/abc374/tasks/abc374_d
制約が$N <= 6$なので、計算量は気にせず全探索できそう
答えの最小値を求める上で全探索したいのは、レーザー照射する線分の順番と左端と右端どちらから照射を始めるからなので、前者を順列全探索、後者をbit全探索を用いて全探索することで答えを求められそう。計算量は$O(N!2^N)$
提出コード

//略
int main(){
    int n;
    double S,T;
    cin >> n >> S >> T;
    vector<int> a(n),b(n),c(n),d(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i] >> b[i] >> c[i] >> d[i];
    }
    double ans = 1e18;
    vector<int> p(n);
    for (int i = 0; i < n; i++) {
        p[i] = i;
    }
    do {
        for (int bit = 0;bit < (1<< n);bit++) {
            double cnt = 0;
            int ni = 0,nj = 0;
            for (int i = 0;i < n;i++) {
                int nexi, nexj, nexxi, nexxj;
                if (bit & (1 << i)) {
                    nexi = a[p[i]];
                    nexj = b[p[i]];
                    nexxi = c[p[i]];
                    nexxj = d[p[i]];
                } else {
                    nexi = c[p[i]];
                    nexj = d[p[i]];
                    nexxi = a[p[i]];
                    nexxj = b[p[i]];
                }
                int di = abs(ni - nexi), dj = abs(nj - nexj);
                cnt += sqrt(di*di+dj*dj)/S;
                di = abs(nexi - nexxi), dj = abs(nexj - nexxj);
                cnt += sqrt(di*di+dj*dj)/T;
                ni = nexxi;
                nj = nexxj;
            }
            ans = min(ans,cnt);
        }
    } while(next_permutation(p.begin(),p.end()));
    
    
    
    cout << fixed << setprecision(10) << ans << endl;
    return 0;
}

感想

久々に緑パフォ出せて嬉しい。久々のbit全探索と順列全探索だったが、ちゃんと実装できて精進の成果が出てきているなと思った。ただBのペナやDにそこそこ時間がかかってしまい大勝利のチャンスを逃してしまったのが悔しい。いつものD問題は今回より難しいので、精進して早解き４完を安定させて入緑したい
https://atcoder.jp/users/tagokoro/history/share/abc374