2020-09-12

WUPC2020

問題集

https://onlinejudge.u-aizu.ac.jp/beta/room.html#WUPC2020/info

解説

https://drive.google.com/drive/folders/16n_1q3evzq2sUJtAdjBT7OnxNW-UpQx4

その他

解いておきたい

2020-09-12

D. Petya and Array ～座標圧縮してBITで数える～

1800 ライブラリ

Quiz
- https://codeforces.com/contest/1042/problem/D
AC
- https://codeforces.com/contest/1042/submission/92543146
解法
- editorialの通り、式変形して、leftを固定して条件を満たすrightを数える
- BITを用いて数え上げるために座標圧縮を使う（累積和を座標圧縮してBITに登録する）
- leftを1進める前に、今回のleftの分をBITから登録解除する

座標圧縮のはいつもの (table ver)

// 座標圧縮
// 変換テーブルを返す
VI make_compress_table(vector<ll>& A){  
  // 変換表
  auto B = A;
  sort(ALL(B));
  auto it = unique(ALL(B));
  B.erase(it, B.end());
  return B;
}
ll compress_by_table(VI& T, ll v){
  return lower_bound(ALL(T), v) - T.begin();
}

書き換えver

// 座標圧縮
// Aをそのまま書き換えるver
void compress(VI& A){  
  ll N = A.size();
  auto B = A;
  sort(ALL(B));
  
  auto it = unique(ALL(B));
  B.erase(it, B.end());
 
  rep(i,N){
    A[i] = lower_bound(ALL(B), A[i]) - B.begin();
  }
}

code

struct AccSum{
    vector<ll> Ac;
    ll L;
    AccSum(){}
    AccSum(vector<ll> &A){
        L = A.size();
        Ac.resize(L+1);
        FOR(i, 0, L){
            Ac[i+1] = Ac[i] + A[i];
        }
    }
    // sum of [a, b]
    ll sum(ll a, ll b){
        if(a<0) return -1;
        if(b>L-1) return -1;
        return Ac[b+1] - Ac[a];
    }
};

// できること
// 一点追加
// 範囲和
// ei1333's BIT
struct BIT {
  VI data;

  BIT(ll sz) {
    data.assign(++sz, 0);
  }

  ll sum(ll k) {
    ll ret = 0;
    for(++k; k > 0; k -= k & -k) ret += data[k];
    return (ret);
  }

  // [i, j]
  ll range_sum(ll i, ll j){
    if(i==0){
      return sum(j);
    }else{
      return sum(j) - sum(i-1);    
    }
  }

  void add(ll k, ll x) {
    for(++k; k < SZ(data); k += k & -k) data[k] += x;
  }
};

// 座標圧縮
// 変換テーブルを返す
VI make_compress_table(vector<ll>& A){  
  // 変換表
  auto B = A;
  sort(ALL(B));
  auto it = unique(ALL(B));
  B.erase(it, B.end());
  debug(B);
  return B;
}
ll compress_by_table(VI& T, ll v){
  return lower_bound(ALL(T), v) - T.begin();
}

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

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

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

    AccSum Acc(A);

    BIT bit(410000);

    // compress
    VI V;
    rep(i,N){
      ll v = Acc.sum(0, i);
      V.push_back(v);
      V.push_back(v+T);
    }

    auto tbl = make_compress_table(V);

    // 累積和をBITに登録
    rep(i,N){
      ll v = Acc.sum(0,i);
      ll idx = compress_by_table(tbl, v);
      bit.add(idx, 1);
    }

    ll ans=0;
    rep(l, N){
      ll v = T;
      if(l!=0){
        v += Acc.sum(0,l-1);
      }
      ll limit = compress_by_table(tbl, v);
      
      if(limit>0){
        ans += bit.sum(limit-1);
      }
      ll idx = compress_by_table(tbl, Acc.sum(0,l));
      bit.add(idx, -1); // 登録から消す
    }
    
    p(ans);
   
    return 0;
}

2020-09-08

L. Lexicography

1800

Quiz
- https://codeforces.com/problemset/problem/1267/L
AC
- https://codeforces.com/contest/1267/submission/92214492
問題理解
- 部分文字列で切り取るわけではなく、与えられる文字列sの文字を好きな順番で使っていいことに注意
- なのですべての文字列は辞書順にできる
- 作られた文字列n個のうち、k番目の文字列を辞書順最小にせよ
解説
- editorialの補足。t (index) というは文字列内のindexではなく、k番目の文字列と今の所一致している文字列の最小位置 (t番目) (下図参照)

f:id:peroon:20200908223145p:plain

code (editorialに合わせています)

int main(){
    // input
    ll n,l,k;cin>>n>>l>>k;
    k--;
    string s;cin>>s;

    // character count
    VI C(26);
    for(char c : s){
      ll v = c-'a';
      C[v]++;
    }

    VS S(n); // n本の文字列
    ll t = 0; // same prefix index
    
    // phase 1
    ll idx=0;
    while(S[k].size()<l){
      if(C[idx]==0){
        idx++;
        continue;
      }
      ll Cp = C[idx];
      char c = 'a'+idx;
      if(Cp>k-t){
        // enough
        FOR(i,t,k+1) S[i] += c;
        C[idx] -= k-t+1;
      }
      else{
        FOR(i,t,t+Cp) S[i] += c;
        t += Cp;
        C[idx] = 0;
      }
    }

    // phase 2
    idx=0;
    rep(i,n){
      if(S[i].size()==l) continue;
      
      while(S[i].size()<l){
        while(C[idx]==0)idx++;
        char c = 'a'+idx;
        S[i] += c;
        C[idx]--;
        if(C[idx]==0)idx++;
      }
    }

    sort(ALL(S));
    for(string s : S){
      p(s);
    }

    return 0;
}

