AtCoder Beginner Contest 257

A - A to Z String 2

O(1)
計算式(X-1)/Nを思いつくか。
またはシミュレートする。

C++

#include <bits/stdc++.h>
string S = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

int main() {
    int N, X;
    cin >> N >> X;
    cout << S[(X-1)/N] << endl;
    return 0;
} 

B - 1D Pawn

O(Q)
シミュレートする。

C++

#include <bits/stdc++.h>

int main() {
    int N, K, Q;
    cin >> N >> K >> Q;
    vector<int> A(K+1), L(Q);
    for(int i=1;i<=K; i++) cin >> A[i];
    for(auto &l:L) cin >> l;

    for(auto &l:L){
        if(A[l] == N) continue;
        else if(l == K) A[l]++;
        else if(A[l]+1 < A[l+1]) A[l]++;
    }

    for(int i=1; i<=K; i++){
        cout << A[i];
        if(i<K) cout << ' ';
        else cout << endl;
    }

    return 0;
}  

C - Robot Takahashi

O(N^2)はTLEになる。
そこでO(NlogN*2)にすることにした。

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)

int N;
string S;
int W[200000+1];
vector<int> child, parent;

int f(int X){
    int t1=0, t2=0;
    auto itr1 = lower_bound(child.begin(), child.end(), X);
    if(itr1 != child.end()) t1 = itr1 - child.begin();
    else t1 = child.size();
    auto itr2 = lower_bound(parent.begin(), parent.end(), X);
    if(itr2 != parent.end()) t2 += parent.end() - itr2;
    return t1+t2;
}

int main() {
    cin >> N >> S;
    rep(i, N) cin >> W[i];

    rep(i, N){
        if(S[i] == '0') child.push_back(W[i]);
        else parent.push_back(W[i]);
    }
    sort(child.begin(), child.end());
    sort(parent.begin(), parent.end());

    int ans=0;
    rep(i, N){
        if(S[i] == '0') ans = max(ans, f(W[i]+1));
        else ans = max(ans, f(W[i]));
    }
    cout << ans << endl;

    return 0;
}