perogram

No.845 最長の切符 ~最長距離・ダイクストラ・ベルマンフォード・bit DP~

Quiz

AC

https://yukicoder.me/submissions/405827

解法

// i : また訪れてない頂点フラグ
// j : 現在地
// とした場合の最長距離
int dp[1<<16][16];
  • としてbit DP

以下、(間違った考え方による)試行錯誤

最長距離をダイクストラで求める!?

f:id:peroon:20191207101115p:plain

5 6
5 3 14284
5 4 7227
2 5 36216
2 1 29991
5 1 49500
4 3 2748
  • これはとあるテストケース
  • 眺めると、2-1-5-3-2と進むのが最長で、答えは96523
  • これをコストに-1をかけて頂点2からダイクストラすると、

f:id:peroon:20191207101505p:plain

  • まず最短距離で行ける5がfixする
  • 次に、最短距離で行ける1がfixする
  • 1から5に行けばより最短距離だが、ダイクストラは近くの点から最短距離をfixさせていき、上書きはしないアルゴリズムなので、2-1-5のパスで上書きされることはなく、正しい解も求まらない

最長距離をベルマンフォードで求める!?

  • ではベルマンフォードならどうか?
  • こちらは上書きを繰り返していくアルゴリズム
  • しかし、上図を見ればわかるように、負の閉路が存在するので解は-infとなり、こちらも正しい解は求まらない

W - Intervals ~遅延セグ木(範囲加算・範囲Max)~

Quiz

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

解説AC

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

感想

  • 論理はemtubasaさんの解説を参考
  • 遅延セグ木はふるやんさんのを借りてきた
    • いくつかパターンが書かれているから再利用しやすそう
    /*
    区間更新・区間和
    auto operation = [](ll a, ll b) { return a + b; };
    auto adapt_lazy = [](ll a, ll b) { return b; };
    auto merge_lazy = [](ll a, ll b) { return b; };
    auto multiply_lazy = [](ll a, int n) { return a * n; };
 
    区間加算・区間和
    auto operation = [](ll a, ll b) { return a + b; };
    auto adapt_lazy = [](ll a, ll b) { return a + b; };
    auto merge_lazy = [](ll a, ll b) { return a + b; };
    auto multiply_lazy = [](ll a, int n) { return a * n; };
 
    区間更新・区間最小
    auto operation = [](ll a, ll b) { return min(a, b); };
    auto adapt_lazy = [](ll a, ll b) { return b; };
    auto merge_lazy = [](ll a, ll b) { return b; };
    auto multiply_lazy = [](ll a, int n) { return a; };
 
    区間加算・区間最小
    auto operation = [](ll a, ll b) { return min(a, b); };
    auto adapt_lazy = [](ll a, ll b) { return a + b; };
    auto merge_lazy = [](ll a, ll b) { return a + b; };
    auto multiply_lazy = [](ll a, int n) { return a; };
    */
  • 範囲Maxセグ木を見つけてきても遅延セグ木じゃない(範囲加算できない)ものだったりして、探すにも時間がかかった
  • コンテスト中に探すのは避けたい
  • 今回のように1度ACしておくと安心して使える
  • 難易度は、水色の自分には少し早かったか

テクい!「D - サイコロ」(Typical DP Contest)

Quiz

https://tdpc.contest.atcoder.jp/tasks/tdpc_dice

AC

https://tdpc.contest.atcoder.jp/submissions/8804908

テクい点

  • サイコロN回分のdpテーブルを用意するとメモリが足りないので、2回分だけ用意して使い回す
    • cur, next
    • memset
  • 素因数分解がsqrt(D)では間に合わない
    • 2, 3, 5で割れるかだけ知りたいのでlog(D)で求められる
  • dpテーブルはlong longで持つとオーバーフローするのでdoubleで持つ
    • ちなみに最初はlong doubleとしていて、どちらでも通った
    • doubleの方が2倍速かった(定数倍効く)
  • dpテーブルの状態の持ち方
    • dp[i][2の指数][3の指数][5の指数]

Code

