J - Sushiで期待値DPを掴んだ気がする

Quiz

https://atcoder.jp/contests/dp/tasks/dp_j

AC

https://atcoder.jp/contests/dp/submissions/8788822

参考

• けんちょんさん https://qiita.com/drken/items/03c7db44ccd27820ea0d#j-%E5%95%8F%E9%A1%8C---sushi
  • しかし、＋１の部分がよく分からなかった
• そこで、tsutajiroさん
  • http://compro.tsutaj.com/archive/180220_probability_dp.pdf

• サイコロの期待値DPで感覚を掴む
• 上記画像の最後で書かれている、
  • Σ（Es+x + 1) / 6
  • これは+1部分を外に出すと
  • Σ（Es+x)/6 + 1
  • となり、けんちょんさんのと同じ形になる
• （遷移元）＝（遷移先）＋１
• 今回のSushiに当てはめると、下記のようになる

• あとはけんちょんさんの通り、式変形で
• dp[i, j, k] = dp[(i, j, kがより小さい)]
• の形にしてメモ化再帰すればいい

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

文字列s内に文字列tは部分文字列として存在するか？

Quiz

D - Lucky PIN https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_d

AC

https://atcoder.jp/contests/sumitrust2019/submissions/8781474

Code：部分列判定

// s内に部分列としてtがあるか探す
bool is_substring(string& s, string& t){
  // t's index
  ll now = 0;
  rep(i, SZ(s)){
    if(s[i]==t[now]){
      now++;
      if(now==SZ(t)) return true;
    }
  }
  return false;
}

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

next_partial_permutationとは何なのか？動作を観察した～ペアの全探索～

next_permutationの動きを確認

    VI V;
    rep(i, 4){
      V.push_back(i);
    }
    do{
      debug(V);
    }while(next_permutation(ALL(V)));

出力

[V]: {0, 1, 2, 3}
[V]: {0, 1, 3, 2}
[V]: {0, 2, 1, 3}
[V]: {0, 2, 3, 1}
[V]: {0, 3, 1, 2}
[V]: {0, 3, 2, 1}
[V]: {1, 0, 2, 3}
[V]: {1, 0, 3, 2}
[V]: {1, 2, 0, 3}
[V]: {1, 2, 3, 0}
[V]: {1, 3, 0, 2}
[V]: {1, 3, 2, 0}
[V]: {2, 0, 1, 3}
[V]: {2, 0, 3, 1}
[V]: {2, 1, 0, 3}
[V]: {2, 1, 3, 0}
[V]: {2, 3, 0, 1}
[V]: {2, 3, 1, 0}
[V]: {3, 0, 1, 2}
[V]: {3, 0, 2, 1}
[V]: {3, 1, 0, 2}
[V]: {3, 1, 2, 0}
[V]: {3, 2, 0, 1}
[V]: {3, 2, 1, 0}

next_partial_permutationというテク

• http://cielavenir.github.io/blog/2018/06/10/pair-team/

    ll N = 4;
    VI V;
    rep(i, 4){
      V.push_back(i);
    }
    do{
      debug(V);
      reverse(V.begin()+N/2,V.end()); // 後半半分をリバースする
    }while(next_permutation(ALL(V)));

出力

[V]: {0, 1, 2, 3}
[V]: {0, 2, 1, 3}
[V]: {0, 3, 1, 2}
[V]: {1, 0, 2, 3}
[V]: {1, 2, 0, 3}
[V]: {1, 3, 0, 2}
[V]: {2, 0, 1, 3}
[V]: {2, 1, 0, 3}
[V]: {2, 3, 0, 1}
[V]: {3, 0, 1, 2}
[V]: {3, 1, 0, 2}
[V]: {3, 2, 0, 1}

• 数は、4!=24だったものが12に減っている (1/2になっている)
• 消えたものを✕でチェックすると、

[V]: {0, 1, 2, 3}
[V]: {0, 1, 3, 2} ✕
[V]: {0, 2, 1, 3}
[V]: {0, 2, 3, 1} ✕
[V]: {0, 3, 1, 2}
[V]: {0, 3, 2, 1} ✕
[V]: {1, 0, 2, 3}
[V]: {1, 0, 3, 2} ✕
[V]: {1, 2, 0, 3}
[V]: {1, 2, 3, 0} ✕
[V]: {1, 3, 0, 2}
[V]: {1, 3, 2, 0} ✕
[V]: {2, 0, 1, 3}
[V]: {2, 0, 3, 1} ✕
[V]: {2, 1, 0, 3}
[V]: {2, 1, 3, 0} ✕
[V]: {2, 3, 0, 1}
[V]: {2, 3, 1, 0} ✕
[V]: {3, 0, 1, 2}
[V]: {3, 0, 2, 1} ✕
[V]: {3, 1, 0, 2}
[V]: {3, 1, 2, 0} ✕
[V]: {3, 2, 0, 1}
[V]: {3, 2, 1, 0} ✕

