hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

four-t practice 2019 #09

2019 年 6 月 2 日 (日) に AOJ でチーム練習をしたのでその時の立ち回りのメモです

メモ

開始。A はすぐわかるので書いて通す。B は微妙に計算量落とさなかったみたいで 1 ペナあったけど通ってた (問題見てない)。C, D もいつの間にか rsk0315 と TAB が通してた。

E は bit DP かな〜と思ってたけどよく考えたらやばそうなケースがあって無理そう、と思ってチームメイトに考察してもらう。その間、F が解けそうなので見てみる。読んでいくと木構造であることはわかるので DP ができるなあと思いながら紙コーディングをする。

G はすでに TAB が見たことあったらしい (問題選定ミスってすいません) ライブラリを写すパートが必要なので F と交代しながら作業していく。しばらくして G が通る。

F は書けたけど永遠にバグっていてサンプルが合わない。そしてそのまま終了してしまった。ひどい・・・。

家に帰って復習してみたんだけど考察の一部が重大に間違っていて、そりゃ通るわけないですねとなりました。そこを直したら通りました。申し訳ない・・・

反省

詰まった時にもっとチームメイトを頼りたい、なんか焦ると視野が狭くなってペアプロとかその辺の選択肢が頭から消えてしまうのでダメで・・・

AOJ-ICPC の問題、なんか通すまで 1 時間くらいかかるのでバチャとかで時間を計ってやる必要性を感じた

AOJ 2436: Card

同じ方針でやっている人があまりいなさそうなので一応書きます。

問題概要

日本語なので原文を参照してください → Card | Aizu Online Judge

解説

整数を組み合わせて最終的に  M という数を作ったとします。与えられるそれぞれの整数について、その整数の 1 の位が  M の何の位として使用されている通り数が何通りあるかがわかれば、元の問題が解けます。ここまでは公式解説の方針と同じです。

さて、整数  a_i について組み合わせを求めるとき、それ以外の整数について並べ方を考慮しなければなりません。特に、 a_i より低い位に並べる整数について、その桁数が合計で何桁になるかは答えを求める際に重要な情報です。また、低い位で整数をいくつ使ったかがわからないと、 a_i より高い位に整数を最大でいくつ使えるかがわかりません。よって、

  •  a_i より低い位に、整数を「何個」並べているか
  •  a_i より低い位に、整数を合計「何桁」並べているか

の情報が必要になります。

これを処理するために DP を考えます。dp[i][j][k] := i 番目の整数まで見て、そのうち j 個を使用し、使用した整数の桁数の合計が k であるような状態の通り数 とします。

しかしここで問題となるのが、 a_i について通り数を考えるときは DP 内で  i 番目を選んではいけない ことです。 i 番目を必ず選ばないとしたときの通り数を求めるために、ここで戻す DP のテクニックを使います。

先ほど定義した DP は、実際に書くと以下のような遷移になります。(説明のため、「何番目の要素まで処理したか」に相当する 1 次元目を省略せずに書いています)

int sum = 0;
for(int i=0; i<N; i++) {
    sum += digit[i]; // i 番目の整数の桁数
    for(int j=0; j<=i; j++) {
        for(int k=0; k<=sum; k++) {
            dp[i+1][j][k] += dp[i][j][k]; // その整数を使わない
            if(k + digit[i] <= sum) dp[i+1][j+1][k+digit[i]] += dp[i][j][k] * (j + 1); // その整数を使う
        }
    }
}

この遷移をひもといていくと、dp[i+1][j][k] = dp[i][j][k] + dp[i][j-1][k-digit[i]] * j が成立します。

これを移項すると dp[i][j][k] = dp[i+1][j][k] - dp[i][j-1][k-digit[i]] * j となります。この式は、i+1 番目の状態から i 番目の状態に戻していることを表します。今回は整数を使用する順番が通り数に依存しないので、i を N 番目の整数とみなすと dp2[i][j][k] = dp[N][j][k] - dp2[i][j-1][k-digit[i]] * j とできます。ここで、dp2[i][j][k] := i 以外の全ての整数を考慮し、その中で j 個使って桁数が k になるような状態の通り数 です。

このような情報が得られていれば元の問題を解くことができます。0 の処理が面倒ですが場合分けすればできます。

ソースコード

ll dp[201][805], tmp[201][805];
ll pw[805], tab[201], tab_zero[201];
  
