トヨタ自動車プログラミングコンテスト2024#9（AtCoder Beginner Contest 370）に参加しました。

使用しているテンプレート

A - Raise Both Hands

問題文の通りに、

  • 左手のみ上げているときはYes
  • 右手のみ上げているときはNo
  • それ以外ならInvalid

を出力すればよい。

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int L, R; cin >> L >> R;
    if((L and R) or (!L and !R)){
        cout << "Invalid\n";
    }else if(L){
        cout << "Yes\n";
    }else{
        cout << "No\n";
    }
}

B - Binary Alchemy

入力が難しいが、現在の元素の番号をansとして持っておいて、問題文の通りにシミュレーションすればよい。

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N; cin >> N;
    vector<vector<int>> A(N + 1, vector<int> (N + 1, -1));
    rrep(i, 1, N + 1){
        rrep(j, 1, i + 1){
            cin >> A[i][j];
        }
    }

    int ans = 1;
    rrep(x, 1, N + 1){
        if(ans >= x){
            ans = A[ans][x];
        }else{
            ans = A[x][ans];
        }
    }

    cout << ans << "\n";
}

C - Word Ladder

$\lvert S \rvert, \lvert T\rvert \leq 100 $ なので、書き換える文字を全探索する $O(N^3)$ 解法でも十分間に合うが、本番では気づかずに考察した。

  • $i=1, 2, \cdots, N $ に対して順に、$S_i > T_i$ なら $i$ 文字目の操作を行う
  • $i = N, N - 1, \cdots, 1$ に対して順に、$S_i < T_i$ なら $i$ 文字目の操作を行う

という $2$ つの操作を順に行うことが最適である。$O(N^2)$ で解くことができる。

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string S, T; cin >> S >> T;
    int N = S.size();

    vector<string> ans;

    rep(i, N){
        if(S[i] > T[i]){
            S[i] = T[i];
            ans.push_back(S);
        }
    }

    rep(i, N){
        if(S[N - 1 - i] < T[N - 1 - i]){
            S[N - 1 - i] = T[N - 1 - i];
            ans.push_back(S);
        }
    }

    cout << ans.size() << "\n";
    for(string s: ans){
        cout << s << "\n";
    }
}

D - Cross Explosion

本番では、$H\times W \leq 4 \times 10^5$ という制約を $H, W \leq 4 \times 10^5$ と読み間違えいて解くことができなかった。
各行と列においてsetを用意し、まだ壁が壊されていない座標を持っておけば、二分探索によって壊す壁の座標を求められる。 これによって、$O(\max(HW, Q\log(\max(H, W)))) $で解くことができる。

コンテスト結果

コメント

問題をよく読みます。