N=6の場合はどうか

    ll N = 6;
    VI V;
    ll cnt=0;
    rep(i, 6){
      V.push_back(i);
    }
    do{
      debug(V);
      cnt++;
      //reverse(V.begin()+N/2,V.end()); // 後半半分をリバースする
    }while(next_permutation(ALL(V)));
    debug(cnt);

• 720回
• reverseを入れると、120回 (1/6になっている)

N=8の場合

• reverseなし40320
• reverseあり1680
• 1/24になっている

N=4, 6, 8を一般化する

• N=4の場合、[4, 3, 2, 1]を考えた時の後半部分 2x1
• N=6の場合、[6, 5, 4, 3, 2, 1]を考えた時の後半部分 3x2x1
• N=8の場合、[8, 7, 6, 5, 4, 3, 2, 1]を考えた時の後半部分 4x3x2x1
• これだけ減る
• next_permutaion N!
• next_partial_permutation nPr

実践

• No.699 ペアでチームを作ろう２ https://yukicoder.me/problems/no/699
• N=14
• 14! = 87178291200 TLE
• reverseを入れると、14! / 7! = 17297280 間に合う
• なぜnext_partial_permutationでいいのかの説明
  • http://cielavenir.github.io/blog/2018/06/10/pair-team/

通るコード例

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());

    ll ans = 0;
    do {
        ll s = 0;
        for (int i = 0; i < n / 2; i++) s ^= (a[i] + a[i + n / 2]);
        ans = max(ans, s);
        reverse(a.begin() + n / 2, a.end());
    } while (next_permutation(a.begin(), a.end()));
    cout << ans << endl;
    return 0;
}

• 配列を前半後半に分断して、図のようにペアにすれば全探索になると理解した

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

sum of all cost between all nodes in a tree ～木の全点間コストの和～

Quiz

https://yukicoder.me/problems/no/872

AC

https://yukicoder.me/submissions/404193

解法

• まずはganariyaさんの解説を読みましょう
  • https://scrapbox.io/ganariya/YukicoderContest221_C%E5%95%8F%E9%A1%8CP2_%E3%80%8CAll_Tree_Path%E3%80%8D

• そこに書かれている通り、あるエッジを使う回数は「エッジの向こう側」ｘ「エッジのこちら側」
• dfsで「エッジの向こう側」の数が求められればよい

// i以降のノード数を返す
// (iも含む)
ll dfs(ll i, ll prev){
  ll sum = 0;
  for(auto edge : G[i]){
    if(edge.to==prev) continue;
    sum += dfs(edge.to, i);
  }

  ll a = sum+1;
  ll b = N-a;
  ll d = dist2(i, prev);
  ans += a*b*d;

  return sum+1;
}

その他

• タイトルをgooglability高い感じにした

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

D - Lucky PIN ～4次元DPで解く編～

Quiz

https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_d

AC

https://atcoder.jp/contests/sumitrust2019/submissions/8754255

解法

• dp[i][j][k][l]
• i : i番目まで見た時
• j : 最後に選んだ数
• k : 1つ前に選んだ数
• l : 2つ前に選んだ数
• としてDP
• しかし、選んだ数が未定という状態を数字10として扱った

ll dp[30010][11][11][11];

// 初期状態
ll v = ctoi(s[0]);
dp[0][v][10][10] = 1;
dp[0][10][10][10] = 1;

Code

FOR(i, 1, N){
  char c = s[i];
  ll v = ctoi(c);

  rep(j, 11){
    rep(k, 11){
      rep(l, 11){
        // 今回のを採用しない
        dp[i][j][k][l] += dp[i-1][j][k][l];
      }
    }
  }

  rep(j, 11){
    rep(k, 11){
      // 今回のを採用
      dp[i][v][j][k] += dp[i-1][j][k][10];
    }
  }
}

ll cnt = 0;
rep(i, 10){
  rep(j, 10){
    rep(k, 10){
      if(dp[N-1][i][j][k]) cnt++;
    }
  }
}
p(cnt);

感想など

• この解法はeditorialに載っていなかったので書いた
• これで通せたのは成長と言えるが、時間をかけすぎた
• editorialにはもっと簡単な解法があったので、DPにこだわりすぎないようにしたい

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?