はまやんはまやんはまやん

hamayanhamayan's blog

Factorization [AtCoder Beginner Contest 110 D]

https://beta.atcoder.jp/contests/abc110/tasks/abc110_d

解法

https://beta.atcoder.jp/contests/abc110/submissions/3260162

数列aにすべて1を入れておく。
すべてかけてMになるためには、Mを素因数分解して、できた素因数を分配していけばいい。
まずはMを素因数分解する。
ある素因数p^mについて、m個のpをn個に分配するが、これは重複組合せで実現できる。
具体的にはnHmである。
これをすべての素因数について求めて、総積を取ると答え。

int N, M;
Comb<mint, 201010> com;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    auto ep = enumpr(M);
 
    mint ans = 1;
    fore(p, ep) ans *= com.nHk(N, p.second);
    cout << ans << endl;
}

String Transformation [AtCoder Beginner Contest 110 C]

https://beta.atcoder.jp/contests/abc110/tasks/abc110_c

解法

https://beta.atcoder.jp/contests/abc110/submissions/3256344

操作を考えてみると、自由度が高そうな感じがある。
任意の文字を別の文字に変えることはできそう。
しかし、ある文字を文字列中に存在する他の文字に変換することだけできない。
よって、文字毎に数を集計して、その数が集合として等しいなら、一致させることができる。
集合として等しいかを確認したいときは、ソートした列を比較すればいい。
vectorは比較関数があるので、そのまま比較できる。
f(s) := 文字列sをハッシュ化する関数

string S, T;
//---------------------------------------------------------------------------------------------------
vector<int> f(string s) {
    map<char, int> m;
    fore(c, s) m[c]++;
    vector<int> res;
    fore(p, m) res.push_back(p.second);
    sort(all(res));
    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S >> T;
 
    if (f(S) == f(T)) printf("Yes\n");
    else printf("No\n");
}

1 Dimensional World's Tale [AtCoder Beginner Contest 110 B]

https://beta.atcoder.jp/contests/abc110/tasks/abc110_b

解法

https://beta.atcoder.jp/contests/abc110/submissions/3256117

Zを全探索する。
ZはX<Z≦Yであるため、最大200通りしか無い。
他の2つの条件のチェックもO(100)位なので、間に合う。

int N, M, X, Y, x[101], y[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> X >> Y;
    rep(i, 0, N) cin >> x[i];
    rep(i, 0, M) cin >> y[i];
 
    rep(Z, X + 1, Y + 1) {
        int ok = 1;
        rep(i, 0, N) if (x[i] >= Z) ok = 0;
        rep(i, 0, M) if (y[i] < Z) ok = 0;
        if (ok) {
            printf("No War\n");
            return;
        }
    }
 
    printf("War\n");
}

Maximize the Formula [AtCoder Beginner Contest 110 A]

https://beta.atcoder.jp/contests/abc110/tasks/abc110_a

解法

https://beta.atcoder.jp/contests/abc110/submissions/3255620

xy+zという風に配置した場合、10x+y+zという結果になる。
つまり、10倍をどこにかけて足すかという問題にすることができる。
下の解法では全てのパターンを試しているが、最大のものに10倍してやってもいい。

int A, B, C;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> A >> B >> C;
 
    int ans = 0;
    chmax(ans, A * 10 + B + C);
    chmax(ans, B * 10 + A + C);
    chmax(ans, C * 10 + A + B);
    cout << ans << endl;
}

均衡な辺削除 (Balanced Edge Deletion) [Aizu Competitive Programming Camp 2018 Day 3 E]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day3/problems/E

考察過程

1. 橋である辺と橋でない辺で挙動が分かれるのは見て分かる
2. 橋である辺を削除した場合の連結成分のコストを求めたい
3. 二重辺連結成分分解すれば良さそう
4. 分解後の成分を木として考えれば、dfsして累積和を取って連結成分のコストが求められる
5. 橋でない辺を削除したほうが最適な場合もあるので注意(その削除した辺のコストがあまりにでかい)

解法

https://onlinejudge.u-aizu.ac.jp/beta/review.html#ACPC2018Day3/3150016

二重辺連結成分分解を知っているかが重要となる問題になる。
 
二重辺連結成分分解をして、無向グラフを二重辺連結成分を頂点とした木に変換しよう。
その木について部分木のコストをsmとして累積和で求めていけば、
ある辺で切ったときの連結成分のコストの総和は求められる。
すべての辺で切る場合を試して最小コストの辺を求めよう。
 
