AtCoder Beginner Contest 374

A - Takahashi san 2

O(1)

substr(N-3, 3) == "san"

C++

#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    string S;
    cin >> S;
    int N = S.size();
    if(S.substr(N-3, 3) == "san") cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
} 

B - Unvarnished Report

O(N)
文字列を比較して、最初に異なっていた文字、または長さのindexを出力します。
シミュレートしましょう。

C++

#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

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

    if(s == t){
        cout << 0 << endl;
        return 0;
    }

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

    return 0;
} 

C - Separated Lunch

O(2^N)
Kiをaとbのグループに任意の要素だけ振り分けます。
0と1のグループに分ける便利な探索はbit全探索です。

「同時に昼休みをとる最大人数としてあり得る最小の値を求めてください。」
全てのパターンでaとbを比較して大きい値を求め、その最小値を出力します。

C++

#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int N;
    cin >> N;
    vector<int> K(N);
    rep(i, N) cin >> K[i];

    int ans = 1e9;
    for(int bit=0; bit<(1<<N); bit++){
        int a = 0;
        int b = 0;
        for(int i=0; i<N; i++){
            if((bit >> i)&1) a += K[i];
            else b += K[i];
        }
        ans = min(ans, max(a, b));
    }
    cout << ans << endl;

    return 0;
} 

D - Laser Marking

O(2^N*N!)
(0, 0)から開始して、N個の線分を書きます。

まず、レーザ照射位置を線分の端点のうちどちらか1つに移動させる。
どちらの端点から描画を始めてもよい。

線を引く始点は、頂点ab,cdのどちらか決まっていないのでbit全探索します。

高橋君はこの印字機でN本の線分を印字したいです。
そのうちi本目の線分は、座標(Ai, Bi)と座標(Ci,Di)を結びます。
なお、複数の線分が重なっていることがありますが、全ての線分についてその都度重なっている部分を印字する必要があります。

N個の線分の順番は決まっていないので順列全探索をします。
時間の計算式は、

時間=距離/速さ

速さは、

レーザを照射していない時、レーザ照射位置は1秒あたり速度Sで任意の方向に移動できる。
レーザを照射している時、レーザ照射位置は1秒あたり速度Tで印字中の線分に沿って移動できる。

距離は、

double dist(pair<double, double> a, pair<double, double> b){
    return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}

実装に必要な考察ができました。

C++

#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

double dist(pair<double, double> a, pair<double, double> b){
    return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}

int main() {
    int N;
    double S, T;
    cin >> N >> S >> T;
    vector<pair<pair<double, double>, pair<double, double>>> abcd(N);
    rep(i, N){
        double a, b, c, d;
        cin >> a >> b >> c >> d;
        abcd[i].first = {a, b};
        abcd[i].second = {c, d};
    }

    double ans = 1e9;
    for(int bit=0; bit<(1<<N); bit++){
        vector<pair<pair<double, double>, pair<double, double>>> temp(N);
        for(int i=0; i<N; i++){
            if((bit >> i)&1){
                temp[i].first = abcd[i].second;
                temp[i].second = abcd[i].first;
            }else{
                temp[i].first = abcd[i].first;
                temp[i].second = abcd[i].second;
            }
        }

        sort(temp.begin(), temp.end());

        do{
            double time = 0;
            pair<double, double> s = {0, 0};
            pair<double, double> t = temp[0].first;

            if(temp[0].first != s){
                time += dist(temp[0].first, {0, 0}) / S;
            }

            for(int i=0; i<N; i++){
                time += dist(temp[i].first, temp[i].second) / T;
                if(i<N-1 && temp[i].second != temp[i+1].first){
                    time += dist(temp[i].second, temp[i+1].first) / S;
                }
            }

            ans = min(time, ans);
        }while(next_permutation(temp.begin(), temp.end()));
    }
    cout << fixed_setprecision(6) << ans << endl;

    return 0;
}