2020-09-06

D. Shortest and Longest LIS

Quiz
- https://codeforces.com/problemset/problem/1304/D
解説
- editorialの補足として、イメージ画像のみ置いておきます
- increasing or decreasingなブロックで分割して、数字を割り振る

f:id:peroon:20200906205943p:plain

2020-09-06

難易度は低いけれど「やるだけ」ではない興味深い問題集

On setting D2A and D2B problems - Codeforces
- https://codeforces.com/blog/entry/75163
- ここで「Div2-A,Bはやるだけ問題を置いておけばいい」「違う、興味深い（思考が必要な）問題も置けるはずだ」という議論がある
- その中で良問として20問ほど挙げられている。difficulty = 800~1200くらい。
- この難易度帯は結構解いてるのでAC済みなものが多かったが、解き直してみて「ハッ」と気づいて解ける良問体験ができた
- 初心者にこどふぉの問題をいくつか提示する場合にいい選択肢だろう

2020-09-06

Bad Ugly Numbers

1000 構築

Quiz
- https://codeforces.com/contest/1326/problem/A
AC
- https://codeforces.com/contest/1326/submission/91974618
解説
- 23333333333333
その他
- AAAAABの形は考えたが、ABBBBBB の形は考えなかった・・・
- その両方を考えつつ、A,Bに2～9を機械的に入れてチェックすれば、答えに徐々に近づいていけるだろう

void solve(){
  ll N;
  cin>>N;
  if(N==1){
    p(-1); return;
  }

  cout << 2;
  rep(i,N-1){
    cout<<3;
  }
  cout << endl;
}

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

2020-09-05

E. Count The Blocks ～ダブルカウントにより本数を数える～

1800

Quiz
- https://codeforces.com/contest/1327/problem/E
AC
- https://codeforces.com/contest/1327/submission/91918902
解説
- editorialの通り、長さlenが何本あるかを数えるときに、はじっこと中間に場合分けして数える
- ここで私がひっかかったのは「ダブルカウントになっているのでは？」だった

例
N = 10
len = 3

はじっこについて、左端の３つに10種類のうちのどれかを置く
たとえば1を置いたとする
111*******

その隣は1以外の何か。たとえば2を置いたとする
1112******

editorialではそれ以外は10種類の自由度があるとしている
（＊には10種類の数字の何でも入る）
なので、例えば下記のものも含まれる
1112**2111

---

同様に右端からも同じように数えるので、同様に
1112**2111
が作れてしまう。これはダブルカウントでは！？

解説つづき
- 今回の問題は「ダブルカウントすることで本数を数えている」と理解した
- 「長さ３を含む数字はいくつあるか？」ではなく「長さ３のブロックは何本とれるか？」の問題であることに注意
- たとえば1112332111なら、2本分カウントするのが正しい
- なのでダブルカウントすることで正しく数えられる。これは新鮮な体験だった

ll N; 
ll f(ll len){
  if(len==N) return 10;

  mint sum = 0;

  // side
  sum += mod_pow(10,N-len) * 9;
  sum += mod_pow(10,N-len) * 9;

  // inner
  sum += (N-len-1) * 9 * 9 * mod_pow(10,N-len-1);

  return sum.x;
}

int main(){
    // input
    cin>>N;
    
    VI Ans;
    FOR(i,1,N+1){
      ll num = f(i);
      Ans.push_back(num);
    }
    print_vector(Ans);
    
    return 0;
}

2020-09-03

D. Maximum Distributed Tree ～木DP 部分木のサイズ, 深さを求めるサンプル～

1800 ライブラリ

Quiz
- https://codeforces.com/contest/1401/problem/D
AC
- https://codeforces.com/contest/1401/submission/91696004
解法
- 辺の両端のノード数の積が大きい辺に、大きい値を割り振るといい
- 木DPで根からの深さと、部分木のサイズを求めておけばいい
- 「割り振る重みが1になる辺は最小にせよ」という条件があるので、重みの個数Mが辺の本数N-1より多いかどうかで場合分けが必要。サンプルにはM<N-1の場合しかないのが不親切
私的メモ
- このコードを木DPのたたき台としよう

f:id:peroon:20200903162943p:plain

// for codeforces
void solve(){
  ll N;
  cin>>N;
  VV G(N);

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

  // 深さを求めるdfs
  VI depth(N, -1);
  function<void(ll,ll,ll)> dfs_depth = [&](ll i, ll prev, ll dep){
    depth[i]=dep;
    for(ll to : G[i]){
      if(to==prev)continue;
      dfs_depth(to,i,dep+1);
    }
    return;
  };
  dfs_depth(0,-1,0);

  // 部分木のサイズを求めるdfs
  VI dp(N, -1);
  function<ll(ll,ll)> dfs = [&](ll i, ll prev){
    ll sum=1;
    for(ll to : G[i]){
      if(to==prev)continue;
      sum += dfs(to,i);
    }
    return dp[i]=sum;
  };
  dfs(0,-1);

  // 割り振る重み
  ll M;cin>>M;
  VI P(M);
  rep(i,M)cin>>P[i];
  RSORT(P);

  // 各辺の倍率
  VI C(N-1);
  rep(i,N-1){
    ll a = A[i];
    ll b = B[i];
    // aの方が根に近いとする
    if(depth[a]>depth[b]) swap(a,b);
    // 両端のnode数
    ll c = dp[b];
    ll d = N-c;
    C[i]=c*d;
  }
  RSORT(C);

  mint ans = 0;
  if(M<N-1){
    // 全ての辺に割り当てられない場合
    P.resize(N-1,1);
    rep(i,N-1){
      mint w = P[i]*C[i]%mod;
      ans += w;
    }
  }
  else{
    // 割り当てる十分なPがある
    // [0]に多くのPを割り当てる
    ll num = M-(N-1)+1;
    mint w = C[0];
    rep(i,num) w *= P[i];
    ans += w;

    // [1]以降
    FOR(i,1,N-1){
      mint w = C[i];
      w *= P[i+num-1];
      ans += w;
    }
  }
  p(ans.x);
}

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

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