A - Reachable Towns

f:id:peroon:20200921040033p:plain (画像、同じYが存在するのは見逃してください><)

#include <atcoder/dsu>
using namespace atcoder; // 忘れがち

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

    // input
    ll N; 
    cin>>N;

    auto uf = dsu(N);

    VI X(N);
    VI Y(N);
    VI Ix(N);
    VI Iy(N);

    rep(i,N){
      ll x,y;cin>>x>>y;
      x--;y--;
      
      X[i]=x;
      Y[i]=y;
      Ix[x]=i;
      Iy[y]=i;
    }
    
    vector<PII> V;
    rep(i,N){
      V.push_back({X[i],Y[i]});
    }
    sort(ALL(V));

    set<ll> se;
    rep(i,N){
      ll x=V[i].first;
      ll y=V[i].second;

      if(se.size()==0){
        se.insert(y);
        continue;
      }

      if(*se.begin()>y){
        se.insert(y);
        continue;
      }

      VI temp;
      // yより小さいものと統合
      for(ll a : se){
        if(a<y){
          temp.push_back(a);
        }else{
          break;
        }
      }
      // 一番小さいyをsetに入れる
      ll mi = y;
      chmin(mi, MIN(temp));
      se.insert(mi);
      // unite
      ll my_idx = Iy[y];
      for(ll v : temp){
        ll idx = Iy[v];
        uf.merge(my_idx, idx);
      }
    }

    rep(i,N){
      ll sz = uf.size(i);
      p(sz);
    }
    
    return 0;
}

E - Sequence Sum ~数列のサイクル検出(位置と長さ)~

f:id:peroon:20200920004710p:plain

code

// ※サイクル!=ループ

// サイクルを見つけます
// 入力:サイクルが存在するであろう数列
// 出力:サイクルの開始index, サイクルの長さ
PII find_cycle(VI& A){
  ll N = SZ(A);
  map<ll,VI> mp;
  rep(i,N){
    ll a = A[i];
    mp[a].push_back(i);
    if(mp[a].size()>1){
      // found cycle
      ll len = mp[a][1] - mp[a][0];
      ll cycle_start_index = mp[a][0];
      return {cycle_start_index, len};
    }
  }
  return {-1,-1};
}

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

  // input
  ll N,X,M;
  cin>>N>>X>>M;

  ll a = X;
  VI A;
  rep(i,200200){
    A.push_back(a);
    a = (a*a)%M;
  }
  auto pa = find_cycle(A);
  ll cycle_start_index = pa.first;
  ll cycle_len = pa.second;
  ll cycle_sum = 0;
  FOR(i,cycle_start_index, cycle_start_index+cycle_len){
    cycle_sum += A[i];
  }
  
  ll sum=0;
  // サイクルに入る前
  rep(i,cycle_start_index){
    sum += A[i];
  }

  ll rest = N-cycle_start_index;
  ll num = rest / cycle_len; // サイクル数
  sum += num * cycle_sum;

  // サイクルのあまり
  ll r = rest%cycle_len;
  FOR(i,cycle_start_index, cycle_start_index+r){
    sum += A[i];
  }
  p(sum);
  return 0;
}

B: P進XOR

using LL = __int128_t;

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

    // input
    ll N,P;cin>>N>>P;

    ll n; // 切り捨てるブロック数
    ll len; // 切り捨てる長さ
    VI A(50);
    if(P==2){
      n = (N+1)/4; 
      len = 4*n;
    }
    else{
      n = (N+1)/P; // 切り取り
      len = P*n;
    }

    // 余った部分は具体的にXORを考える
    FOR(i,len,N+1){
      ll v = i;
      // vをP進数で表して足す
      rep(j,50){
        A[j] += v%P;
        A[j] %= P;
        v /= P;
        if(v==0) break;
      }
    }
    ll ans = 0;
    LL power=1; // overflow注意
    rep(i,50){
      ans += A[i] * power;
      power *= P;
      if(power>inf) break;
    }
    p(ans);
    
    return 0;
}

ACPC2020Day1, Day2, Day3

Day 1 (農工大Set)

Day2 (Aizu Set)

Day3 (Hokudai Set)

Range Update Query (by ACL) 範囲更新