接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。

トップ > AtCoderBeginnerContest171 > AtCoder Beginner Contest 171（ABC171）

AtCoder Beginner Contest 171（ABC171）

AtCoderBeginnerContest171 AtCoderBeginnerContest ABC171 ABC

atcoder.jp

冷えたけど復習してたら楽しくなっちゃった（？）

A - αlphabet

'a'~'z'もしくは'A'~'Z'はASCIIコードでは連続になっているので小文字もしくは大文字かどうかを判定できる
提出コード

void solve(){
    char c;
    cin >> c;
    if('A' <= c && c <= 'Z') cout << "A" << endl;
    else cout << "a" << endl;
}

B - Mix Juice

昇順にソートし、小さい方からK個の合計を出力
提出コード

void solve(){
    int N, K;
    cin >> N >> K;
    vector<int> p(N);
    REP(i,N) cin >> p[i];
    sort(p.begin(), p.end());
    int sum = 0;
    REP(i,K) sum += p[i];
    cout << sum << endl;
}

C - One Quadrillion and One Dalmatians

難しい
26進数っぽいものを求めて出力すればいい
1文字目を考えると'a'が1に対応しているので0-indexedに戻してあげる
次に桁上りした場合、その桁が1から始まるがこの問題だと0(='a')にならないといけない
そのため、各桁ごとに予め1引いた状態で26進数を求めればいい
提出コード

void solve(){
    ll N;
    cin >> N;
    string ans = "";
    while(N > 0){
        N--;
        ans += char('a' + N % 26);
        N /= 26;
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
}

D - Replacing

一瞬区間クエリだと思って激ムズでは？となった
数列のある要素を全部書き換えるようなクエリなので、現時点での総和と各値が何個あるかをvectorなどで管理する
そうすると、数列中のB_iをすべてC_iに変えたときの総和はその都度差分を考えることで求めることが出来る
提出コード

void solve(){
    int N;
    cin >> N;
    vector<ll> cnt(101010);
    ll sum = 0;
    REP(i,N){
        int A;
        cin >> A;
        cnt[A]++;
        sum += A;
    }
    int Q;
    cin >> Q;
    REP(i,Q){
        int B, C;
        cin >> B >> C;
        ll tmp_cnt = cnt[B];
        ll tmp_sum = tmp_cnt * B;
        cnt[B] = 0;
        cnt[C] += tmp_cnt;
        sum -= tmp_sum;
        sum += tmp_cnt * C;
        cout << sum << endl;
    }
}

E - Red Scarf

出力する数列をB_0, B_1, ... , B_{N-1}とする
この時
A_0 = B_1 xor B_2 xor ... xor B_{N-1}
A_1 = B_0 xor B_2 xor ... xor B_{N-1} ... のようになる
B_1 xor B_1 = 0のように同じもののxorは0になるので1個だけ残るようにxor出来ないかを考えてみる
そうすると、B_0 = A_1 xor A_2 xor ... xor A_{N-1}のように自分を除いたもの以外のxorの合計がB_iとなる
これは、左右からの累積xorのようなものを事前に計算しておくと出来る
全体のxorからA_iのxor取るのでも同じ様になるんだけど、その発想出てこなかったな
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> a(N);
    REP(i,N) cin >> a[i];
    vector<int> left(N), right(N);
    left[0] = a[0], right[N-1] = a[N-1];
    for(int i=1;i<N;i++) left[i] = left[i-1] ^ a[i];
    for(int i=N-2;i>=0;i--) right[i] = right[i+1] ^ a[i];
    REP(i,N){
        if(i == 0) cout << right[i+1] << " ";
        else if(i == N-1) cout << left[i-1] << " ";
        else cout << (left[i-1] ^ right[i+1]) << " ";
    }
    cout << endl;
}

F - Strivore

教えてもらってなんとか理解できた（教えてくれた人ありがとう）
まず、適当に操作を行うと重複が出来てしまうので、操作と結果が1対1になるようにしたい
今回の場合、文字列Sに操作を行って出来たときの文字列をTとする
Tの先頭から貪欲に部分文字列を選んでSにするとき、その選んだindexが必ず辞書順最小となるように操作を行って文字列Tを作ることを考える
そうすると例えば、S="abc"とした時
'a'の左側には'a'以外の25文字、'a'と'b'の間は'b'以外の25文字、'b'と'c'の間は'c'以外の25文字、'c'より右側は好きな26文字すべておける
S_Nより左側にi文字、右側にK-i文字置くかを考え、0 \leq i \leq Kの場合を加算する
iを固定したときは、左側はそれぞれ25^i通りで、 S_1 〜 S_{N-1}をN - 1 + i個の中からどこに置くかで _{N - 1 + i} C _{N - 1}通り、右側は26^{K-i}通りあるので全体で
25^i \times _{N - 1 + i} C _{N - 1} \times 26^{K - i}通りとなる
求めた答えは、実は文字列Sの各文字に依存しないことがわかる、これすごい
提出コード

using mint = Fp<MOD>;
BiCoef<mint> bc(2020202);

void solve(){
    int K;
    string S;
    cin >> K >> S;
    int N = S.size();
    mint ans = 0;
    for(int i=0;i<=K;i++){
        ans +=  modpow(mint(25), i) * bc.com(N-1+i, N-1) * modpow(mint(26), K-i);
    }
    cout << ans << endl;
}