2021-10-10

AOJ 3117 K Average Ranges

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3117
誰も解説を書いていなかったので、方針だけ
入力Aの累積和をBとする

(i, jが右辺と左辺に分離できた)
条件を満たすi,jの組を数えるには、座標圧縮してBITを使うなどすればいい

2021-10-09

fake nodeと二部グラフ 2部グラフ

Quiz
- D The Number of Imposters
- https://codeforces.com/contest/1594/problem/D
感想
- 有向グラフの問題に見えるが、よく考えると無向グラフ
- imposterと言っているなら、頂点x, yは違う色
- crewmateと言っているなら、頂点x, yは同じ色★
- ★について、色はまだ不明だけど同じ色であることは確定しているときに使えるのがfake node。x---fake_node---yのように繋げる
- editorialに書いていて、初めて知った
- 後は（連結成分ごとに）2部グラフであることを確認して、多い色の方をimposterとして数えればいい
editorial
- https://codeforces.com/blog/entry/95525
元ネタ：among us

f:id:peroon:20211009090304j:plain

2021-09-29

RUPC2018 C-一致 mapの一致判定は速い!?

Quiz
- https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp18Day1/problems/C
AC
- https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp18Day1/5920491
解法
- 左からK個を入れたmap
- 右からK個を入れたmap
- をそれぞれ作って==で比較。愚直解として書いてTLEだろうなと思ったら通ってしまった。mapの比較が速い？

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N;
    cin>>N;

    VI A(N);
    rep(i, N){
      cin >> A[i];
    }

    map<ll,ll> left,right;

    VI Ans;
    rep(i,N){
      {
        ll a = A[i];
        left[a]++;
      }
      {
        ll a = A[N-1-i];
        right[a]++;
      }
      if(left==right){
        Ans.push_back(i+1);
      }
    }
    print_vector(Ans);
    
    return 0;
}