2020-05-29

TechFUL: かわいいは罪 in グラフ

TechFUL TechFUL: 上級グラフ行列行列累乗

問題概要

$N$ 頂点 $M$ 辺の重み付き無向グラフが与えられる．

$i$ 番目の辺は頂点 $a_{i}$ と頂点 $b_{i}$ を結んでおり、重みは $c_{i}$ である．

グラフは連結で、自己ループや多重辺は存在しない．

以下のクエリに答えよ．

頂点 $x$ から $t$ 本の辺を移動して頂点 $y$ に移動したとき、通った $t$ 本の辺の重みの積を「かわいい度」と定義する．頂点 $x$ から頂点 $y$ へ $t$ 本の辺を辿って着くような全ての移動方法のかわいい度の総和を求めよ．

https://techful-programming.com/user/practice/problem/coding/11282

制約

$2 \le N \le 50$
$1 \le M \le \frac{N(N - 1)}{2}$
$1 \le a_{i} \lt b_{i} \le N$
$1 \le c_{i} \le 10^{5}$
$1 \le Q \le 10$
$1 \le x_{i}, y_{i} \le N$
$1 \le t_{i} \le 10^{5}$
$(a_{i}, b_{i}) \neq (a_{j}, b_{j}) \; (i \neq j)$

考えたこと．

グラフの遷移を扱う問題なので行列累乗で解けないか考えてみる．

次のような行列を定義する．

$G_{u, v}$ := 頂点 $u$ から頂点 $v$ を繋ぐ辺が存在しないなら 0, 存在するならその辺の重み

$i$ 回の移動で頂点 $u$ に辿り着く全ての移動方法のかわいい度の総和を $dp_{i}(u)$ とする．

このとき、以下の漸化式が成り立つ．

$dp_{i+1}(v) = \sum_{1 \le u \le N} G_{u, v} \cdot dp_{i}(u)$

よって、 $dp_{i}$ を長さ $N$ の列ベクトルと考えると、

$dp_{i+1} = G \, dp_{i}$

と表せることから、 $dp_{t}$ は次の式で求められる．

$dp_{t} = G^{\,t} \, dp_{0}$

$dp_{t}$ を $dp_{0}(x) = 1, dp_{0}(*) = 0$ で上式に従って計算すれば、 $dp_{t}(y)$ が答えになる．

計算量は $O(N^{3} Q \log t)$ 時間である．

行列累乗については以下を参照．

行列累乗の解説
競技プログラミングにおけるDPの考え方 ~繰り返し２乗法と行列累乗~ - サンリオピューロランド

#include <bits/stdc++.h>
using namespace std;

using vec = vector<long long>;
using Matrix = vector<vec>;
const int MOD = 1000000007;

// 行列同士の積
Matrix mul(const Matrix& A, const Matrix& B) {
    assert(A.size() > 0 && A[0].size() == B.size());
    Matrix C(A.size(), vec(B[0].size(), 0));
    for (int i = 0; i < A.size(); ++i) {
        for (int j = 0; j < B[0].size(); ++j) {
            for (int k = 0; k < A[i].size(); ++k) {
                C[i][j] += A[i][k] * B[k][j] % MOD;
                C[i][j] %= MOD;
            }
        }
    }
    return C;
}

// 行列の累乗
Matrix pow(Matrix A, int n) {
    Matrix B(A.size(), vec(A[0].size(), 0));
    for (int i = 0; i < A.size(); ++i) {
        B[i][i] = 1;
    }
    while (n > 0) {
        if (n & 1) B = mul(B, A);
        A = mul(A, A);
        n >>= 1;
    }
    return B;
}

int N, M, Q;
Matrix G;

int main() {
    cin >> N >> M;
    G.resize(N, vec(N, 0));
    for (int i = 0; i < M; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        G[a][b] = G[b][a] = c;
    }
    cin >> Q;
    for (int i = 0; i < Q; ++i) {
        int x, y, t;
        cin >> x >> y >> t;
        x--; y--;
        cout << pow(G, t)[y][x] << endl;
    }
}

類題

R - Walk

2020-05-29

TechFUL: 春のにわとり祭り

TechFUL TechFUL: 上級ナップザック DP bit DP

問題概要

$N$ 個のドアがあり、初めは全て閉じている．

Tech ちゃんは $M$ 個の魔法を使用することができる．

$i$ 番目の魔法を使用することで、 $a_{i, 1}, \ldots, a_{i, k_{i}}$ 番目の全てのドアについて開 → 閉 / 閉 → 開を行う．

各魔法の使用には金額が $c_{i}$ 円かかる．

