Mister雑記

競プロやります。

TopCoder SRM763 Medium 「RootItRight」

問題

 N頂点の木が与えられる。頂点 vにはコスト V_vが割り当てられている。

この木の頂点を1つ選び rとし、木を rを根とする根付き木と見なす。 このとき、各頂点に対してコスト C_vを以下のように定める。

  • 頂点 vに対し、 rから vへのパスを r = v_0, v_1, \cdots, v_k = vとする。
  • このとき C_v = \sum_{i = 0}^{k} V_{v_i} \cdot i

そして根付き木のコストを、全頂点のコストの総和とする。

 rを適切に選んだときの、根付き木のコストの最小値を求めよ。

制約

  •  1 \leq N \leq 2 \times 10^5
  •  0 \leq V_i \lt 10^3

考察

根付き木に関する問題なので、見た感じ全方位木DPだろうな〜と検討がつく(実際合っている)。

まず根付き木のコストについてだが、これは以下のように変形することができる。

 \displaystyle \sum_{v = 0}^{N - 1} V_v \cdot d_v \cdot sz_v

ここで d_vは頂点 vの深さ、 sz_vは頂点 vを根とする部分木のサイズである。  vを通るパスは vの子孫の数だけあって、かつ vは常に d_v番目に現れることからこれは成り立つ。

これを元に根を変えたときのコストの変化量を考えると、以下の図のようになる。

よって頂点0を根としたときの

  • 頂点 vを根とする部分木のサイズ sz_v
  • 部分木全体の V_u \cdot sz_uの和 vsz_v

を事前計算で求めておけば良さそう。

ただし上の図にあるように部分木の根の扱いが厄介で、本番はこの辺を上手く詰められずに時間切れになった。

実装例

using lint = long long;

struct Edge { int src, dst; };
using Graph = vector<vector<Edge<Cost>>>;


class RootItRight {
    int VNUM;        // 頂点数
    vector<lint> V;  // 重み
    Graph tree;

    vector<lint> sz, vsz;
    lint ans;

    // sz, vszを埋めつつ初期解を求める
    // dは頂点vの深さ
    lint dfs(int v, int r, int d) {
        lint ret = 0;
        sz[v] = 1;
        vsz[v] = 0;
        for (auto e : tree[v]) {
            if (e.dst == r) continue;
            ret += dfs(e.dst, e.src, d + 1);
            sz[v] += sz[e.dst];
            vsz[v] += vsz[e.dst];
        }
        vsz[v] += sz[v] * V[v];
        ret += sz[v] * V[v] * d;
        return ret;
    }

    // vを根としたときの解がcost
    void edfs(int v, int r, lint cost, lint add) {
        ans = min(ans, cost);

        for (auto e : tree[v]) {
            if (e.dst == r) continue;

            lint nadd = add;
            nadd += vsz[v] - vsz[e.dst] - V[v] * sz[v];   // 根以外の頂点の分
            nadd += V[v] * (VNUM - sz[e.dst]);            // 根の分

            lint ncost = cost + nadd;
            ncost -= vsz[e.dst];

            edfs(e.dst, e.src, ncost, nadd);
        }
    }

public:
    lint findMinimumTotalCost(int N, vector<int> edge, vector<int> val, int D, int seed, int MX) {
        // グラフ、重みの初期化は省略
        sz.resize(N);
        vsz.resize(N);
        
        ans = dfs(0, -1, 0);

        edfs(0, -1, ans, 0);
        return ans;
    }
};

反省

  • DPは落ち着いて遷移を詰めないとダメとあれほど...。
  • グラフの入力形式に戸惑った時間が無駄だった。

TopCoder SRM763 Easy 「CutCutCut」

問題

 10,000 \times 10,000の正方形がある。 以下の形式からなる Q個のクエリに答えよ。

  • クエリは (x_1, y_1), (x_2, y_2)の2点からなる。
    • 2点は正方形の頂点を除く、異なる辺上にある。
  • 正方形にこの2点を結ぶ線分を加えたとき、正方形がいくつの領域に分割されるか求めよ。
  • ここで加えられた線分は以降のクエリでも残り続ける。

