おはやし日記

特にテーマ無しの日記。

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;
}

図解

2i 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

2i
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の数が思い通りになる

各A[i]の各ビットの気持ちになると何となくわかるかと思います。

まとめ

謎のひらめきが発生し1時間で5完できました!やったね!

でもそんなに順位良くはないんかな…………

DであからさまなTLEをヤケクソで投げたのが悔やまれる

プライバシーポリシー ・お問い合わせはこちら