D. Powerful Ksenia

• Quiz
  • https://codeforces.com/contest/1438/problem/D
• AC
  • なし
• 解説
  • editorialは読んだとする
  • このコード、美しい・・・ https://codeforces.com/contest/1438/submission/98381344

from functools import reduce
n = int(input())
a = list(map(int, input().split()))
def solve(n):
    print("YES\n", n-1, sep = '')
    for i in range(n//2):
        print(2*i+1, 2*i+2, n)
    for i in range(n//2):
        print(2*i+1, 2*i+2, n)
if n%2 == 1:
    solve(n)
elif reduce(lambda x, y : x^y, a, 0) > 0:
    print("NO")
else:
    solve(n-1)

• 動作を画像にすると以下

C. Space Formula

• Quiz
  • https://codeforces.com/contest/1046/problem/C
• AC
  • https://codeforces.com/contest/1046/submission/98531774
• 感想
  • 通したんだけどモヤモヤ・・・
  • "It's guaranteed that given astronaut will have unique number of points before the race."って書かれているから配列Sはunique(同じ数が存在しない)なのでは？
  • (TLEしたのでテストケースを見たらSに同じ数が存在した)
• 解法
  • D番目の自分が1位を取ったことにして、その時のスコアが基準となる。そのスコアをmeとする
  • レースで1番低い点数を与えてもmeを越えてしまう人には、低い点数を割り振らなくてよく、逆に残っているうちの1番高い点数を割り当てればいい

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

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

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

    // next point
    VI P(N);
    rep(i, N) cin >> P[i];

    ll me = A[D-1] + P[0];
    
    multiset<ll> se;
    rep(i,N){
      if(i==D-1)continue;
      se.insert(A[i]);
    }

    ll rank=1;
    FOR(i,1,N){
      ll p = P[i];
      // この大きいポイントを誰に与えるか
      auto it = se.begin();
      if(*it + p <= me){
        se.erase(it);
      }
      else{
        // 1番小さい人に与えても抜けないので、このポイントはseの1番大きい人に与える
        it = se.end();
        it--;
        se.erase(it);
        rank++;
      }
    }
    p(rank);

    return 0;
}

C. Sonya and Robots

• Quiz
  • https://codeforces.com/contest/1004/problem/C
• AC
  • https://codeforces.com/contest/1004/submission/98520055
• 解説
  • 左のロボットの居場所と右のロボットの居場所の切れ目をすべて見る
  • 左のロボットの領域を1つずつ拡大していく
  • すでに見た数字を左に取り込んだなら、そのペアはすでに数えているので数えない

sample 1

int main(){
    // input
    ll N; 
    cin>>N;

    VI A(N);
    rep(i, N) cin >> A[i];
    
    map<ll,ll> mp, mp2;
    
    // left
    mp[A[0]]++;

    // right
    FOR(i,1,N)mp2[A[i]]++;

    ll sum=0;
    sum += mp.size() * mp2.size();

    FOR(i,1,N-1){
      // i番目を左に移動
      ll a = A[i];
      bool new_val=false;
      if(mp.count(a)==0){
        new_val=true;
      }

      mp[a]++;
      mp2[a]--;
      if(mp2[a]==0){
        auto it = mp2.find(a);
        mp2.erase(it);
      }

      if(new_val){
        sum += mp2.size();
      }
    }
    p(sum);
    
    return 0;
}

981C - Useful Decomposition

• Quiz
  • https://codeforces.com/contest/981/problem/C
• AC
  • https://codeforces.com/contest/981/submission/98427495
• 問題理解
  • 読解に苦労したが、画像を見れば一発だろう（下記）
  • 木をパスに分解する。各パスは互いに接している必要がある

• 解説
  • これを考えると次数3以上の頂点が2つ以上あると「接せない異なる色のパス」ができてしまうのでNo
  • それ以外の場合は次数3以上の頂点は高々1つで、そこから葉に向けてをパスにすれば条件を満たす

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

    // input
    ll N; 
    cin>>N;

    VI A(N-1);
    VI B(N-1);
    VI dim(N);
    rep(i,N-1){
      ll a,b;cin>>a>>b;a--;b--;
      A[i]=a;
      B[i]=b;
      dim[a]++;
      dim[b]++;
    }

    if(N==2){
      p_yes();
      p(1);
      p2(A[0]+1,B[0]+1);
      return 0;
    }
    
    ll over3_cnt=0;
    rep(i,N){
      if(dim[i]>=3)over3_cnt++;
    }
    if(over3_cnt>1)no();

    VI leafs;
    rep(i,N){
      if(dim[i]==1)leafs.push_back(i);
    }

    ll ma = MAX(dim);
    ll center = -1;
    rep(i,N){
      if(dim[i]==ma)center=i;
    }
    p_yes();
    p(leafs.size());
    for(ll leaf : leafs){
      p2(leaf+1, center+1);
    }

    return 0;
}

D. Divide by three, multiply by two

• Quiz
  • https://codeforces.com/problemset/problem/977/D
  • x2か÷3をして作れる列を復元せよ
• AC
  • https://codeforces.com/contest/977/submission/98420443
• 解説
  • 制約には書いていないが、操作を考えると各数字aは1度しか出てこないことが分かる
  • サンプル1を図示するとDAGになっている
  • トポロジカルソートすればよい

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

    // input
    ll N; 
    cin>>N;

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

    // 存在確認用
    set<ll> se;
    for(ll a : A)se.insert(a);
    
    // value to index
    map<ll,ll> mp;
    rep(i,N){
      ll a = A[i];
      mp[a] = i;
    }

    VV G(N);
    rep(i,N){
      ll a = A[i];
      if(se.count(2*a)){
        ll j = mp[2*a];
        G[i].push_back(j);
      }
      if(a%3==0 && se.count(a/3)){
        ll j = mp[a/3];
        G[i].push_back(j);
      }
    }
    auto result = topological_sort(G);
    VI Ans;
    for(ll i : result) Ans.push_back(A[i]);
    print_vector(Ans);

    return 0;
}

別解：一本道なので

• 始点が分かれば一本道になることが分かる
• 始点になれる点は、他の数字から遷移してこれない、入次数が0のもの。それが1つだけ存在する
• x2, ÷3のどちらかの遷移先が存在知るので、setで存在確認をlogNで行えば間に合う
• AC https://codeforces.com/contest/977/submission/107385062

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

    // input
    ll N; 
    cin>>N;

    VI A(N);
    rep(i, N) cin >> A[i];
    
    set<ll> se;
    for(ll a : A)se.insert(a);

    ll start=-1;
    for(ll a : A){
      // 左からの矢印が生えていない
      if(a%2==0 && se.count(a/2))continue;
      if(se.count(3*a))continue;
      
      // 上記条件を通らないものがあるならば、それは始点
      start=a;break;
    }

    VI Ans = {start};
    rep(i,N-1){
      ll a = Ans.back();
      if(se.count(2*a)>0){
        Ans.push_back(2*a); continue;
      }
      if(a%3==0 && se.count(a/3)>0){
        Ans.push_back(a/3); continue;
      }
    }

    print_vector(Ans);
    return 0;
}