D. Nezzar and Board 差の絶対値の全ペアのgcdはO(N^2)ではなくO(N)

f:id:peroon:20210129120544p:plain

G - Strange Beauty

f:id:peroon:20210127062803p:plain

  • 計算量
    • Time LimitがシビアでTLEしていたので、各数字のカウントをmapからvectorにした
    • dpの箇所で各値の倍数を見ていくが、これは調和級数の和なので 1/1 + 1/2 + 1/3 + ... + 1/N = log(N) に収まる
void solve(){
  ll N;cin>>N;
  VI A(N);
  rep(i, N)cin>>A[i];
  SORT(A);
  ll max_value = A.back();

  VI C(max_value+1); // count
  for(ll a : A)C[a]++;

  VI B = A; // unique values
  auto it = unique(ALL(B));
  B.erase(it, B.end());

  VI exist(max_value+1);
  for(ll b : B)exist[b]=1;

  auto dp = C;
  ll max_group_size=MAX(dp);

  for(ll b : B){
    FOR(i,2,max_value+1){
      ll v = i*b;
      if(v>max_value)break;
      if(exist[v]){
        chmax(dp[v], dp[b]+C[v]);
        chmax(max_group_size, dp[v]);
      }
    }
  }
  ll ans = N-max_group_size;
  p(ans);
}

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

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

koboshiさん

F. Unusual Matrix

たしかにそうっぽいが天才感がある。もっと再現性のある方法はないか？ということで以下に続く

  • 私の解法
    • A[i][j] ^= B[i][j]として、Aを全て0にする問題にする
    • 1行目のswapを「やる」「やらない」の両方試す
    • 1行目のswapをやった後でも1行目にまだ1が残っているならば、その1は縦swapにより0にする必要がある。つまり1行目を決めてやると縦のswapをするかどうかが全て決まる
    • あと残された操作は2行目以降の横swapのみ。これを使って全てを0にできればYES
    • （蟻本でも「1行目を決めてやれば後は決まる」というのがありましたね）

code

// for codeforces
void solve(){
  ll N;
  cin>>N;
  VV A(N, VI(N));
  VV B(N, VI(N));
  rep(i,N){
    string s;cin>>s;
    rep(j,N){
      if(s[j]=='1')A[i][j]=1;
    }
  }
  rep(i,N){
    string s;cin>>s;
    rep(j,N){
      if(s[j]=='1')B[i][j]=1;
    }
  }
  rep(i,N){
    rep(j,N){
      A[i][j] ^= B[i][j];
    }
  }
  
  auto A_original = A;
  // 1週目 1行目をswapしない場合
  // 2週目 1行目をswapした場合
  rep(_,2){
    A = A_original;

    if(_==0){
      // 1行目をswap
      rep(i,N){
        A[0][i] ^= 1;
      }
    }

    // check
    // 1行目を見て、列のswapが必要な箇所は今1である部分
    rep(x,N){
      if(A[0][x]==1){
        // その列は全てswapする
        rep(y,N){
          A[y][x] ^= 1;
        }
      }
    }

    bool ok=true;
    FOR(y,1,N){
      // 残りの行は0にできるか
      // 全部0か、全部1なら横swapにより可能
      ll sum = SUM(A[y]);
      if(sum==0 or sum==N){
        // safe
      }else{
        ok=false;
      }
    }
    if(ok){
      p_yes();return;
    }
  }
  p_no();
}

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

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

E. Correct Placement

1700
  • Quiz
  • AC
  • 解説
    • 座圧したりセグ木使ったり色々解法はあるようですが、mapを使った解法を紹介します
    • (width, height)は横長で揃えておく
    • (width, height, index)のデータをwidthの昇順ソートし、小さい順に見ていく
    • 今見ているデータより前に出てきたデータは現在のwidth以下である（ので、あとはheightだけに注目すればいい）
    • 現在のwidth「未満」の人の中での最小高さ（とその人のindex）を持っておけば、その人は小さい（枠に収まる）

f:id:peroon:20210125064438p:plain

void solve(){
  ll N;
  cin>>N;

  // width => (height, index)
  map<ll, vector<PII>> mp;
  
  rep(i,N){
    ll w,h;cin>>w>>h;
    // assume w >= h
    if(h>w)swap(w,h);
    mp[w].push_back({h,i});
  }
  
  VI Ans(N,-2);
  ll min_height=inf;
  ll min_height_index=-1;
  for(auto pa : mp){
    ll w = pa.first;

    ll local_min_height=inf;
    ll local_min_height_idx=-1;
    for(auto h_i : pa.second){
      ll h = h_i.first;
      ll idx = h_i.second;
      if(min_height<h){
        // found!
        Ans[idx]=min_height_index;
      }
      if(chmin(local_min_height,h)){
        local_min_height_idx = idx;
      }
    }

    // finally, update for next width
    if(chmin(min_height, local_min_height)){
      min_height_index = local_min_height_idx;
    }
  }
  print_vector(Ans,1);
}

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

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