2020-10-19

ICPC国内予選2014E: 橋の撤去/Bridge Removal

グラフ最大最小木の直径影響の大きさを考える貪欲法

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1196&lang=ja

問題

$N$ 頂点 $N-1$ 辺からなるグラフ(つまり木)が与えられる。
最初、好きな島に居るとして繰り返し以下のいずれかの操作が可能。

今いる頂点の隣の頂点に移動する。
今いる頂点に生えている辺を削除する。

ただし、いずれの操作も辺の重み $d$ だけのコストがかかる。
全ての辺を削除するのに必要な最短時間を求めよ。

解法

まず、下のような部分木について考えると全ての辺を削除するのに葉に行く必要は無いことと、合計で3回の操作が必要な辺が存在することがわかります。
また、この時点ではほとんどの辺には3回の操作が必要ではないかという予感がします。(後に外れます)

f:id:kadomachi_noiri:20201019184504p:plain

もう少し考察を進めるために、先ほどの図では無視していた右側の部分木を付け加えて考えると、適当に選んだPathに含まれる辺は2回の操作で済む事がわかります。

f:id:kadomachi_noiri:20201019190213p:plain

以上の考察より次の事実がわかります。

葉となっている頂点から生えている辺は1回の操作で済む。
葉では無い頂点uを始点に、頂点vを終点にもつPathに含まれる辺は2回の操作で済む。
上記以外の辺は3回の操作で削除できる。

ここまで来ると、どんな頂点をu, vとして選べばよいかが気になります。出来るだけ得をしたいのでuとvの距離 $dist(u, v)$ が大きいとうれしいです。
制約が小さいのでuとvを総当りしても良いですが、 $dist(u, v)$ が最大は木の直径だということに気づけます。(ググると良い記事がいっぱいあります！)
頂点u, vは葉では無い事を上で断っていることに注意すると、葉を取り除いた後のグラフの直径を求めれば良い事がわかります。

よって、これまでの事をまとめると答えは次の式で表せます。
$Ans = 3\times (全ての辺の和) - (直径となるPathに含まれる辺の和) - 2\times(葉から生えている辺の和)$

実装

実装についての話をメモ書き程度ですが書いておきます。(自分用なのでちょっと適当かも、パッとコードが読めないんですよね・・・悲しい・・・)
まず、重みつきグラフを受け取ります。その際にまとめて辺の和を3倍したものを求めてしまいます。
次に、葉を削除します。葉は次数1の頂点のことなので簡単に見つける事が出来ます。ついでに葉に繋がった辺を2倍して引いてあげます。
あとは削除した頂点がスタート地点では困るので、スタート地点をいい感じにしてdouble sweepで直径を求めます。
(適当選んだ頂点sから一番遠い頂点uを調べて、今度は頂点uから一番遠い頂点vを見つけると、u, vが直径になってるってやつです。)
最後に、直径を答えから引いたら考察の最後に書いた式を計算できています。無事終了です。

コード

AIZU ONLINE JUDGE: Code Review

using P = pair<int, int>;
const int INF = 1e9;

int n;
vector<vector<P>> G;
vector<int> leaves;


vector<int> calc_distance(int start) {
    vector<int> dist(n, INF);
    dist[start] = 0;

    function<void(int, int)> dfs = [&](int v, int p) {
        for (auto x : G[v]) {
            int nv = x.first;
            int w = x.second;
            if (nv == p) continue;
            if (!leaves[nv]) {
                dist[nv] = dist[v] + w;
                dfs(nv, v);
            }
        }
    };
    dfs(start, -1);

    return dist;
}


void solve() {

    int ans = 0;

    vector<int> tmp(n - 1);
    for (int i = 0; i < n - 1; i++) cin >> tmp[i];

    //重みつきグラフを受け取る
    G.assign(n + 1, vector<P>());
    for (int i = 1; i < n; i++) {
        int w; cin >> w;
        int to = tmp[i-1] - 1;
        ans += 3 * w;
        G[i].push_back(P{ to, w });
        G[to].push_back(P{ i, w });
    }

    //葉を除去する
    leaves.assign(n, 0);
    for (int i = 0; i < n; i++) {
        if (G[i].size() == 1) {
            leaves[i] = 1;
            ans -= 2 * G[i][0].second;
        }
    }


    //すでに除去した頂点がスタート地点になっているとき変更する
    int start = 0;
    while (leaves[start]) {
        start++;
    }


    //startから一番遠い点uを求める
    int u = start;
    auto dist_u = calc_distance(start);
    for (int i = 0; i < n; i++) {
        if (!leaves[i] && dist_u[i] > dist_u[u]) u = i;
    }

    //uから一番遠い点vを求める
    int v = start;
    auto dist_v = calc_distance(u);
    for (int i = 0; i < n; i++) {
        if (!leaves[i] && dist_v[i] > dist_v[v]) v = i;
    }
    
    //uとvの距離(木の直径)
    int diameter = dist_v[v];
    ans -= diameter;

    cout << ans << endl;
}