$i$ 番目のドアが開いていたら $d_{i}$ 円もらえる場合、最終的にもらえる利益の最大を求めよ．

https://techful-programming.com/user/practice/problem/coding/10967

制約

$1 \le N \le 10$
$1 \le d_{i} \le 10^{5}$
$1 \le M \le 10^{3}$
$1 \le c_{i} \le 10^{5}$
$1 \le k_{i} \le N$
$1 \le a_{i, 1} \le \cdots \le a_{i, k_{i}} \le N$
$a_{i, j} \neq a_{i, k} \; (j \neq k)$

考えたこと

まず、魔法を 2 回唱えると元どおりになるため、同じ魔法を 2 回以上唱える必要はない．

よって、各魔法について唱える回数は 0 or 1 回であることから、ナップザック DP による解法を考える．

また、見るからに bit DP を使いそうなので、ナップザック DP と bit DP を組み合わせた DP を考える．

ナップザック DP と bit DP の解説は以下を参照．

本問題の DP の状態の持ち方、出力、初期化は次の通りになる．

状態の持ち方

$dp(i, S)$ := 最初の $i$ 個の魔法からいくつか選び、開いているドアの集合を $S$ にするための最小金額．

出力するもの

$\max_{S} { \sum_{i \in S} d_{i} - dp(N, S) }$

初期化

$dp(0, 0) = 0$
$dp(i, j) = \infty \ (i \neq 0 \wedge j \neq 0)$

#include <bits/stdc++.h>
using namespace std;

const int INF = 1 << 30;
int N, M;
int d[11], c[2000];
int mask[2000]; // i 番目の魔法による影響を受けるドアの集合
int dp[2000][2000];

int main() {
    cin >> N;
    for (int i = 0; i < N; ++i) {
        cin >> d[i];
    }
    cin >> M;
    for (int i = 0; i < M; ++i) {
        int k;
        cin >> c[i] >> k;
        for (int j = 0; j < k; ++j) {
            int a;
            cin >> a;
            mask[i] |= 1 << (a - 1);
        }
    }

    // 初期化
    for (int i = 0; i < 2000; ++i) {
        for (int j = 0; j < 2000; ++j) {
            dp[i][j] = INF;
        }
    }
    dp[0][0] = 0;

    // DP の計算
    for (int i = 0; i < M; ++i) {
        for (int S = 0; S < 1 << N; ++S) if (dp[i][S] < INF) {
            dp[i + 1][S] = min(dp[i + 1][S], dp[i][S]);
            dp[i + 1][S ^ mask[i]] = min(dp[i + 1][S ^ mask[i]], dp[i][S] + c[i]);
        }
    }

    // 出力
    int ans = 0;
    for (int S = 0; S < 1 << N; ++S) if (dp[M][S] < INF) {
        int sum = -dp[M][S];
        for (int i = 0; i < N; ++i) if (S >> i & 1) {
            sum += d[i];
        }
        ans = max(ans, sum);
    }
    cout << ans << endl;
}

類題

E - Get Everything

2020-05-28

TechFUL: Extreme Happy!

TechFUL TechFUL: 中級二分探索二分法

問題概要

関数 $f$ が以下のように定義される．

$f(x) = a \cdot x^{2 + \log (x)} + b \cdot x + c$

$f(x)$ が最小となる $x$ の値を小数点第 5 位を四捨五入して出力せよ．

但し、最小値となる $x$ はただ一つであり、0 より大きく 100 未満の値をとることが保証されている．

制約

$a, b, c$ は実数．
$0 \lt a, x \lt 100$
$-100 \lt b, c \lt 100$
$\log (x)$ はネイピア数 $e$ を底とする自然対数である．

考えたこと

$f(x) = a \cdot x^{2 + \log (x)} + b \cdot x + c$ を微分すると $f'(x) = 2a \cdot x^{1 + \log (x)} \cdot (1 + \log (x)) + b$ となる．

$f(x)$ が最小となる $x$ の値を $x^{*}$ とする．

条件から恐らく $f(x)$ は下に凸で、 $f'(x^{*}) = 0$ が成り立つと考えられる．

$x^{*}$ の値は二分法で求めることができる．

二分法の解説：二分法とは？アルゴリズム・収束・例題 - 理数アラカルト -

#include <bits/stdc++.h>
using namespace std;

double round_n(double data, long long n) {
    double ret = data * pow(10.0, n);
    ret = (double) (long long) (ret + 0.5);
    return ret * pow(10.0, -n);
}

const double EPS = 1e-10;
double a, b, c;