橋で切らなくても、最小になる場合がある。
橋でない頂点について全体のコスト-辺のコストが最小になる場合もあるので、それも計算すると答え。

int N, M;
int U[101010], V[101010], W[101010];
ll cst[101010];
vector<pair<int,int>> E[101010];
//---------------------------------------------------------------------------------------------------
int dpt[101010]; ll sm[101010];
void dfs(int cu, int _dpt = 1) {
    dpt[cu] = _dpt;
    sm[cu] = cst[cu];
    fore(p, E[cu]) if (!dpt[p.first]) {
        dfs(p.first, _dpt + 1);
        sm[cu] += sm[p.first] + p.second;
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) cin >> U[i] >> V[i] >> W[i];
    rep(i, 0, M) U[i]--, V[i]--;

    BridgeSCC bs;
    bs.init(N);
    rep(i, 0, M) bs.add_edge(U[i], V[i]);
    bs.scc();

    UnionFind uf(N);
    fore(v, bs.SC) fore(i, v) uf(v.front(), i);

    ll mincst = infl;
    pair<int, int> ans = { U[0], V[0] };
    ll tot = 0;
    rep(m, 0, M) tot += W[m];
    rep(m, 0, M) if(uf[U[m]] == uf[V[m]]) {
        if (tot - W[m] < mincst) {
            mincst = tot - W[m];
            ans = { U[m], V[m] };
        }
        else if (tot - W[m] == mincst) chmin(ans, { U[m], V[m] });
    }

    if (1 < bs.SC.size()) {
        int root = 0;
        rep(m, 0, M) {
            if (uf[U[m]] == uf[V[m]]) cst[uf[U[m]]] += W[m];
            else {
                E[uf[U[m]]].push_back({ uf[V[m]], W[m] });
                E[uf[V[m]]].push_back({ uf[U[m]], W[m] });
                root = uf[U[m]];
            }
        }

        dfs(root);

        rep(m, 0, M) if (uf[U[m]] != uf[V[m]]) {
            int u = uf[U[m]], v = uf[V[m]];
            if (dpt[u] < dpt[v]) swap(u, v);
            ll uc = sm[u];
            ll vc = sm[root] - uc - W[m];

            ll cs = abs(uc - vc);
            if (cs < mincst) {
                mincst = cs;
                ans = { U[m], V[m] };
            }
            else if (cs == mincst) chmin(ans, { U[m], V[m] });
        }
    }

    printf("%d %d\n", ans.first + 1, ans.second + 1);
}

ピボット (Pivots) [Aizu Competitive Programming Camp 2018 Day 3 B]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day3/problems/B

前提知識

考察過程

1. 全然分からない
2. 参加記でリストという単語を発見
3. なるほどー
4. 双方向リスト作るんね

実装

https://onlinejudge.u-aizu.ac.jp/beta/review.html#ACPC2018Day3/3149978

双方向リストを作ろう。
クエリの処理は最高でも5つのノードを変更するだけで実現できる。
N=1のときはノードが1つになり、バグりそうな雰囲気を感じたので場合分けしてある。
あとは、実装する。
 
L[i] := ノードiの左側にあるノード
R[i] := ノードiの右側にあるノード
top := リストの先頭ノード
last := リストの末尾ノード

を用意して、適宜切り貼りしていく。
プログラムにコメントをつけたので追ってみるといいが、双方向リストを直接学んだ方が早いかもしれない。

