AtCoder ABC171 反省会 [A,B,C,D,E完]

こんにちは。ABC171でした。

5完でした！！！

即席解説記事行きます

A

愚直な実装。

#include <bits/stdc++.h>
using namespace std;

int main(){
  char x;cin>>x;
  if('A'<=x && x<='Z')cout<<"A\n";
  else cout<<"a\n";
}

B

ソートして小さい方から $K$ 個取る。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(int)n; i++)
#define all(v) (v).begin(), (v).end()

int main(){
  int N,K;cin>>N>>K;
  vector<int> p(N);
  rep(i,N)cin>>p[i];

  sort(all(p));

  int ans = 0;
  rep(i,K){
    ans += p[i];
  }
  cout<<ans<<endl;
}

C

「26進法」のように実装。下の桁から順にvectorに突っ込んでいって、最後逆転させて出す。（追記：最初27進法って書いてましたが26進法ですね）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i=0; i<(int)n; i++)
#define all(v) (v).begin(), (v).end()

int main(){
  ll N;cin>>N;

  vector<char> ans;

  while(N>0){
    N--;
    ll c = N%26;
    N++;
    ans.push_back(c+'a');
    N -= c;
    N /= 26;
    if(N==0)break;
  }

  reverse(all(ans));

  for(char x: ans){
    cout<<x;
  }
  cout<<endl;
}

1始まりである $N$ を0始まりにして（N--;）26でのあまりを取る→アルファベットa-zに変換
$N$ を1始まりに戻す
$N$ から変換済みの端数を引いて桁を下げる

D

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i=0; i<(int)n; i++)

int main(){
  int N;cin>>N;
  ll ans = 0;
  map<ll,ll> A;
  rep(i,N){
    ll a;cin>>a;
    A[a]++;
    ans += a;
  }

  int Q;cin>>Q;
  while(Q--){

    ll b,c;cin>>b>>c;
    ll Ab = A[b];
    ll Ac = A[c];

    A[c] += Ab;
    A[b] = 0;

    ans -= Ab * b;
    ans += Ab * c;

    cout<<ans<<endl;

  }
}

数列にどの数字が何個あるかをmapで保持して、最初の総和ansを計算しておけば、各クエリごとに

$B$ の数だけansから $B$ を引く
増えた分（$B$ の数）だけansに $C$ を足す
$C$ の数を、$B$ の数だけ増やす
$B$ の数は0になる

とやれば高速に計算できます。

最初、Ab, Acをint型で持っていたためにWAだして、一回ansをいちいち算出するようにしてTLEを出し（それはそう）、プログラムとにらめっこしていたらAb * b;やAb * c;がオーバーフローしそうだなぁって思って ll に書き換えてAC。

E

発想としては、2進数にした時の桁ごとに

1の数が偶数→A[i]のその桁は反転させて出力
1の数が奇数→A[i]のその桁はそのまま出力

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(int)n; i++)

int main(){
  int N;cin>>N;
  int bits = 0;
  vector<int> A(N);

  rep(i,N){
    int x;cin>>x;
    A[i] = x;
    for(int c=0; c<32; c++){
      if(x & 1<<c){
        bits ^= 1<<c;
      }
    }
  }

  rep(i,N){
    cout<<(A[i]^bits)<<" ";
  }
  cout<<endl;
}

図解

2ⁱ	20	11	9	24
i=4	1	0	0	1
i=3	0	1	1	1
i=2	1	0	0	0
i=1	0	1	0	0
i=0	0	1	1	0

この時、出力の時のフィルターとなるbitsは

2ⁱ
i=4	0
i=3	1
i=2	1
i=1	1
i=0	0

です。1のところは反転、0のところはそのまま。すなわちA[i] XOR bitsを出力すれば良いということですね。

各ビットについて

全体で1の数が偶数のとき
- 1になっているA[i]目線だと自分以外に1が奇数個立っていて欲しい
  （実際奇数個）
- 0になっているA[i]目線だと自分以外に1が偶数個立っていて欲しい
  （実際偶数個）
  - 現状維持で出力すれば良い
全体で1の数が奇数のとき
- 1になっているA[i]目線だと自分以外に1が奇数個立っていて欲しい
  （実際は偶数個）
- 0になっているA[i]目線だと自分以外に1が偶数個立っていて欲しい
  （実際は奇数個）
  - 出力する全体を反転すると全体での1の数は奇数を保ったまま自分の持っているビットが反転する→自分以外の1の数が思い通りになる