double ff(double x) {
    return 2 * a * pow(x, 1 + log(x)) * (1 + log(x)) + b;
}

int main() {
    cout << fixed << setprecision(4);

    cin >> a >> b >> c;
    double lb = 0.0, ub = 100.0;
    for (int i = 0; i < 100; ++i) {
        double m = (lb + ub) / 2.0;
        if (ff(m) < -EPS) lb = m;
        else ub = m; 
    }
    cout << round_n(lb, 4) << endl;
}

類題

B - ムーアの法則

2020-05-28

TechFUL: マスクが買いたい

TechFUL TechFUL: 中級いもす法

問題概要

Tech ちゃんはお店に買い物にいく．

お店は時刻 0 ちょうどに開き、時刻 $E$ ちょうどに閉まる．

$N$ 人のお客さんの出入りのデータが与えられる．

$i$ 番目のお客さんは時刻 $S_{i}$ にお店に入り、時刻 $T_{i}$ にお店を出る．

お客さんが最も少ない時間を出力せよ．

制約

$0 \lt E \le 2 \times 10^{5}$
$0 \le N \le 10^{5}$
$0 \le S_{i} \le T_{i} \le E$

解法

各時間帯におけるお客さんの人数をいもす法を用いて求め、お客さんが最も少ない時間帯を列挙する．

いもす法の解説：いもす法 - いもす研 (imos laboratory)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int E, N;
    cin >> E >> N;
    vector<int> cum(E + 1, 0);
    for (int i = 0; i < N; ++i) {
        int S, T;
        cin >> S >> T;
        cum[S]++;
        cum[T]--;
    }
    for (int i = 0; i < E; ++i) {
        cum[i + 1] += cum[i];
    }
    int num = N;
    for (int i = 0; i < E; ++i) {
        num = min(num, cum[i]);
    }
    for (int i = 0; i < E; ++i) {
        if (cum[i] == num) {
            cout << i << " ";
        }
    }
    cout << endl;
}

2020-05-28

TechFUL: Fair or UnFair

TechFUL TechFUL: 中級貪欲法

問題概要

Tech ちゃんと FUL ちゃんは $2 \times N$ 枚のカードを用いて遊ぶことにした．

$i$ 枚目のカードには数字 $a_{i}$ が書かれている．

Tech ちゃんと FUL ちゃんは交互にデッキから好きなカードを 1 枚ずつ取り出す．

デッキがなくなったとき、Tech ちゃんと FUL ちゃんはカードを $N$ 枚ずつ持っている．

Tech ちゃんと FUL ちゃんは $N$ 回のラウンドでカードの数字の大きさ比べを行う．

より大きい数字を出した方が勝ちであり、同じ数字であれば引き分けとなる．

毎回のラウンドで Tech ちゃんが先にカードを出すとき、FUL ちゃんの勝利回数の最大値を求めよ．

但し、Tech ちゃんと FUL ちゃんが自分の勝ちを最大化できるよう最善を尽くすものとする．

制約

$1 \le N \le 10^{5}$
$1 \le a_{i} \le 10^{5}$

考えたこと

数字が大きいカードが有利なので、Tech ちゃんと FUL ちゃんがデッキから選ぶカードは一意に決まる．

具体的には、 $2 \times N$ 枚のカードを大きい順に交互に選択する．

Tech ちゃんが選んだカードを大きい順に $T_{1}, T_{2}, \ldots, T_{N}$ とする．

また、FUL ちゃんが選んだカードを大きい順に $F_{1}, F_{2}, \ldots, F_{N}$ とする．

$i_{1}$ を $T_{i_{1}} \lt F_{1}$ を満たす 1 以上 $N$ 以下の最小のインデックスとする．

Tech ちゃんがカード $T_{i_{1}}$ を出すとき、FUL ちゃんは $F_{1}$ を出すのが最適である．

続いて、 $i_{2}$ は $T_{i_{2}} \lt F_{2}$ を満たす $i_{1} + 1$ 以上 $N$ 以下の最小のインデックスとする．

Tech ちゃんがカード $T_{i_{2}}$ を出すとき、FUL ちゃんは $F_{2}$ を出すのが最適である．

同様にして、FUL ちゃんが $F_{3}, F_{4}, \ldots$ を出すのが最適であるような Tech ちゃんのカードを求めることができる．

下図を例にすると、

