PAST E - 順列

f:id:peroon:20201106103407p:plain

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

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

    // input
    ll N; 
    cin>>N;

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

    dsu uf(N);

    rep(i,N){
      uf.merge(i,A[i]);
    }

    VI Ans;
    rep(i,N){
      ll ans = uf.size(i);
      Ans.push_back(ans);
    }
    print_vector(Ans);
    
    return 0;
}

D. Extreme Subtraction 単調増加と単調減少に分離

1800 
string solve(){
  ll N;
  cin>>N;
  VI V(N);
  rep(i, N){
    cin >> V[i];
  }
  VI A(N); // decreasing
  VI B(N); // increasing
  A[0]=V[0];
  FOR(i,1,N){
    A[i] = min(A[i-1], V[i]-B[i-1]);
    B[i] = V[i]-A[i];
    if(B[i]<B[i-1]) return "NO";
    if(A[i]<0 or B[i]<0) return "NO";
  }
  return "YES";
}

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

    // input
    ll N; 
    cin>>N;

    while(N--){
      auto ans = solve();
      p(ans);
    }
    
    return 0;
}

memo image

f:id:peroon:20201105101827p:plain

1436B - Prime Square

900

f:id:peroon:20201028013842p:plain

void solve(){
  ll N;
  cin>>N;
  if(N==2){
    p("1 1");
    p("1 1");
    return;
  }
  VI A(N);
  rep(i,3)A[i]=1;
  rep(i,N){
    print_vector(A);
    rotate(A.begin(), A.begin()+1, A.end());
  }
}

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

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

B - Putting Bricks in the Wall ～入口と出口なら管理しやすい～

1100 
void solve(){
  ll N;
  cin>>N;
  VS S(N);
  rep(i,N)cin>>S[i];
  
  ll goal=0;
  if(S[N-1][N-2]=='1')goal++;
  if(S[N-2][N-1]=='1')goal++;

  ll start=0;
  if(S[0][1]=='1')start++;
  if(S[1][0]=='1')start++;

  vector<PII> Ans; // (y,x)
  if(goal==0){
    // 左上を1で囲む
    if(S[0][1]=='0')Ans.push_back({0,1});
    if(S[1][0]=='0')Ans.push_back({1,0});
  }
  else if(goal==2){
    // 左上を0で囲む
    if(S[0][1]=='1')Ans.push_back({0,1});
    if(S[1][0]=='1')Ans.push_back({1,0});
  }
  else{
    // goal==1
    if(start==0){
      // 右下を1で囲む
      if(S[N-1][N-2]=='0')Ans.push_back({N-1,N-2});
      if(S[N-2][N-1]=='0')Ans.push_back({N-2,N-1});
    }
    else if(start==2){
      // 右下を0で囲む
      if(S[N-1][N-2]=='1')Ans.push_back({N-1,N-2});
      if(S[N-2][N-1]=='1')Ans.push_back({N-2,N-1});
    }
    else{
      // start==1
      // 左上を0で囲み、右下を1で囲む
      // 左上を0で囲む
      if(S[0][1]=='1')Ans.push_back({0,1});
      if(S[1][0]=='1')Ans.push_back({1,0});
      // 右下を1で囲む
      if(S[N-1][N-2]=='0')Ans.push_back({N-1,N-2});
      if(S[N-2][N-1]=='0')Ans.push_back({N-2,N-1});
    }
  }
  p(SZ(Ans));
  for(auto pa : Ans){
    p2(pa.first+1, pa.second+1);
  }
}

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

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

C. Link Cut Centroids ～木の重心～

1700 ライブラリ 重心
  • 問題説明

重心が1つのみの木を作りたい。辺を1つ削除し、辺を1つ追加して新たな木としてよい時、それは可能。その操作（辺の追加・削除）を構築せよ

f:id:peroon:20210619183536p:plain

  • その他
    • 木の重心を求める関数を使いました記念
    • 下記のコドフォURL内の関数を微修正したのみ。centroidを求めるコードの理解はしていない
// 木の重心（最大2つ）
// https://codeforces.com/blog/entry/57593
VI Centroid(const VV &g) {
  int n = g.size();
  VI centroid;
  VI sz(n);
  function<void (int, int)> dfs = [&](int u, int prev) {
    sz[u] = 1;
    bool is_centroid = true;
    for (auto v : g[u]) if (v != prev) {
      dfs(v, u);
      sz[u] += sz[v];
      if (sz[v] > n / 2) is_centroid = false;
    }
    if (n - sz[u] > n / 2) is_centroid = false;
    if (is_centroid) centroid.push_back(u);
  };
  dfs(0, -1);
  return centroid;
}

蟻本

  • 蟻本v2 p320に「木の重心分解」について書いてある