AtCoder Beginner Contest 279（ABC279）

atcoder.jp

Bondo416さんのトヨタシステムズプログラミングコンテスト2022(AtCoder Beginner Contest 279)での成績：548位
パフォーマンス：1706相当
レーティング：1554→1570 (+16) :)#AtCoder #トヨタシステムズプログラミングコンテスト2022(ABC279) https://t.co/xnWL21LNGv

— ボンド@競プロ (@bond_cmprog) November 26, 2022

A - wwwvvvvvv

v のとき $ 1 $ 、w のとき $ 2 $ 加算し、その総和が答え

提出コード

void solve() {
    int res = 0;
    string s;
    cin >> s;
    for (char c : s) {
        if (c == 'v') res++;
        else if (c == 'w') res += 2;
    }
    cout << res << endl;
}

B - LOOKUP

$ S $ のなかに $ T $ が含まれるかどうかを愚直に調べる

提出コード

void solve() {
    string S, T;
    cin >> S >> T;
    bool ans = false;
    REP(i, (int)S.size() - (int)T.size() + 1) {
        bool ok = true;
        REP(j, T.size()) {
            if (S[i + j] != T[j]) ok = false;
        }
        ans |= ok;
    }
    cout << (ans ? "Yes" : "No") << endl;
}

C - RANDOM

$ S, T $ の行と列を入れ替え、ソートしたものが一致するかどうかを判定

提出コード

void solve() {
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    vector<string> T(H);
    REP(i, H) cin >> S[i];
    REP(i, H) cin >> T[i];
    vector<string> SS(W), TT(W);
    REP(j, W) REP(i, H) {
        SS[j] += S[i][j];
        TT[j] += T[i][j];
    }
    sort(ALL(SS));
    sort(ALL(TT));
    cout << (SS == TT ? "Yes" : "No") << endl;
}

D - Freefall

求めたい時刻 $ t $ は下に凸な関数になるので三分探索で $ g $ について求める
求めた $ g $ に対して余分に前後を探索してその最小値を出力する

提出コード

void solve() {
    ll A, B;
    cin >> A >> B;

    auto f = [&](long double g) -> long double { return (long double)A / sqrt(g) + B * max((long double)0, (g - 1)); };
    long double l = 0;
    long double r = ceil_div(A, B);
    dumps(l, r);
    REP(_, 100) {
        long double c1 = (l * 2 + r) / 3;
        long double c2 = (l + r * 2) / 3;
        if (f(c1) > f(c2)) l = c1;
        else r = c2;
    }
    long double ans = LINF;
    for (int i = -100; i <= 100; i++) {
        chmin(ans, f(max((long double)0, floor(l - i))));
    }
    printf("%.12Lf\n", ans);
}

E - Cheating Amidakuji

後ろからの操作の累積を求めておくと、各 $ index $ が最終的な操作でどこにいるかを求めることができる
よって前から順番に操作を行い、残りの差分は後ろからの操作を参照することで各質問に高速に答える事ができる

提出コード

void solve() {
    int N, M;
    cin >> N >> M;
    vector<int> A(M);
    int one_idx = 0;
    REP(i, M) {
        cin >> A[i];
        --A[i];
    }
    vector<int> B(N);
    vector<int> S(N);
    iota(ALL(B), 0);
    iota(ALL(S), 0);
    for (int i = M - 1; i >= 0; i--) {
        swap(S[A[i]], S[A[i] + 1]);
        dump(S);
    }
    dump(S);
    REP(i, M) {
        swap(S[A[i]], S[A[i] + 1]);
        cout << S[one_idx] + 1 << endl;
        swap(B[A[i]], B[A[i] + 1]);
        if (B[A[i]] == 0) one_idx = A[i];
        if (B[A[i] + 1] == 0) one_idx = A[i] + 1;
    }
}