double dp[2][201][101][101];

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

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

    ll cur = 0;
    ll next = 1;
    dp[0][0][0][0] = 1;
    rep(i, N){
      memset(dp[next], 0, sizeof(dp[next]));
      // i回目なら、今までに出た2の数は
      ll num2_max = 2*i;
      ll num3_max = i;
      ll num5_max = i;
      
      rep(j, num2_max+1){
        rep(k, num3_max+1){
          rep(l, num5_max+1) if(dp[cur][j][k][l]){
            dp[next][j][k][l] += dp[cur][j][k][l]; // 1
            dp[next][j+1][k][l] += dp[cur][j][k][l]; // 2
            dp[next][j][k+1][l] += dp[cur][j][k][l]; // 3
            dp[next][j+2][k][l] += dp[cur][j][k][l]; // 4
            dp[next][j][k][l+1] += dp[cur][j][k][l]; // 5
            dp[next][j+1][k+1][l] += dp[cur][j][k][l]; // 6
          }
        }
      }
      swap(cur, next);
      // cur == 1
      // next == 0
    }

    ll d = D;
    int two = 0, three = 0, five = 0;
    while(d % 2 == 0) two++, d /= 2;
    while(d % 3 == 0) three++, d /= 3;
    while(d % 5 == 0) five++, d /= 5;

    double sum = 0;
    FOR(i, two, 201){
      FOR(j, three, 101){
        FOR(k, five, 101){
          sum += dp[cur][i][j][k];
        }
      }
    }
    rep(i, N){
      sum /= 6.0;
    }
    cout << setprecision(20);
    p(sum * (d==1));

    return 0;
}

U - Grouping (Educational DP Contest / DP まとめコンテスト)

Quiz

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

AC

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

参考にした解説

https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/0106_educational_dp_3

部分集合から部分集合を選ぶ全列挙

http://perogram.hateblo.jp/entry/2019/12/06/021400

無限ループでRE

f:id:peroon:20191206031217p:plain

  • rec関数で無限ループに入る箇所があり、REが起きていた
  • return code 139なので、いつもの配列の範囲外アクセスだと思いこみ、配列をvectorに書き直して、アクセスを[]から.at()に書き換えていくも直らず
  • 原因は、部分集合の中の部分集合列挙時、空集合を作ってしまうと同じrecを呼んでしまうからだった
  • 画像をよく見ると、max memory: 11MBと表示されており、これは配列のエラーでは出ない
  • この表示の場合は同じrecを呼び続けたスタックオーバーフローだろう

ビットで表された部分集合の全探索(蟻本p144)

  • たとえば8人集合 01101101
  • 1が生きているとする
  • 生きている中から部分集合の選び方を全探索する
  • 今回の場合、1が5つあるので、25=32種類の選び方がある
  • それを無駄なく列挙する方法は蟻本に書いてある
    ll sup = 0b01101101;
    ll sub = sup;
    do{
      debug(bitset<10>(sub));
      sub = (sub-1)&sup;
    }while(sub!=sup);

実行結果

[bitset<10>(sub)]: 1011011000
[bitset<10>(sub)]: 0011011000
[bitset<10>(sub)]: 1001011000
[bitset<10>(sub)]: 0001011000
[bitset<10>(sub)]: 1010011000
[bitset<10>(sub)]: 0010011000
[bitset<10>(sub)]: 1000011000
[bitset<10>(sub)]: 0000011000
[bitset<10>(sub)]: 1011001000
[bitset<10>(sub)]: 0011001000
[bitset<10>(sub)]: 1001001000
[bitset<10>(sub)]: 0001001000
[bitset<10>(sub)]: 1010001000
[bitset<10>(sub)]: 0010001000
[bitset<10>(sub)]: 1000001000
[bitset<10>(sub)]: 0000001000
[bitset<10>(sub)]: 1011010000
[bitset<10>(sub)]: 0011010000
[bitset<10>(sub)]: 1001010000
[bitset<10>(sub)]: 0001010000
[bitset<10>(sub)]: 1010010000
[bitset<10>(sub)]: 0010010000
[bitset<10>(sub)]: 1000010000
[bitset<10>(sub)]: 0000010000
[bitset<10>(sub)]: 1011000000
[bitset<10>(sub)]: 0011000000
[bitset<10>(sub)]: 1001000000
[bitset<10>(sub)]: 0001000000
[bitset<10>(sub)]: 1010000000
[bitset<10>(sub)]: 0010000000
[bitset<10>(sub)]: 1000000000
[bitset<10>(sub)]: 0000000000

Range Max Query セグメント木

f:id:peroon:20191205162040p:plain

Quiz

Q - Flowers https://atcoder.jp/contests/dp/tasks/dp_q

AC (自作セグ木)

AC(https://ei1333.github.io/luzhiled/)

SegmentTree<ll> seg(N, [](ll a, ll b) { return max(a, b); }, 0);

その他

  • 1度ACしておくと、コンテスト中も安心して再利用できる

assert(false)でREを起こしてジャッジの反応を見る

f:id:peroon:20191205013225p:plain

Quiz

M - Candies https://atcoder.jp/contests/dp/tasks/dp_m

RE Code

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

解説

  • REとなったコードはO(NxKxK)なので普通に出すとTLE
  • そのまま出してAC or TLEだったら論理は合っていそう
  • ただ、ジャッジに待つ
  • そこで、Kが大きい時はこちらからREを発生させてしまおう
    if(K>999){
      assert(false);
    }
  • これで小さいテストケースでは全てACすることが確認でき、あとは高速化だけをすればよさそうと判断できる