制約

  •  1 \leq Q \leq 500
  • 座標は整数かつ互いに異なる
  • 3つの線分が1点で交わることはない

考察

「正方形の辺上に点を追加」と聞いて、まず浮かんだのがこれ。 「座標を一次元に変換する」という点は使えたのだが、その後の考察でこの問題の解法に引きずられすぎてタイムロスした。

1つの線分が他の k個の点と交わったとする。このとき線分は k + 1個に分割され、各線分が1つの面を分割する。よって k + 1個領域が増えることになる。

線分の交差判定は幾何に見えるが、正方形を数直線に展開して線分を区間とみなせば、2つの区間が交わるか否かで判定できる。 よって新しく追加された線分に対して、他の全ての線分と交差判定をすれば O(Q^2)でこの問題が解ける。

実装例

int L = 10000;

class CutCutCut {
    // 辺上の点を数直線上の点に変換
    int encode(int x, int y) {
        if (x == 0) {
            return y;
        } else if (x == L) {
            return L * 3 - y;
        } else if (y == 0) {
            return L * 4 - x;
        } else {
            return L + x;
        }
    }

public:
    vector<int> findPieces(vector<int> X1, vector<int> Y1, vector<int> X2, vector<int> Y2, int Q) {
        vector<int> in(Q), out(Q);
        vector<int> ret(Q);
        
        int ans = 1;
        for (int i = 0; i < Q; ++i) {
            int p1 = encode(X1[i], Y1[i]);
            int p2 = encode(X2[i], Y2[i]);
            if (p1 > p2) swap(p1, p2);
            in[i] = p1;
            out[i] = p2;

            ++ans;
            for (int j = 0; j < i; ++j) {
                // 交差判定
                for (int q = 0; q < 2; ++q) {
                    if (in[i] < in[j] && in[j] < out[i] && out[i] < out[j]) {
                        ++ans;
                    }
                    swap(i, j);
                }
            }
            ret[i] = ans;
        }
        return ret;
    }
};

反省

  • 焦りすぎてとても悪いムーブをしてしまった。
    • 初めてAppletを使って仕様に戸惑ったというのもある。

AOJ 1620 「論理式圧縮機」

onlinejudge.u-aizu.ac.jp

問題

以下の文法からなる論理式が与えられる。

<E> ::= 0 | 1 | a | b | c | d | -<E> | (<E>*<E>) | (<E>^<E>)

ここで-*^はそれぞれnot、and、xorに当たる。

与えられた式と同値な論理式で、最短のものの長さを求めよ。

制約

  • 論理式の長さは 16以下

考察

与えられた論理式を同値なものに圧縮する、みたいなことを考えるとどツボにハマる。

そもそも論理式が同値というのは「a~dにどんな真理値を割り振っても、全体の真理値が合致する」ということである。 よって全ての割り振りに対して全体の真理値を求め、それをintにすることでその論理式を表現することができる(これを真理値表と呼ぶことにする)。 この真理値表は 2^4通りの全ての割り振りに対して構文解析を行うことで求められる。

後はこの真理値表に対応する論理式の、長さの最小値が分かればいい。 これは長さが短い方から、「その長さの論理式で表現できる真理値表」を求めていけばいい。これは

  • 長さを1増やしてnotをつける
  • 長さを3増やしてandかxorをつける

という遷移によって埋めることができる。

疑問なのは計算量だが、なんと長さ16の論理式で表せる真理値表の数は 3,000を超えない。これはxorとandは高々3個しか入らないことが大きな要因となっている。

実装例

構文解析とDPで実装はそこそこ重いが、やるしかない。

なお以下のコードでは、実装しやすいように文法を以下のように変換している。

expr ::= term | -expr | (bin)
bin  ::= expr*expr | expr^expr
term ::= 0 | 1 | a | b | c | d

onlinejudge.u-aizu.ac.jp

constexpr int mask = (1 << 16) - 1;
constexpr int INF = 1 << 30;

/* ----- 真理値表埋め ----- */
vector<vector<int>> T(17);
// T[l] = 長さlの論理式で表せる真理値表の集合(lは最小)