2020-09-08

B. Beingawesomeism

1800

Quiz
- https://codeforces.com/contest/1281/problem/D
AC
- https://codeforces.com/contest/1280/submission/92201582
解説
- editorialの通り、ひたすら場合分け。考察難易度は低い
学び
- より小さい答えになるものをコードの前方に書く
- 長くなりがちだし、提出後にWAになりやすく、はまりやすい。コンテスト中ははまる危険度が高い

bool is_A_line(string& s){
  for(char c : s){
    if(c!='A') return false;
  }
  return true;
}

// for codeforces
void solve(){
  // input
  ll R,C;cin>>R>>C;
  VS S(R);
  rep(i,R)cin>>S[i];

  // impossible easy case
  {
    ll p_cnt=0;
    for(string s : S){
      for(char c : s){
        if(c=='P') p_cnt++;
      }
    }
    if(p_cnt==R*C){
      p("MORTAL"); return;
    }
    ll a_cnt = R*C - p_cnt;
    if(a_cnt==R*C){
      p(0); return; // 忘れがち
    }
  }

  // P-exist range
  ll min_x = inf;
  ll min_y = inf;
  ll max_x = -1;
  ll max_y = -1;
  rep(i,R){
    rep(j,C){
      char c = S[i][j];
      if(c=='P'){
        chmin(min_y,i);
        chmax(max_y,i);
        chmin(min_x,j);
        chmax(max_x,j);
      }
    }
  }

  // about x
  rep(i,R){
    string s = S[i];
    ll len = max_x - min_x + 1;
    string sub = s.substr(min_x, len);
    if(min_y<=i && i<=max_y) continue; // 間だとダメ
    if(is_A_line(sub)){
      p(1); return;
    }
  }
  // about y
  rep(x,C){
    stringstream ss;
    rep(i,R) ss<<S[i][x];
    string s = ss.str();
    ll len = max_y - min_y + 1;
    string sub = s.substr(min_y, len);
    if(min_x<=x && x<=max_x) continue; // 間だとダメ
    if(is_A_line(sub)){
      p(1); return;
    }
  }

  // 一撃で終わらなかった場合のコーナー
  {
    string s = S[0];
    if(s[0]=='A' or s.back()=='A'){
      p(2); return;
    }
    s = S[R-1];
    if(s[0]=='A' or s.back()=='A'){
      p(2); return;
    }
  }

  // 以降、コーナーは全てP
  // P-exist rangeをつつみこむAラインがあれば2回で済む
  // about x
  rep(i,R){
    string s = S[i];
    ll len = max_x - min_x + 1;
    string sub = s.substr(min_x, len);
    if(is_A_line(sub)){
      p(2); return;
    }
  }
  // about y
  rep(x,C){
    stringstream ss;
    rep(i,R) ss<<S[i][x];
    string s = ss.str();
    ll len = max_y - min_y + 1;
    string sub = s.substr(min_y, len);
    if(is_A_line(sub)){
      p(2); return;
    }
  }

  // はじっこにAがあるなら3回で可能
  if(S[0].find("A")!=string::npos){
    p(3); return;
  }
  if(S[R-1].find("A")!=string::npos){
    p(3); return;
  }
  rep(i,R){
    if(S[i][0]=='A'){
      p(3);return;
    }
    if(S[i][C-1]=='A'){
      p(3);return;
    }
  }

  p(4);
}

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

    // input
    ll N; 
    cin>>N;
    
    while(N--)solve();
    
    return 0;
}

2020-09-07

オイラーのトーシェント関数 (φ, ファイ, phi)

1800 ライブラリ

verified

// 借り物
// https://ei1333.github.io/luzhiled/snippets/math/euler-phi.html
int64_t euler_phi(int64_t n) {
  int64_t ret = n;
  for(int64_t i = 2; i * i <= n; i++) {
    if(n % i == 0) {
      ret -= ret / i;
      while(n % i == 0) n /= i;
    }
  }
  if(n > 1) ret -= ret / n;
  return ret;
}

// 1 to n までのnと互いに素である個数
ll eulers_totient_function(ll n){
  ll n_original = n;
  // 10^10まで可能
  VI P;
  for(ll i=2; i*i<=n; i++){
    if(n%i==0){
      P.push_back(i);
    }
    while(n%i==0) n/=i;
  }
  P.push_back(n);
  // 素因数を使って実際に求める
  n = n_original;
  for(ll p : P){
    if(p==1) continue; // 盲点
    n -= n/p;
  }
  return n;
}

void solve(){
  ll a,m;cin>>a>>m;
  ll g = gcd(a,m);
  ll n = m/g;

  ll ans = eulers_totient_function(n);
  // ll ans = euler_phi(n);

  p(ans);
}

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

    // input
    ll N; 
    cin>>N;
    
    while(N--)solve();
    
    return 0;
}