int main() {
    while (1) {
        cin >> n;
        if (n == 0) break;
        solve();
    }
}

2020-10-14

D. String Deletion

貪欲法文字列ランレングス

Educational Codeforces Round 96 (Rated for Div. 2) https://codeforces.com/contest/1430/problem/D

問題

0と1で構成された文字列 $S$ が与えられる。
$S$ に対して2stepからなる操作を何回か適用することを考える。

$S[i$ ]を選んで削除する。ただし $(0 \leqq i \leqq |S|)$ である。
$|S|$ が0で無いならば、 $S$ の先頭から同じ文字が連続しているカタマリを削除する。

上記の操作を最大で何回行えるか求めよ。

解法

先頭の連続したカタマリを $S$ のPrefixと呼ぶ事とする。
最大回数行うためには、1回の操作で出来るだけ文字を消さないようにすれば良いことがわかる。
まず、Prefixは、操作を行うと必ず消えてしまうので $S[i$ ]を選んで消すときにPrefixに含まれる場所を選んで消せばPrefixだけを消すだけ済む。
上だけでは、Prefixが1の場合に困ってしまう。次に考えるのは、 $S[i$ ]を選んだときに別のカタマリから借りてくることである。ここで、安易にPrefixを削除しないのは、100001のような場合にPrefixを削除してしまうと無駄に文字を消してしまうからである。先ほど述べたように削除する要素 $S[i$ ]を別のカタマリから借りてくれば削除する文字はPrefix(length = 1)と $S[i$ ]の2文字だけである。
しかし、よくよく考えると101010のような、別のカタマリから借りてくると損をする場合が存在する。このような場合では、末尾を削除するのが最適である(先頭でも良いが実装では末尾を選択した)。というのも、この場合で末尾および先頭以外を削除すると11010(i=1を削除)のようにPrefixが大きくなってしまって余計に文字を削除してしまうからである。
以上より、この問題は貪欲法で解けます。

実装では、連続するカタマリのサイズを前計算することで処理をやりやすくしている。
先頭より後ろのサイズが2以上のカタマリをqueueに追加している。
後は、順番に前から見ていって、prefixが1より大きかったらprefixのみを削除、prefixが1だったら他のカタマリから借用している。
また、queueの先頭がprefixとなっている場合もしくは1の時はpopしてひとつ後ろのカタマリをqueueの先頭としている。
残りは、上の考察と同じです。

コード

https://codeforces.com/contest/1430/submission/95345916

void solve(){
    int n;
    string s;
    cin >> n >> s;
 
    vector<int> v;
    char cur = s[0];
    int left = 0;
    rep(i, n) {
        if (cur != s[i]) {
            v.push_back(i - left);
            cur = s[i];
            left = i;
        }
    }
    v.push_back(n - left);
 
    queue<int> borrow;
    for (int i = 1; i < v.size(); i++) {
        if (v[i] >= 2) borrow.push(i);
    }
 
    int ans = 0;
    int last = v.size() - 1;
    rep(i, v.size()) {
        if (v[i] == 0) {//empty!
            break;
        }
 
 
        //借りてるidxがprefixになったら外す, 次のに付け替える
        int idx;
        if (borrow.size() != 0) idx = borrow.front();
        if (borrow.size() != 0 && idx == i) {
            borrow.pop();
            if (borrow.size() != 0) idx = borrow.front();
        }
 
        if (v[i] >= 2) {//prefixが2以上
        }
        else if (borrow.size() != 0) {//借りれる
            v[idx]--;
            if (v[idx] == 1) borrow.pop();//これ以上借りれない
        }
        else {//借りる相手がいないので末尾から取る
            if (v[last] < 1) last--;
            v[last]--;
        }
 
        ans++;
    }
    
 
    cout << ans << endl;
}
 
int main() {
    int t;
    cin >> t;
    rep(i, t) solve();
}

2020-10-14

E. Directing Edges

トポロジカルソートグラフ有向グラフグラフの構築

Codeforces Round #656 (Div. 3)

https://codeforces.com/contest/1385/problem/E