vector<int> U(1 << 16, INF);
// T[t] = 真理値表tを表す最短の論理式の長さ

void init() {
    // 長さ1は0, 1, a, b, c, dのみ
    T[1] = {0b0000000000000000,
            0b1111111111111111,
            0b1010101010101010,
            0b1100110011001100,
            0b1111000011110000,
            0b1111111100000000};
    for (auto t : T[1]) U[t] = 1;

    for (int k = 2; k <= 16; ++k) {
        for (auto t : T[k - 1]) {
            int v = mask ^ t;  // notを合成
            if (U[v] == INF) {
                U[v] = k;
                T[k].push_back(v);
            }
        }

        for (int i = 1; i <= k - 3 - i; ++i) {
            // 長さの和がk-3になる組を全て試す
            for (auto t1 : T[i]) {
                for (auto t2 : T[k - 3 - i]) {
                    int v = t1 & t2;  // andを合成
                    if (U[v] == INF) {
                        U[v] = k;
                        T[k].push_back(v);
                    }

                    v = t1 ^ t2;  // xorを合成
                    if (U[v] == INF) {
                        U[v] = k;
                        T[k].push_back(v);
                    }
                }
            }
        }
    }
}

/* ----- 構文解析 ----- */
string S;
int pat;  // a, b, c, dの割り振り

bool expr(int&);

// expr^expr, expr*expr
bool bin(int& i) {
    bool ret = expr(i);
    if (S[i] == '*') {
        ++i;
        ret = expr(i) && ret;
    } else if (S[i] == '^') {
        ++i;
        ret = expr(i) != ret;
    }
    return ret;
}

// 0, 1, a, b, c, d
bool term(int& i) {
    bool ret;
    if ('0' <= S[i] && S[i] <= '1') {
        ret = S[i] - '0';
    } else if ('a' <= S[i] && S[i] <= 'd') {
        ret = (pat >> (S[i] - 'a')) & 1;
    }
    ++i;
    return ret;
}

// term, -expr, (bin)
bool expr(int& i) {
    bool ret;
    if (S[i] == '(') {
        ++i;
        ret = bin(i);
        ++i;
    } else if (S[i] == '-') {
        ++i;
        ret = !expr(i);
    } else {
        ret = term(i);
    }
    return ret;
}

/* ----- main ----- */
bool solve() {
    cin >> S;

    // 真理値表を計算
    int i, tab = 0;
    for (pat = 0; pat < (1 << 4); ++pat) {
        i = 0;
        tab += expr(i) << pat;
    }

    // 前計算で得たテーブルを参照
    cout << U[tab] << endl;
    return true;
}

構文解析にて1つ大きな注意点がある。 bin内のret = expr(i) && ret;だが、これは順番を逆にすると短絡評価によってexpr(i)が評価されないことがある。 一番確実なのは変数に格納することである。

反省

  • シンプルに実装が重くてしんどい。
  • 真理値表の数があれだけ少ないのは非自明だった。

AOJ 1619 「弁当作り」

onlinejudge.u-aizu.ac.jp

問題意訳

長さ Mのbit列が N個与えられる。 全体のXORが 0となるような部分集合の、要素数の最大値を求めよ。

制約

  •  1 \leq N, M \leq 500
  •  1 \leq NM \leq 500

考察

あることに気づけるかが鍵となる問題。 それを言ってしまうと終わりなので、まだちゃんと考えてない人は考えてから先に進むことを推奨する。








この問題の肝は「 1 \leq NM \leq 500」という制約で、ここから「 N \leq 23 M \leq 23のいずれかが成立する」ことが分かる。 これの何が嬉しいかというと、毎回 N Mのいずれかでbit全探索ができるのである。

まず N \leq 23のとき。 これは部分集合をbit全探索して 0になるか判定すればいい。 ただし最大で M = 500になるので、bitsetで入力を持つと良いだろう。

次に M \leq 23のとき。 これは dp_b =「全体のXORが bとなるような部分集合の、要素数の最大値」というbitDPで解ける。 N個配列を取るとメモリ不足が怖いので、DPテーブルを使い回すのが良いと思われる。