int N, Q, A[101010];
int L[101010], R[101010];
int top, last;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) A[i]--;

    if (N == 1) {
        printf("1\n");
        return;
    }

    top = A[0];
    last = A[N - 1];
    rep(i, 0, N) {
        if (i) L[A[i]] = A[i - 1];
        else L[A[i]] = -1;

        if (i + 1 < N) R[A[i]] = A[i + 1];
        else R[A[i]] = -1;
    }

    rep(_, 0, Q) {
        int q; cin >> q; q--;

        if (q == top) { // qが先頭だったとき
            top = R[q]; // qの右側が先頭になる
            L[top] = -1; // 先頭の左側はなくなる
            R[last] = q; // 末尾にqが来るので、現在の末尾の右側はq
            L[q] = last; // qの左側は現在の末尾
            R[q] = -1; // qは末尾になるので、右側はなくなる
            last = q; // 末尾がqであることをメモ
        }
        else if (q == last) { // qが末尾だったとき
            last = L[q]; // qの左側が末尾に成る
            R[last] = -1; // 末尾の右側はなくなる
            L[top] = q; // 先頭にqが来るので、現在の先頭の左側はq
            R[q] = top; // qの右側は先頭になる
            L[q] = -1; // qの左側はなくなる
            top = q; // 先頭がqであることをメモ
        } else {
            int nxtop = R[q]; // qの右側が次の先頭になる
            int nxlast = L[q]; // qの左側が次の末尾になる

            L[q] = last; // qの右側を現在の末尾にする
            R[q] = top; // qの左側を現在の先頭にする

            L[nxtop] = -1; // 次の先頭の左側はなくなる
            R[nxlast] = -1; // 次の末尾の右側はなくなる

            L[top] = q; // 今の先頭の左側はqになる
            R[last] = q; // 今の末尾の右側はqになる

            top = nxtop; // 先頭更新
            last = nxlast; // 末尾更新
        }
    }

    int f = 1;
    rep(i, 0, N) if (L[i] < 0) top = i;
    while (0 <= top) {
        if (f) f = 0;
        else printf(" ");

        printf("%d", top + 1);
        top = R[top];
    }
    printf("\n");
}

回文部分列 (Palindromic Subsequences) [Aizu Competitive Programming Camp 2018 Day 3 G]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day3/problems/G

考察過程

1. 似たような問題設定を見たことあった
2. DEGwerさんのgreedyからの帰着で解ける
3. それで区間DPすればいけそう

解法

https://onlinejudge.u-aizu.ac.jp/beta/review.html#ACPC2018Day3/3149963

区間DPをする。
dp[L][R] := [0,L]と[R,N+1]の文字列で回分を貪欲に作ったときの組み合わせ数
ここで貪欲というのが重要。
元々作ってある回分にaaを足したい場合、Lから右にあるaのうちどれか、Rから左にあるaのうちどれか
のように自由度を高めてしまうと、重複して数える可能性が出てくる。
なので、貪欲に一番近いaを取るという風にしてしまうと、重複せず数え上げることができる。
 
なぜ重複しないのかというのが、DEGwerさんのgreedyからの帰着の話になるのだが、
ある回分があって、その回文が文字列の部分文字列として含まれるかの判定問題を考える。
その判定問題は左右から貪欲に文字を決定していけば含まれるかが分かるので、その挙動を遷移として採用するというもの。
 
遷移を書くときは事前に
go_migi[i][c] := i番目の文字から右に行って一番近い文字cがある添字
go_hidari[i][c] := i番目の文字から左に行って一番近い文字cがある添字
を累積和のような要領で作って、DPをしていく。
 
答えを数え上げるときは、遷移の最中に集計する。
if(len != N + 2) ans += dp[L][R];
これは偶数長の回分を集計している。(len=N+2のときはからの部分文字列なので排除)
if (LL <= RR) ans += dp[L][R];
これは奇数長の回分を集計している。
LL≦RRを満たすのならば(L,R)の間に該当する文字が1つはあるということなので、集計する。

string S; int N;
mint dp[2020][2020];
int go_migi[2020][26], go_hidari[2020][26];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;
    N = S.length();
    S = "#" + S + "#";

    rep(c, 0, 26) go_migi[N][c] = N + 1;
    rrep(i, N - 1, 0) {
        rep(c, 0, 26) go_migi[i][c] = go_migi[i + 1][c];
        go_migi[i][S[i + 1] - 'a'] = i + 1;
    }

    rep(c, 0, 26) go_hidari[1][c] = 0;
    rep(i, 2, N + 2) {
        rep(c, 0, 26) go_hidari[i][c] = go_hidari[i - 1][c];
        go_hidari[i][S[i - 1] - 'a'] = i - 1;
    }

    mint ans = 0;
    dp[0][N + 1] = 1;
    rrep(len, N + 2, 2) {
        rep(L, 0, N + 1) {
            int R = L + len - 1;
            if (N + 1 < R) break;

            if(len != N + 2) ans += dp[L][R];
            rep(c, 0, 26) {
                int LL = go_migi[L][c];
                int RR = go_hidari[R][c];

                if (LL <= RR) ans += dp[L][R];
                if (LL < RR) dp[LL][RR] += dp[L][R];
            }
        }
    }

    cout << ans << endl;
}