問題

$n$ 頂点 $m$ 辺のグラフが与えられる。
ここで、与えられる辺は、有向辺または無向辺のどちらかである。
無向辺に向きを付けることで、DAGを構成できるかどうか判定せよ。
判定できる場合は、構成したDAGの辺を出力しなさい。

解法

まず、元のグラフから無向辺を全て取り除いた有向グラフ $H$ を生成します。
次に、 $H$ をトポロジカルソートします。トポロジカルソート出来る条件は、DAGであることなので、もし失敗したら $H$ にはサイクルが存在しますから無向辺の向き付けをどんなに頑張ってもDAGを構成することは出来ません。
逆にトポロジカルソートが成功した場合は、必ず構成できます。この事実は下の図を見れば直感的に理解できると思います。

f:id:kadomachi_noiri:20201014063505p:plain

コード

https://codeforces.com/contest/1385/submission/95461303

using P = pair<int, int>;
vector<vector<int>> G;

vector<int> color;//0:未訪問, 1:保留, 2:決定済み
vector<int> res;
bool cycle = false;

void dfs(int v) {
    if (color[v] == 1) cycle = true;
    if (color[v] == 2 || cycle) return;

    //訪問したが頂点集合に加えられていないためステータスを保留とする
    color[v] = 1;

    for (auto nv : G[v]) {
        dfs(nv);
    }

    //帰りがけに頂点を加え、決定済みとする
    color[v] = 2;
    res.push_back(v);
}


void solve(){
    int n, m;
    cin >> n >> m;

    vector<P> ans;

    vector<P> E; //無向辺
    G.assign(n, vector<int>());

    rep(i, m) {
        int typ, a, b;
        cin >> typ >> a >> b;
        a--; b--;
        if (typ == 1) {
            G[a].push_back(b);
            ans.push_back(P{ a, b });
        }
        else {
            E.push_back(P{ a, b });
            E.push_back(P{ b, a });
        }
    }

    //有向グラフGをトポロジカルソート
    color.assign(n, 0);
    res = vector<int>();
    cycle = false;
    rep(i, n) {
        dfs(i);
    }
    reverse(all(res));

    if (cycle) {
        cout << "NO" << endl;
        return;
    }


    //頂点をトポロジカルソートしたときの順番
    map<int, int> ord;
    rep(i, n) ord[res[i]] = i;


    //後ろから前に向かって辺を向き付け
    for (auto e : E) {
        if (ord[e.first] < ord[e.second]) ans.push_back(P{ e.first, e.second });
    }

    //答えを出力
    cout << "YES" << endl;
    for (auto p : ans) cout << p.first + 1 << " " << p.second + 1 << endl;
}

int main() {
    int t;
    cin >> t;
    rep(i, t) solve();
}

2020-10-09

D. a-Good String

再帰的定義全探索文字列

Codeforces Round #656 (Div. 3)

https://codeforces.com/contest/1385/problem/D

問題

長さ $2^k$ の文字列 $S$ が与えられるので、 $i$ 番目の文字を任意の文字に置き換える操作を何度か行うことでa-goodな文字列にできる最小の操作回数を求める。
ここで、c-goodであるとは次の条件の内どれかを満たす事である。

長さ1の文字列
前半部が文字cのみで構成され、後半部は(c + 1)-goodである。
後半部が文字cのみで構成され、前半部は(c + 1)-goodである。

解法

c-goodの条件を眺めると再帰的定義であることに気がつく。
これは、半分をaに統一すると、もう半分はb-goodにならなければならない。今度は、半分の半分をbに統一するともう半分は、c-goodに....という風に1文字になって分割できなくなるときまで続くことからわかる。
次に制約を眺めてみると再帰木の葉の総数は高々 $10^5$ 程度であることがわかるので、全探索をすれば良い事がわかる。

実装についてだが、葉に達したときにansをcostで更新するようにした。
再帰関数を呼び出すときは、左半分を文字cで統一したときにかかるコストをdiff1として、右半分に対して潜るような実装をしている。右半分を統一したときはその逆である。
また、文字cで統一したときのコストは、累積和を計算しておき、(区間の長さ)から(区間に存在するcの総数)の差をとることで高速に求めることが出来る。
今回、区間の分割の仕方は、(左半分) = [left, mid], (右半分) = [mid+1, right]のようにした。また、累積和は、左端が閉じていて、右端が開いているという実装にした。

コード

https://codeforces.com/contest/1385/submission/94952181

int n;
string s;
vector<vector<int>> c;
int ans = INF;