実装例

onlinejudge.u-aizu.ac.jp

using bits = bitset<500>;
constexpr int INF = 1 << 30;

void solve() {
    /* ----- 入力 ----- */
    int N, M;
    cin >> N >> M;

    int ans = 0;
    if (N <= 23) {
        /* ----- Nが小さいとき ----- */
        vector<bits> B(N);
        for (auto& b : B) cin >> b;

        // 部分集合を全列挙
        for (int b = 0; b < (1 << N); ++b) {
            bits pat(0);
            for (int i = 0; i < N; ++i) {
                if ((b >> i) & 1) pat ^= B[i];
            }

            // xorが0なら要素数で更新
            if (pat.none()) {
                ans = max(ans, __builtin_popcount(b));
            }
        }
    } else {
        /* ----- Mが小さいとき ----- */
        vector<int> dp(1 << M, -INF);
        dp[0] = 0;

        for (int i = 0; i < N; ++i) {
            bits s;
            cin >> s;
            int b = s.to_ulong();  // 入力を整数に変換

            vector<int> ndp = dp;
            for (int p = 0; p < (1 << M); ++p) {
                ndp[b ^ p] = max(ndp[b ^ p], dp[p] + 1);
                // bを使う場合で更新
            }
            swap(dp, ndp);
        }
        ans = dp[0];
    }
    cout << ans << endl;
}

これを投げると5.55sで通るのだが、他の人もその程度の実行時間になるらしい。 50倍かかるからそんなものか。

反省

  • 皆さん気づきましたか?僕は気づきませんでした。
  • bitsetの使い方を復習した。

Diverta 2019 2 - E 「Balanced Piles」(800)

atcoder.jp

問題

 N個の何も置かれていないマスがある。 以下の操作を繰り返すことで、全てのマスに H個のブロックが 積まれているようにしたい。

  • 積まれているブロック数の最大値を M、最小値を mとする。
  •  m個のブロックが積まれているマスを1つ選び、 M個以上 M + D個以下になるように正の数だけブロックを積む。

このような積み方の総数を求めよ。

制約

  •  1 \leq N \leq 10^6
  •  1 \leq D \leq H \leq 10^6

考察

※以下を読む前に、pekempeyさんのブログがとても分かりやすいので そちらを先に読むことをオススメします。

pekempey.hatenablog.com


本番では「ブロック数の最大値が鍵なんだろうなぁ」と思いながら何とかして状態をまとめようとしたが、「最小の山の数」を使うのにどうしても全ての山のブロック数を持つ必要があって行き詰まってしまった。

この発想自体は近いというか逆で、解法は操作を「最小の山から1つ選んで積む」のではなく、「最小の山に積んだ後、最大の山のうちどこに挿れるか選ぶ」と見る、というものだった。 つまり、積んでしまった時点で後で選ぶときの優先順位を決めてしまうのである。 これなら保持するべきは「最大の山の数」になり、全ての山のブロック数を持つ必要がなくなる。


まず、操作中に一度は積まれることになるブロック数の集合を A ( 0, H \in A, 0-indexed)とし、 K = |A|とする。 この K種類の数は、間隔が D以下でないといけない。 そして dp'_{k, l}を「ブロック数の最大値が A_kで、そのような山の数が l個となるような操作数」とする( 1 \leq k \leq K - 1, 1 \leq l \leq N)。 この数列の漸化式を考えると、以下のようになる。

 \displaystyle dp'_{k + 1, 1} = \sum_{l = 1}^{N} dp'_{k, l}  \\
dp'_{k, l + 1} = (l + 1) dp'_{k, l}

これを整理すると、 dp'_{k + 1, 1} = dp'_{k, 1} \sum_{l = 1}^{N} l!という式が得られる。以降 F = \sum_{l = 1}^{N} l!とする。


次に、 dp_{h}の定義を「ブロック数の最大値が hで、そのような山の数が1個となるような操作数」とする。上の漸化式を利用すると、以下のような漸化式が求まる。

 \displaystyle dp_h = F \sum_{i = \max(0, h - D)}^{h - 1} dp_i