signed main() {
    int N; cin >> N;
    pw[0] = 1;
    for(int i=1; i<805; i++) {
        pw[i] = (pw[i-1] * 10) % MOD;
    }
 
    // tab[i] = iP0 + iP1 + ... iPi
    for(int i=0; i<=N; i++) {
        tab[i] = 1;
        ll P = 1;
        for(int k=1; k<=i; k++) {
            (P *= i - k + 1) %= MOD;
            (tab[i] += P) %= MOD;
            (tab_zero[i] += P * k % MOD) %= MOD;
        }
    }
 
    bool exist_zero = false;
    vector<int> A, digits;
    for(int i=0; i<N; i++) {
        int val; cin >> val;
        if(val == 0) {
            exist_zero = true;
            continue;
        }
        else A.push_back(val);
 
        int d = 0; while(val) d++, val /= 10;
        digits.push_back(d);
    }
 
    int M = A.size(), sum = 0;
    dp[0][0] = 1;
    for(int i=0; i<M; i++) {
        for(int j=i; j>=0; j--) {
            for(int k=sum; k>=0; k--) {
                (dp[j+1][k+digits[i]] += dp[j][k] * (j + 1)) %= MOD;
            }
        }
        sum += digits[i];
    }
 
    // i 番目を使わない場合
    ll ans = 0;
    for(int i=0; i<M; i++) {
        fill(tmp[0], tmp[M+1], 0);
        for(int j=0; j<M; j++) {
            for(int k=0; k<=sum; k++) {
                tmp[j][k] = dp[j][k];
                if(j - 1 >= 0 and k - digits[i] >= 0) {
                    (tmp[j][k] += MOD - (tmp[j-1][k - digits[i]] * j % MOD)) %= MOD;
                }
 
                // j 個を使って合計 k 桁 (これを i 番目の下に置くイメージ)
                // 残っているのは M-j-1 個
                {
                    // 0 を使わない場合
                    ll comb = tab[M-j-1] * tmp[j][k] % MOD;
                    ll val = A[i] * pw[k] % MOD;
                    ll add = val * comb % MOD;
                    (ans += add) %= MOD;
                }
 
                if(exist_zero) {
                    // 0 を使う場合 (i 番目の下に置く)
                    {
                        ll comb = tab[M-j-1] * tmp[j][k] % MOD * (j+1) % MOD;
                        ll val = A[i] * pw[k + 1] % MOD;
                        ll add = val * comb % MOD;
                        (ans += add) %= MOD;
                    }
 
                    // 0 を使う場合 (i 番目の上に置く)
                    {
                        ll comb = tab_zero[M-j-1] * tmp[j][k] % MOD;
                        ll val = A[i] * pw[k] % MOD;
                        ll add = val * comb % MOD;
                        (ans += add) %= MOD;
                    }
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

four-t practice 2019 #08

2019 年 5 月 19 日 (日) に 会津合宿 2013 Day1 を AOJ で解いたのでその時の立ち回りのメモです

メモ

開始。A がパッと見面倒そうだけどよくみたら制約が優しい。落ち着いて書いて AC。

B は TAB と rsk0315 が頑張っていたので任せて、自分は C を見る。答えを求めるパートは簡単だけど、辞書順最小にするところがだるい。適当に復元したら WA になった。辞書順最小なのでちゃんと前から追わないといけなくて、そこに気をつけたら通った。

D は BDD を簡約化するらしい。rsk0315 に任せる。

E を見たけど前半の面倒を抜ければ大丈夫そう。個数制限ナップザックをちゃんと log にして実装して通す。後から気づいたけど log じゃなくて愚直にやると時間制限が危ないらしい。

B がハマってるらしいのでコードを見る。ループの順番がおかしいのと、途中まで 1-indexed の気持ちだったものがあるところから 0-indexed になっていたので指摘する。手間取っていたけど最終的になんとか通ったのでよかった。

F は二重辺連結成分分解でいけないかなあと思って試してみるも WA が返る。関節点を入れたらだめなことに最後の方に気づくも時間が足りなくて終了した。ちなみに関節点考慮しても通らなかったので考察が間違っていそう。

反省

今回は実装量が多めだったのでかなり ICPC の練習になった気がする。

今日の自分は実装面ではそんなにハマらなかったけど、他の人が担当している問題のリカバリーをするのがおそすぎた。B 問題はもっと早く助けたかった。(とはいえ、A と C と E の実装が終わった後にやっと見れた感じだったので、しょうがない感もある・・・結果的に自分が実装過多になってしまったけどまぁこういうときもありますよね)

あと F は heno_world からフローだよって言われて確かになあってなる。点素だったり辺素だったりするときは当然疑うべきなんですよね、悔しい。

5 時間セットに慣れすぎて 3 時間が一瞬に感じてしまう (時間が足りない)、今まで以上に問題の優先順位を気にしないと厳しそう。