void rec(char x, int left, int right, int cost) {
    if (left == right) {
        chmin(ans, cost + (s[left] != x));
        return;
    }

    int mid = left + (right - left) / 2;
    
    int diff1 = (mid - left + 1) - (c[x - 'a'][mid + 1] - c[x - 'a'][left]);
    int diff2 = (right - mid) - (c[x - 'a'][right + 1] - c[x - 'a'][mid + 1]);

    
    rec(x+1, left, mid, cost + diff2);    
    rec(x+1, mid + 1, right, cost + diff1);
}



void solve() {
    cin >> n >> s;

    ans = INF;
    c = vector<vector<int>>(26, vector<int>(n+1));

    rep(i, n) {
        int t = s[i] - 'a';
        c[t][i + 1]++;
    }
    rep(i, 26) {
        rep(j, n) c[i][j + 1] += c[i][j];
    }

    rec('a', 0, n - 1, 0);

    cout << ans << endl;
}

int main() {
    int t;
    cin >> t;
    rep(i, t) solve();
}

2020-10-09

E1. Weights Division (easy version)

グラフプライオリティキュー変化量を考える貪欲法影響の大きさを考える

Codeforces Round #661 (Div. 3)

https://codeforces.com/contest/1399/problem/E1

問題

頂点1を根とする $n$ 頂点からなる木が与えられる。また、各辺には重み $w_i$ が付けられている。
操作を1度行うたび、任意の重みを $\lfloor \frac{w_i}{2} \rfloor$ に更新することが出来る。
根から葉へのパスの重みの総和を $s$ 以下にするには、最低で何回操作を行えば良いか求める。

解法

まず、根から葉に行くまでに通った各辺を通った回数を $cnt_i$ とし、各辺におけるスコアを $w_i \times c_i$ と定義する。
また、ある辺に対して操作を行ったときの変化量を $d=w_i \times c_i - \lfloor \frac{w_i}{2} \rfloor \times c_i$ とする。
プライオリティーキューに全ての辺の変化量を入れておき大きい順に $w_i$ を更新していけばよい。

各辺を通った回数は、dfsの帰りがけ順に計算していけばよい。
具体的には、各辺に番号 $id$ を振っておき、今見ている辺の親の辺 $pid$ に $cnt_{id}$ を加えていくとよい。

コード

https://codeforces.com/contest/1399/submission/94948972

using P = pair<ll, ll>;
vector<vector<P>> G;

vector<ll> cnt, w;

void dfs(int v, int pid) {
    if (G[v].size() == 1 && pid != -1) {
        cnt[pid] = 1;
    }

    for (auto nv : G[v]) {
        int id = nv.second;
        if (id == pid) continue;

        dfs(nv.first, id);
        if (pid != -1) cnt[pid] += cnt[id];
    }
}



ll get_diff(int id) {
    ll diff = w[id] * cnt[id] - (w[id] / 2) * cnt[id];
    return diff;
}


void solve() {
    ll n, s;
    cin >> n >> s;

    G.assign(n, vector<P>());
    cnt.assign(n - 1, 0);
    w.assign(n - 1, 0);

    rep(i, n - 1) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        G[a].push_back(P{ b, i });
        G[b].push_back(P{ a, i });
        w[i] = c;
    }

    dfs(0, -1);


    priority_queue<P> que;
    ll sum = 0;

    rep(i, n - 1) {
        ll diff = get_diff(i);
        que.push(P{ diff, i });
        sum += cnt[i] * w[i];
    }

    int ans = 0;

    while (sum > s) {
        int id = (que.top()).second;
        que.pop();
        sum -= get_diff(id);
        w[id] /= 2;
        que.push(P{ get_diff(id), id });
        ans++;
    }

    cout << ans << endl;
}


int main() {
    int t;
    cin >> t;
    rep(i, t) solve();
}

2020-10-09

模擬国内2018E: 分割統治

グラフ幅優先探索彩色問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2885&lang=jp

問題

色A, B, C で与えられたグラフを次の条件を満たすように彩色する問題を考える。

AとBで彩色された頂点は、辺で直接繋がっていない。
同じ色で彩色された頂点は、辺で直接繋がっていない。
Aで彩色された頂点とBで彩色された頂点の個数は等しい。

以上の条件を満たして彩色できるとき、Aで彩色できる頂点の数を列挙する。

解法