これは dpの累積和を持つことで O(H)で埋められる。

最終的な優先順位は区別しないことから、解は dp_Hとなる(個数 Hの山が1つできたら、優先順位の高い順に Hにしていくのみ)。

最後にずっと放置していた初期条件について。 最初の優先順位は自由に決められることから dp_0 = N!としたくなる。 しかし、 dp_0から dp_hに遷移するときは上の漸化式の係数がつかない(「0個になるように積む」という操作はできないため)。 これは dp_0 = N! \cdot F^{-1}とすることで打ち消されていい感じになる。

実装例

atcoder.jp

template <int MOD> class ModInt { ... }
template <int MOD> class Combination { ... }

constexpr int MOD = 1e9 + 7;
using mint = ModInt<MOD>;
const Combination<MOD> C(1 << 20);

int main() {
    /* ----- 入力 ----- */
    int N, H, D;
    cin >> N >> H >> D;

    /* ----- 1! + ... + N! ----- */
    mint fsum = 0;
    for (int l = 1; l <= N; ++l) {
        fsum += C.fact(l);
    }

    /* ----- DP ----- */
    vector<mint> dp(H + 1, 0), dpsum(H + 1, 0);
    dp[0] = dpsum[0] = C.fact(N) / fsum;
    // dp[h] = ブロック数の最大値がhで、そのような山の数が1個となるような操作数

    for (int h = 1; h <= H; ++h) {
        dp[h] = fsum * (dpsum[h - 1] -
                        (h - D - 1 >= 0 ? dpsum[h - D - 1] : 0));
        dpsum[h] = dpsum[h - 1] + dp[h];
    }

    cout << dp[H] << endl;
    return 0;
}

反省

  • 厳しい。
  • 遷移が分かっても、初期条件周りが難しかった
  • この発想がいつか活かされることを願う。

Diverta 2019 2 - D「Squirrel Merchant」 (600)

atcoder.jp

問題

リスは今家にいて、 N個のどんぐりを持っている。 これを増やすために、今から換金所へ行こうとしている。

換金所は2つあり、 i番目の換金所では j = 1, 2, 3について 以下の操作ができる。

  • どんぐり g_{i,j}個と1gの金属 jを交換する。
    • この交換は双方向で行うことができる。

リスはこれから家→換金所1→換金所2→換金所1→家の順に移動を行い、 換金所では好きな回数だけ上の操作を行うことができる。

最後に家に着いた時点で、 リスが持ちうるどんぐりの個数の最大値を求めよ。

制約

  •  1 \leq N, g_{i, j} \leq 5000

考察

最初の換金所1→換金所2の移動について考える。

ここで、換金所2に移動したとき換金所1で手に入れた全ての金属を どんぐりに戻しても問題ない。 これはそのどんぐりをまた同じ数の金属に戻せるためである。

ここから、各操作というのは 「 g_{1, j}個のどんぐりを g_{2, j}個に変える」 と同値になる。 これは最初に持っているどんぐりを「重さ」、 得られるどんぐりを「価値」と見ることで 個数無制限ナップザックDPによって最適解が得られる (何それ?という人は蟻本のP.58を読みながら これ を通すといいと思います)。

重みの最大値を W、取引種数を Kとしたとき このDPの計算量は時間は O(WK)、空間は O(W)となる。 換金所2にいる時点で持っているどんぐりの数は高々  2.5 \times 10^7個なので、時間はともかくメモリも際どいが取れる。

ただし、DPの初期値に注意する必要がある。 単純に全部0にすると、例えば

  •  N = 3 2 \to 2で解が 2になる。
  •  N = 1 2 \to 2で解が 0になる。

みたいなことが起こる。これは取引に使わなかったどんぐりの存在を 無視しているためである。 よって「取引なしでも i個は得られる」ということで  dp_i = iと初期化するとよい。

実装例

atcoder.jp

using lint = long long;

