CafeCoder Test 001

cafecoder.top

A - Compare

if文で判定
提出コード

void solve(){
    int A, B, C;
    cin >> A >> B >> C;
    if(A + B < C) cout << "Yes" << endl;
    else cout << "No" << endl;
}

B - minimum prise

を出力
提出コード

void solve(){
    ll A, B, C;
    cin >> A >> B >> C;
    B = B - B * C / 10.0;
    cout << min(A, B) << endl;
}

C - HELP!

かが1なら-1
の場合そのままでいい
の場合、間にを適当に追加すればいいので個数を+1する
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    int ans = 0;
    REP(i,N-1){
        if(A[i] == 1 or A[i+1] == 1){
            cout << -1 << endl;
            return;
        }
        if(gcd(A[i], A[i+1]) == 1) ans++;
    }
    cout << ans << endl;
}

D - Sqrt Simpilfy

素因数分解をする
各素因数の2の倍数分外に出してあげる
提出コード

void solve(){
    int N;
    cin >> N;
    auto res = prime_factorize(N);
    int x = 1, y = 1;
    for(auto [p, cnt] : res){
        dumps(p, cnt);
        x *= pow(p, cnt / 2);
        if(cnt & 1) y *= p;
    }
    cout << x;
    if(y != 1) cout << " " << y;
    cout << endl;
}

E - Strong String

ソートの比較関数にラムダ式を渡してあげればいい
文字数が同じ場合は辞書順で昇順に、文字数が異なれば小さい順にソートする
提出コード

void solve(){
    int N;
    cin >> N;
    vector<string> vs(N);
    REP(i,N) cin >> vs[i];
    sort(vs.begin(), vs.end(), [&](string s, string t){
        return ((int)s.size() == (int)t.size() ? s < t : (int)s.size() < (int)t.size());
    });
    REP(i,N) cout << vs[i] << endl;
}

F - UTBE

頭壊れた
j番目の玉がiにあるとき、それを石に変えたときの操作の最小とする
のとき玉は左端、のとき玉は右端にあるとする
操作2と操作3を行っても並び順は循環しているので相対的な位置関係は変わっていない
そのため、前の玉が右端もしくは左端にあるかどうかがわかれば今見ている玉を右端・左端に移動させるための操作回数がわかる
後は、dpで最小回数を求めればいい
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> idx(N);
    REP(i,N){
        int a;
        cin >> a;
        idx[--a] = i;
    }
    vector<vector<ll>> dp(2, vector<ll>(N, LINF));

    REP(i,N){
        if(i == 0){
            dp[0][i] = idx[i] + 1;
            dp[1][i] = N - idx[i];
        }
        else{
            int prevL = idx[i-1];
            int prevR = N - idx[i-1] - 1;
            dp[0][i] = min(dp[0][i-1] + (idx[i] - prevL + N) % N, dp[1][i-1] + (prevR + idx[i]) % N) + 1;
            dp[1][i] = min(dp[0][i-1] + N - ((idx[i] - prevL + N) % N), dp[1][i-1] + N - (prevR + idx[i]) % N);
        }
    }
    cout << min(dp[0][N-1], dp[1][N-1]) << endl;
}