一見、取っ掛かりが無いので1頂点選んでAで彩色してみます。(AはCに比べて条件が厳しいので, 別にBでもいいです)
すると隣接する頂点は、全てCで塗らなければならないことがわかります。
次に、Cで彩色した頂点に隣接する未彩色の頂点について考えると、AかBで彩色出来ることがわかります。
また、AとBの彩色数は等しいことが要求されていたことを思い出すと次は、Bで彩色したくなります。

ここで、AとBを同一視した色Dを考えます。すると、Cに隣接する頂点はDに彩色され、Dに隣接する頂点はCに彩色されることになります。
つまり、開始地点の色を決定すると全ての頂点の彩色状態が決定するような問題だということがわかります。
また、このことから彩色状態は高々2パターンしか存在しないということもわかりました。

先ほど考えた色Dの中で辻褄が合うように塗り分ければよいので、Aで彩色した後はBで、Bで彩色した後はAで彩色していけば良い事がわかります。

以上を適当な点を始点とした幅優先探索を利用して実現すれば計算量も十分に間に合いそうです。
ただし、3つの頂点が3つの頂点でサイクルを形成しているようなグラフなどは、条件2に触れてしまうので、彩色したあとのグラフに対して別途チェックを書く必要があります。

コード

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4899936#1

int n, m;

void solve() {
    vector<vector<int>> G(n, vector<int>());
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    function<int(int, int)> bfs = [&](int start, int init_color) {
        queue<int> que;
        que.push(start);
        vector<int> color(n, -1);
        color[start] = init_color;

        int x = 0, y = 0;
        if (init_color == 1) x++;

        while (que.size() != 0) {
            int v = que.front();
            que.pop();

            for (auto nv : G[v]) {
                if (color[nv] != -1) continue;

                if (color[v] == 0) {
                    if (x == y) x++;
                    else y++;
                    color[nv] = 1;
                }
                else {
                    color[nv] = 0;
                }

                que.push(nv);
            }
        }


        int ret = x;
        for (int i = 0; i < n; i++) {
            for (auto nv : G[i]) {
                if (color[i] == color[nv]) ret = -1;
            }
        }

        if (x != y) ret = -1;

        return ret;
    };

    set<int> ans;
    int res = bfs(0, 0);
    if (res != -1) ans.insert(res);
    res = bfs(0, 1);
    if (res != -1) ans.insert(res);

    cout << ans.size() << endl;
    for (auto x : ans) cout << x << endl;
}


int main() {
    while (1) {
        cin >> n >> m;
        if (n == 0 && m == 0) break;
        solve();
    }
}

2020-10-07

模擬国内2017C: クイズ

sort 最大最小計算結果の最適な方をとる

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2825

問題

参加者 $n$ 人、問題数 $m$ 問のクイズ大会を考える。また、 $i$ 問目の問題の得点は $s_i$ である。
このクイズ大会では、 $i$ 問目に正解する可能性がある参加者が $k_i$ 人おり、それぞれ $c_i$ であることがわかっている。
この設定で、 $m+1$ 問目の得点をその時点でどのような得点状況でも正解すれば逆転できるように設定する。
そのような得点の最小値を出力する。

解法

それぞれの人に対して、その人が取り得る得点の最小値と最大値を計算しておく。
そのような配列を $ma$ , $mi$ として、あわせて誰の得点なのかも保持しておく。
計算方法としては、

最小 → 出来るだけ正解しない、候補が自分1人のときはしょうがないので正解する。
最大 → 出来るだけ正解する。

を愚直にやれば良い。

最後に $Max\{ma\} - Min\{mi\} + 1$ とすれば答えが出るのだが、最大値と最小値の保持者が同じときに注意が必要であり、このとき、 $Max \{ ma[0] - mi[1], ma[1] - mi[0] \} + 1$ のようにする必要がある。

コード

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4896138#1

int n, m;

void solve() {
    using P = pair<int, int>;

    vector<P> ma(n), mi(n);
    for (int i = 0; i < m; i++) {
        int s, k;
        cin >> s >> k;
        for (int j = 0; j < k; j++) {
            int id; cin >> id;
            if (k == 1) mi[id-1].first += s;
            ma[id-1].first += s;
        }
    }

    for (int i = 0; i < n; i++) {
        ma[i].second = i;
        mi[i].second = i;
    }

    sort(ma.rbegin(), ma.rend());
    sort(mi.begin(), mi.end());

    int ans = ma[0].first - mi[0].first;
    if (ma[0].second == mi[0].second) {
        //ここはmaxです(戒め)
        ans = max(ma[0].first - mi[1].first, ma[1].first - mi[0].first);
    }

    cout << ans + 1 << endl;
}