int main() {
    /* ----- 入力 ----- */
    lint N;
    cin >> N;
    vector<vector<lint>> val(2, vector<lint>(3));
    for (auto& v : val) {
        for (auto& m : v) cin >> m;
    }

    /* ----- 取引 ----- */
    for (int i = 0; i < 2; ++i) {
        vector<lint> from = val[i], to = val[(i + 1) % 2];
        // fromで金属に変換してからtoでどんぐりに戻す

        /* ----- 個数無制限ナップザックDP ----- */
        vector<lint> dp(N + 1);
        iota(dp.begin(), dp.end(), 0LL);
        // dp[i] = どんぐりi個から得られるどんぐりの最大個数
        //         無変換でi個は確実に得られることに注意

        for (int i = 0; i < 3; ++i) {
            lint F = from[i], T = to[i];
            for (int m = 0; m + F <= N; ++m) {
                dp[m + F] = max(dp[m + F], dp[m] + T);
            }
        }
        N = dp[N];
    }

    cout << N << endl;
    return 0;
}

反省

  • 考察はとてもスムーズだったが詰めが甘かった。
    • 「99%このミスがWAの原因じゃないな」と思いながら再提出するのやめてぇ。
  • 個数無制限ナップザックDPはなぜかすんなり書ける。
  • ちなみに本番では要らない場合分けをしていた。通ったからいいけど。

Diverta 2019 2 - C「Successive Subtraction」 (500)

atcoder.jp

問題

長さ Nの整数列 Aに対して、以下の操作を長さが1になるまで繰り返す。

  •  A_i, A_jを消し、末尾に A_i - A_jを追加する。

最終的に残る値の最大値を求め、それを実現する操作列を1つ構成せよ。

制約

  •  2 \leq N \leq 10^5
  •  |A_i| \leq 10^4

考察

まず Nが小さいケースで考えてみる。  N = 3, A = \{ 1, 3, 6 \}のとき、  1 - 3 = -2, 6 - (-2) = 8で最大値 8が得られる。

これを展開してみると 6 - (1 - 3) = -1 + 3 + 6となり、 最小値はマイナスで他全部プラスのやつが作れることに気づく。 実際、 A_N - ( \cdots ((A_1 - A_2) - A_3) \cdots - A_{N - 1} ) =
-A_1 + A_2 + \cdots + A_Nで構成できることが分かる。

 A_1 + \cdots + A_Nはどう考えても作れないから、これが最大! ということで提出したらWA。 これは負の数が含まれる場合は A_1 + \cdots + A_Nが最善ではないためである (なぜこの段階で提出してしまったのか自分でも分からない)。

 Aをソートしたとき、 A_m \lt 0かつ A_{m + 1} \geq 0だったとする。 このとき上のを少し変更して  A_N - (A_1 - A_{m + 1} - \cdots - A_{N - 1}) -
A_2 - \cdots - A_mとすれば、  - A_1 - \cdots - A_m + A_{m + 1} + \cdots + A_N となって最大値が得られる。 また Aが全て正、及び全て負のケースでも これで最大値が得られることが場合分けで分かる。

実装例

atcoder.jp

int main() {
    /* ----- 入力 ----- */
    int N;
    cin >> N;
    vector<int> A(N);
    for (auto& a : A) cin >> a;
    sort(A.begin(), A.end());

    /* ----- 最大値を求める ----- */
    int sum = 0;
    for (auto& a : A) sum += abs(a);
    if (A.front() > 0) sum -= A.front() * 2;  // 全て正の場合
    if (A.back() < 0) sum += A.back() * 2;    // 全て負の場合
    cout << sum << endl;

    /* ----- 操作列の構成 ----- */
    int acc = A.front();

    // 正の要素を引く
    for (int i = 1; i < N - 1; ++i) {
        if (A[i] >= 0) {
            cout << acc << " " << A[i] << endl;
            acc -= A[i];
        }
    }

    // 正負逆転
    cout << A.back() << " " << acc << endl;
    acc = A.back() - acc;

    // 負の要素を引く
    for (int i = 1; i < N - 1; ++i) {
        if (A[i] < 0) {
            cout << acc << " " << A[i] << endl;
            acc -= A[i];
        }
    }
    return 0;
}

反省

  • いや注意力が低いなんてもんじゃない。
  • 具体例なしでパッと構成法が浮かぶようになるもんなのかね。