$i_{1} = 2$ より、Tech ちゃんが $T_{2} = 5$ を出すとき、FUL ちゃんは $F_{1} = 6$ を出すべきである．
$i_{2} = 3$ より、Tech ちゃんが $T_{3} = 4$ を出すとき、FUL ちゃんは $F_{2} = 5$ を出すべきである．
$i_{3} = 5$ より、Tech ちゃんが $T_{5} = 1$ を出すとき、FUL ちゃんは $F_{3} = 4$ を出すべきである．
$i_{4} = 6$ より、Tech ちゃんが $T_{6} = 1$ を出すとき、FUL ちゃんは $F_{4} = 2$ を出すべきである．
Tech ちゃんが $T_{1} = 7, T_{4} = 4$ を出すとき、FUL ちゃんは $F_{5} = 1, F_{6} = 1$ から適当に出せばいい．

f:id:legosuke_prog:20200528094157p:plain

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> a(2 * N);
    for (int i = 0; i < a.size(); ++i) {
        cin >> a[i];
    }
    sort(a.begin(), a.end(), greater<int>());
    vector<int> T, F;
    for (int i = 0; i < N; ++i) {
        T.push_back(a[2 * i]);
        F.push_back(a[2 * i + 1]);
    }
    int ans = 0, i = 0, j = 0;
    while (i < N && j < N) {
        if (T[i] < F[j]) {
            j++;
            ans++;
        }
        i++;
    }
    cout << ans << endl;
}

2020-05-28

TechFUL: 文字変化(Easy)

TechFUL TechFUL: 初級

問題概要

英語の小文字からなる長さ $L$ の文字列 $S$ が与えられる．

Tech ちゃんはこの文字列の $i$ 番目 $(1 \le i \le | S |)$ の文字 $S_{i}$ に対して次の二つの操作を行うことができる．

操作 A : 1 ポイントを使用して、文字 $S_{i}$ を辞書順に一つ次の文字に変化させる．z の一つ次の文字は a である．

操作 B : 1 ポイントを使用して、文字 $S_{i}$ を辞書順に一つ前の文字に変化させる．a の一つ前の文字は z である．

文字列 $S$ から文字列 $T$ に変化させるのに必要な最小ポイントを求めよ．

制約

$1 \le L \le 10^{5}$
$| S | = | T | = L$
$S, T$ は英子文字からなる文字列．

解法

文字 $S_{i}$ を $T_{i}$ に変化させる方法として、操作 A のみを繰り返すか、操作 B のみを繰り返すかの二通りのみを考えればいい．

$S_{i}, T_{i}$ の辞書順における番号をそれぞれ $s, t$ とする．

$s \le t$ のとき、

操作 A のみを繰り返す場合の操作回数は $t - s$ 回．
操作 B のみを繰り返す場合の操作回数は $26 + s - t$ 回

$s \gt t$ の場合も同様に求められる．

#include <bits/stdc++.h>
using namespace std;

int main() {
    int L;
    string S, T;
    cin >> L >> S >> T;
    int ans = 0;
    for (int i = 0; i < L; ++i) {
        if (S[i] > T[i]) swap(S[i], T[i]);
        ans += min(T[i] - S[i], 26 + S[i] - T[i]);
    }
    cout << ans << endl;
}

2020-05-28

TechFUL: TechちゃんとFULちゃんのおねだり

TechFUL TechFUL: 初級最小公倍数

問題概要

Tech ちゃんは 1 個 $A$ 円のジュースを、FUL ちゃんは 1 個 $B$ 円の板チョコを買いたい．

Tech ちゃんと FUL ちゃんはお金を持っていないため、お母さんからお小遣いを貰おうとした．

二人に対し、お母さんは次の3つの条件を満たすようなお小遣いを渡すと言った．

Tech ちゃんと FUL ちゃんには同じ金額のお小遣いを渡す．
Tech ちゃんと FUL ちゃんのそれぞれが必ず全ての金額をちょうど使い切れるだけのお小遣いを渡す．
お小遣いの金額は $C$ 円以下．

お小遣いの通り数を求めよ．

制約

$1 \le A, B, C \le 10^{5}$

解法

$x$ を条件 1 と 2 を満たす最小のお小遣いの金額とする．

このとき、 $x$ は $A, B$ の最小公倍数となる．

最大公約数・最小公倍数の解説：AtCoder 版！マスター・オブ・整数 (最大公約数編) - Qiita

条件 1, 2, 3 を満たすお小遣いは $xk$ 円で表せる．

$k$ の範囲は $1 \le k \le \left\lfloor \frac{C}{x} \right\rfloor$ である．

#include <bits/stdc++.h>
using namespace std;

int main() {
    int A, B, C;
    cin >> A >> B >> C;
    cout << C / lcm(A, B) << endl;
}