AtCoder Regular Contest 033 C - データ構造

問題

 数の集合Sに対する以下のクエリを処理せよ。

  • タイプ1 : Sに数Xを追加する。
  • タイプ2 : Sに含まれる数のうちX番目に小さい数を答え、その数をSから削除する。

解法

 「X番目に小さい数⇔それ以下の数がX個以上追加されている数のうち最も小さい数」と考え、ある数以下の数がS内にいくつあるかを高速に取得できれば二分探索で答えるべき数を求めることができる。これはセグメント木を使うことにより実装が可能であり、タイプ1である数が登場した際の操作、タイプ2において累積和を求める操作を各O(\log{N})で行えるためこの問題が解けた。

反省

 ここ数日、あまり机に向かう時間は取れなかったが移動中などにこの問題を考えていて、計数時間は考えたと思うが解けなかったので解説スライドを見た。セグメント木でやっていく発想が一切出てこなかったのは猛省するべき案件で、データ構造という問題名があまりにも露骨だったのでそういう解法を捨ててしまっていた。

 セグメント木の実装は今まで何回かやってきたが、いつもセグメント木をソラで書きたいあなたにを写してばっかりで何も学びを得ていなかったため、今回はかなり自分で考えながら実装してみた。といっても見た覚えがあるのでどうしても似た書き方になってしまうが……。

 数十分かけてなんとか実装できたと思ったが、被覆関係の処理が間違っていてO(\log{N})になっておらずTLE。仕方がなく先のページを見てそこだけ参考にした。

 今までセグメント木を実装できなかったのでセグメント木を使いそうな問題に対してもそうではない解法を考えてしまっていたが、さすがに逃げ続けるわけにはいかないのでちゃんと選択肢に入れて考察していきたい。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class SegmentTree {
public:
    SegmentTree(ll n) {
        ll radicand = (ll)ceil(log2(n));
        size_ = (ll)pow(2, radicand);
        nodes_.resize(2 * size_ - 1, 0);
    }
    void add(ll x, ll v) {
        for (ll i = x + size_ - 1; ; i = (i - 1) / 2) {
            nodes_[i] += v;
            if (i == 0) {
                break;
            }
        }
    }
    ll getSum(ll a, ll b, ll k = 0, ll l = 0, ll r = -1) {
        //[a, b)の和を求める
        if (r == -1) {
            r = size_;
        }
        assert(a < b);
        assert(l < r);
        //printf("(%lld, %lld, %lld, %lld, %lld)\n", a, b, k, l, r);

        //nodes_[k]が担当する範囲が[l, r)
        if (b <= l || r <= a) {
            //被覆なし
            return 0;
        }

        if (a <= l && r <= b) {
            //完全被覆
            return nodes_[k];
        }

        //部分被覆
        ll kl = (k + 1) * 2 - 1;
        ll kr = (k + 1) * 2;
        return getSum(a, b, kl, l, (l + r) / 2) + getSum(a, b, kr, (l + r) / 2, r);
    }
private:
    ll size_;
    vector<ll> nodes_;
};

int main() {
    ll Q;
    cin >> Q;

    vector<ll> T(Q), X(Q);
    for (ll i = 0; i < Q; i++) {
        cin >> T[i] >> X[i];
    }

    constexpr ll MAX = (ll)2e5;
    SegmentTree st(MAX + 1);
    for (ll i = 0; i < Q; i++) {
        if (T[i] == 1) {
            st.add(X[i], 1);
        } else {
            ll low = 0, high = MAX + 1;
            while (low + 1 != high) {
                ll mid = (low + high) / 2;
                (st.getSum(0, mid) >= X[i] ? high = mid : low = mid);
            }
            cout << low << endl;
            st.add(low, -1);
        }
    }
}

AtCoder Regular Contest 032 C - 仕事計画

問題

 N個の仕事があり、i番目の仕事は時刻a_iに始まりb_iに終わる。時刻が重ならないようにできるだけ多くの仕事をこなすことを考えたとき、こなす仕事の種類を選び方が複数ある場合は辞書順最小のものとして構築せよ。

解法

 dp[i] := 時刻iから終了までにこなせる仕事の数及び最初にこなすべき仕事のインデックスとして後ろから求めていく。遷移は仕事を行わないときdp[i] = dp[i + 1]であり、仕事をこなすときは各仕事に対してそれを行ったときより多くの仕事がこなせるなら必ずそれを選び、同数になるなら辞書順最小のものを選ぶ、としていく。

反省

 昨日40分ほど考えて解けず、今日もまた40分ほど考えて解けず解説スライドを見て通した。

 想定解と似たような感じで各時刻iについてdp[i]を考えるというところには思い至っていたが、stringで経路を全て持とうとしてメモリが足りないことに(おそらく)なっていたり、前からdpしていくことしか考えていなかったので辞書順を上手く最小化するのがどうしても上手くいかなかった。

 forループDPを考えるときに順番を上手くやるのが苦手で、メモ化再帰で解きに行った方が可能性があったかもしれない。辞書順最小ということを考えなければ典型DPであり、なぜか典型はforループでやりたがってしまうという性質があるためそこに固執してしまった。

 解説を見てからも時刻iから始まる仕事を行わないときの遷移が間違っていて2WAほど出してしまった。どうも遷移を考える丁寧さも足りず、全体的にDPは苦手という意識が強い。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

constexpr ll MAX = (ll)1e6;

int main() {
    ll N;
    cin >> N;
    struct Job {
        ll start, end;
    };
    vector<Job> jobs(N);
    for (ll i = 0; i < N; i++) {
        cin >> jobs[i].start >> jobs[i].end;
    }

    struct Edge {
        ll to, index;
    };
    vector<vector<Edge>> edges(MAX);
    for (ll i = 0; i < N; i++) {
        edges[jobs[i].start].push_back({ jobs[i].end, i });
    }

    struct Element {
        ll cost, next;
    };
    vector<Element> dp(MAX + 1, { 0, INT_MAX });

    for (ll i = MAX - 1; i >= 0; i--) {
        //時刻iから始まる仕事を行わない
        dp[i] = dp[i + 1];

        //時刻iから始まる仕事を行う
        for (Edge j : edges[i]) {
            ll new_cost = dp[j.to].cost + 1;
            if (dp[i].cost < new_cost) {
                dp[i].cost = new_cost;
                dp[i].next = j.index;
            } else if (dp[i].cost == new_cost) {
                dp[i].next = min(dp[i].next, j.index);
            }
        }
    }

    ll ans = dp[0].cost;
    cout << ans << endl;

    ll curr_time = 0;
    for (ll i = 0; i < ans; i++) {
        cout << dp[curr_time].next + 1 << " \n"[i == ans - 1];
        curr_time = jobs[dp[curr_time].next].end;
    }
}

AtCoder Beginner Contest 109 参加ログ

結果

 10分ちょっと遅れてスタートし、24分ほどかけて全完。Dでアホみたいな2WA出してペナルティ食らったのは反省。

A - ABC333

 脳みそを使いたくなかったので愚直にやった。コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll A, B;
    cin >> A >> B;
    for (ll C = 1; C <= 3; C++) {
        if (A * B * C % 2 == 1) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}

B - Shiritori

 std::mapで2回以上出るかを数えて、あとは前のものの最後と今回の先頭文字が一致しているかを確認。コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N;
    cin >> N;
    vector<string> W(N);
    for (ll i = 0; i < N; i++) {
        cin >> W[i];
    }

    map<string, ll> mp;
    for (ll i = 0; i < N; i++) {
        if (++mp[W[i]] == 2) {
            cout << "No" << endl;
            return 0;
        }
        if (i > 0 && W[i - 1].back() != W[i].front()) {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
}

C - Skip

 x_1, \dots, x_NXを一つの配列に詰めてソートして、階差の最大公約数を取っていったものが答え。厳密には証明してないけど、まぁこれでしょという感じで解いた。コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

ll gcd(ll a, ll b) {
    return (b ? gcd(b, a % b) : a);
}

int main() {
    ll N, X;
    cin >> N >> X;
    vector<ll> x(N);
    for (ll i = 0; i < N; i++) {
        cin >> x[i];
    }
    x.push_back(X);
    sort(x.begin(), x.end());

    ll ans;
    for (ll i = 0; i < N; i++) {
        ll diff = x[i + 1] - x[i];
        if (i == 0) {
            ans = diff;
        } else {
            ans = gcd(ans, diff);
        }
    }

    cout << ans << endl;
}

D - Make Them Even

 各列について左から右へ見ていき、奇数だったら右に一個流す。最後に各行の一番右を見ていき、奇数だったら下に一個流す。間違えてa[i][j] % 2 == 0とか書いていたのと、最初に操作回数を表示することを忘れていて2回WA。コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll H, W;
    cin >> H >> W;

    vector<vector<ll>> a(H, vector<ll>(W));
    for (ll i = 0; i < H; i++) {
        for (ll j = 0; j < W; j++) {
            cin >> a[i][j];
        }
    }

    vector<ll> y, x, yy, xx;
    for (ll i = 0; i < H; i++) {
        for (ll j = 0; j < W - 1; j++) {
            if (a[i][j] % 2 == 1) {
                //右へ
                y.push_back(i + 1);
                x.push_back(j + 1);
                yy.push_back(i + 1);
                xx.push_back(j + 2);
                a[i][j]--;
                a[i][j + 1]++;
            }
        }
    }
    for (ll i = 0; i < H - 1; i++) {
        if (a[i][W - 1] % 2 == 1) {
            //下へ
            y.push_back(i + 1);
            x.push_back(W);
            yy.push_back(i + 2);
            xx.push_back(W);
            a[i][W - 1]--;
            a[i + 1][W - 1]++;
        }
    }

    cout << y.size() << endl;
    for (ll i = 0; i < y.size(); i++) {
        cout << y[i] << " " << x[i] << " " << yy[i] << " " << xx[i] << endl;
    }
}

AtCoder Regular Contest 031 C - 積み木

問題

 全て高さが違うN個の積み木が1列に並べられている。隣り合う積み木を交換する操作ができるとき、一番高い積み木から順に左右へ低くなっていくような状態へ変化させるのに必要な最小の操作回数を求めよ。

解法

 一番大きな積み木から位置を確定させていくとして、ある積み木を確定させるときには今の位置から左側、右側について自分より大きな積み木がある個数がわかれば、小さい方へ交換していけばいい。これはBinary Indexed Treeを用いることでO(\log{N})で求めることができるので、全体O(N\log{N})でこの問題が解けた。

反省

 1時間43分(0WA)でAC。最初の30分くらいは眠くて何も考えられなかった。そこからバブルソートの交換数みたいな感じで、自分より大きいものの数が重要になってくるんだろうというところまでは考察できた。一番高い積み木の位置を決めて、左右についてまず求めて、一番高い積み木の位置をずらしたときの差分を計算していくことでO(N\log{N})とかにならないかなと考えていたものの、わからなかったので1時間15分くらい経ったところで解説スライドを見た。

 BinaryIndexedTreeを知らなかったのでこのページとかを調べて実装する。1-indexというのが厄介でちょっと手間取ったりした。(i & -i)で最右ビットが求めるのすごい。

 小さい方から確定させていくというのがよくわからなくて、結局大きい方から確定させていく方針で通した。小さい方からやっていく場合BITの値を直接いじらないといけないのかな?

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class BinaryIndexedTree {
public:
    //1-indexed
    //(i & -i)はその番号が管理する区間の長さを表す
    //参考:http://hos.ac/slides/20140319_bit.pdf
    BinaryIndexedTree(ll n) : bit_(n + 1, 0) {}
    void add(ll a, ll w) {
        for (ll i = a; i < bit_.size(); i += (i & -i)) {
            bit_[i] += w;
        }
    }
    ll sum(ll a) {
        ll result = 0;
        for (ll i = a; i > 0; i -= (i & -i)) {
            result += bit_[i];
        }
        return result; 
    }
private:
    vector<ll> bit_;
};

int main() {
    ll N;
    cin >> N;
    vector<ll> B(N);
    vector<ll> index(N + 1);
    for (ll i = 0; i < N; i++) {
        cin >> B[i];
        index[B[i]] = i + 1;
    }

    BinaryIndexedTree bit(N);

    ll ans = 0;
    for (ll i = N; i >= 1; i--) {
        ll left = bit.sum(index[i]);
        ll right = N - i - left;
        ans += min(left, right);
        bit.add(index[i], 1);
    }

    cout << ans << endl;
}

SRM511 Div1 Easy - Zoo

解法

 一番身長が高いもの以外、ある数字を言う動物は1匹か2匹。0から最大値までそれ以外が出てきたらおかしく、また一度1になってから再び2になるのもおかしいのでそれも弾く。それ以外2匹のときはどっちかを選べるので×2,最後が1だったらさらに×2をすれば答えが求まる。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class Zoo {
public:
    long long theCount(vector<int> answers) {
        sort(answers.begin(), answers.end());
        vector<ll> num(answers.back() + 1, 0);
        for (int a : answers) {
            num[a]++;
        }
        ll ans = 1;
        for (int i = 0; i <= answers.back(); i++) {
            if (num[i] > 2 || num[i] <= 0) {
                //数がおかしい
                return 0;
            }
            if (i > 0 && num[i] > num[i - 1]) {
                //増えるわけはない
                return 0;
            }
            ans *= num[i];
        }
        if (num[answers.back()] == 1) {
            ans *= 2;
        }
        return ans;
    }
};

SRM510 Div2 Medium - TheLuckyGameDivTwo

解法

 最初にn以下の数字の中でLucky Numberはいくつあるかを計算しておき、両者が選べる数字の範囲について全探索すればいい。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class TheLuckyGameDivTwo {
public:
    int find(int a, int b, int jLen, int bLen) {
        vector<int> num(b + 1, 0);
        for (int i = 1; i <= b; i++) {
            num[i] = num[i - 1] + isLucky(i);
        }

        int ans = 0;
        for (int i = a; i <= b - jLen + 1; i++) {
            int tmp = INT_MAX;
            for (int j = i; j <= i + jLen - bLen; j++) {
                tmp = min(tmp, num[j + bLen - 1] - num[j - 1]);
            }
            ans = max(ans, tmp);
        }
        return ans;
    }
private:
    bool isLucky(int n) {
        for (char c : to_string(n)) {
            if (c != '4' && c != '7') {
                return false;
            }
        }
        return true;
    }
};

AtCoder Regular Contest 030 C - 有向グラフ

問題

 n頂点m辺の有向グラフが与えられる。各頂点にはアルファベットが一つ書かれている。

 このグラフを好きな頂点から任意の順番で訪問し、k個のアルファベットを回収することを考える。頂点は何度も訪問することができ、ある頂点に書かれたアルファベットは任意の訪問タイミングで回収できる。このとき回収してできる文字列として辞書順最小のものを求めよ。

解法

 強連結成分分解をしてできたグラフについてDPを行う。

反省

 3時間8分(8WA)でAC。最初は普通にDPやるだけかと勘違いして実装したが、一度取ったらなくなるのでどこ頂点から取ってあるのかを状態として持たないといけないことに提出してWA出てから気づく。そこからしばらく考えたが計1時間ほど考えてわからなかったので解説スライドを見た。

 解法を知ってからの実装が大変な問題だった。まず強連結成分分解のアルゴリズムがスライドだけではよくわからなかったので他のページなど見ながらなんとか実装していく。さらにその後のDPも結構複雑で、他人の提出を見ないとわからなかった。

 強連結成分分解を2回の深さ優先探索で実装すれば、その後のグラフを再度トポロジカルソードし直す必要はないのだろうか。自分の提出では特にそういうことをしていないので、それで通ったということはすでにトポロジカル順に並んでいる気がする(し、アルゴリズム的にもなんとなくそういう感じなんじゃないかと思われるが……)。

 ライブラリにしやすい感じで書いたので、強連結成分分解が必要な問題に当たったらこの回の自分の提出を再利用したい。以前見たことがあるのはAlien's Countingで、これも強連結成分分解してからDPという感じだったと記憶しているので、ある種の典型ではあるのだろうか。

 最終的な実装がいろいろ終わってからもループの範囲をミスってREを出しまくってしまった。難しい実装と些細なミスが絡むと原因が分からなくなって大変なことになってしまう。気を付けていきたい。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class StronglyConnectedComponents {
public:
    StronglyConnectedComponents(ll n) :
        n_(n),
        edges_(n),
        reverse_edges_(n),
        order_(n),
        num_(0) {}
    
    void addEdge(ll from, ll to) {
        edges_[from].push_back(to);
        reverse_edges_[to].push_back(from);
    }

    vector<vector<ll>> scc() {
        visit.assign(n_, false);
        for (ll i = 0; i < n_; i++) {
            dfsForward(i);
        }
        sort(order_.begin(), order_.end(), [](const Order& lhs, const Order& rhs) {
            return lhs.order > rhs.order;
        });
        visit.assign(n_, false);
        for (ll i = 0; i < n_; i++) {
            auto curr_result = dfsBackward(order_[i].index);
            if (curr_result.size() == 0) {
                continue;
            }
            result_.push_back(curr_result);
        }
        return result_;
    }

    vector<vector<ll>> sccEdges() {
        vector<vector<ll>> scc_edges(result_.size());
        vector<ll> indexToScc(n_);
        for (ll i = 0; i < (ll)result_.size(); i++) {
            for (ll j : result_[i]) {
                indexToScc[j] = i;
            }
        }

        for (ll i = 0; i < (ll)result_.size(); i++) {
            for (ll from : result_[i]) {
                for (ll to : edges_[from]) {
                    if (indexToScc[to] == i) {
                        continue;
                    }
                    scc_edges[i].push_back(indexToScc[to]);
                }
            }
        }
        return scc_edges;
    }
private:
    void dfsForward(ll curr) {
        if (visit[curr]) {
            return;
        }
        visit[curr] = true;
        for (ll next : edges_[curr]) {
            dfsForward(next);
        }
        order_[curr] = { curr, num_++ };
        return;
    }

    vector<ll> dfsBackward(ll curr) {
        vector<ll> curr_result;
        if (visit[curr]) {
            return curr_result;
        }
        visit[curr] = true;
        curr_result.push_back(curr);
        for (ll next : reverse_edges_[curr]) {
            auto members = dfsBackward(next);
            for (ll m : members) {
                curr_result.push_back(m);
            }
        }
        return curr_result;
    }

    ll n_;
    vector<vector<ll>> edges_;
    vector<vector<ll>> reverse_edges_;
    struct Order {
        ll index, order;
    };
    vector<Order> order_;
    vector<bool> visit;
    vector<vector<ll>> result_;
    ll num_;
};

int main() {
    ll n, m, k;
    cin >> n >> m >> k;
    vector<char> c(n);
    for (ll i = 0; i < n; i++) {
        cin >> c[i];
    }

    StronglyConnectedComponents scc(n);
    for (ll i = 0; i < m; i++) {
        ll a, b;
        cin >> a >> b;
        a--; b--;
        scc.addEdge(a, b);
    }

    auto scc_result = scc.scc();
    auto scc_edges = scc.sccEdges();

    ll N = scc_result.size();
    vector<string> scc_chars(N);
    for (ll i = 0; i < N; i++) {
        for (ll j : scc_result[i]) {
            scc_chars[i].push_back(c[j]);
        }
        //ソートしておく
        sort(scc_chars[i].begin(), scc_chars[i].end());
    }

    vector<vector<string>> dp(N + 1, vector<string>(k + 1));

    for (ll i = N - 1; i >= 0; i--) {
        for (ll j = 0; j <= min((ll)scc_result[i].size(), k); j++) {
            string str = scc_chars[i].substr(0, j);
            if (dp[i][j].empty() || dp[i][j] > str) {
                dp[i][j] = str;
            }
            for (ll next : scc_edges[i]) {
                for (ll l = 1; l <= k - j; l++) {
                    if (l > 0 && dp[next][l].empty()) {
                        break;
                    }
                    string tmp = str + dp[next][l];
                    if (dp[i][j + l].empty() || dp[i][j + l] > tmp) {
                        dp[i][j + l] = tmp;
                    }
                }
            }
        }
    }

    string ans;
    for (ll i = 0; i < N; i++) {
        if (dp[i][k].empty()) {
            continue;
        }
        if (ans.empty() || ans > dp[i][k]) {
            ans = dp[i][k];
        }
    }

    cout << (ans.empty() ? "-1" : ans) << endl;
}

AtCoder Regular Contest 029 C - 高橋君と国家

問題

 N個の都市とM本の道を持つ国家がある。都市には交易所を置くという操作ができ、道には舗装するという操作ができ、それぞれ各都市、道ごとにコストが設定されている。全ての都市について、「その都市に交易所が設置されている」あるいは「舗装された道のみを用いて交易所が設置されている都市に移動できる」条件を満たすように操作を行うとき、最小のコストを求めよ。

解法

 0番目の都市というものを考え、ここにはすでに交易所があり他の全ての都市へ道を持つものとする。「都市iに交易所を置く」という操作は「都市0と都市iの道を舗装する」という操作に変換して考えるものとする。このコストはもともと都市iに交易所を設置するコストとして与えられたものに等しい。

 このとき、条件を満たす状態は都市0から都市Nが連結になっていることであり、これはプリム法やクラスカル法などから高速に求めることができる。

反省

 1時間11分(4WA)でAC。1時間ほどダイクストラ法 + Union Findみたいな方針でやっていたが、WAがしこたま出てどうしようもない感じだったので解説スライドを見た。全く想定していない解法だった。

 フローの問題とかである(らしい)感じの、仮想的なノードを作って問題を簡単にする手法にはまだ全然慣れていなくてどういうときに有効なのかよくわからない。しかしより一般化すると、「操作が複数あるときにそれを統一的な視点から眺め直す」ということなのだろうか。交易所の設置と道の舗装という操作を一つにまとめたいという気になって、こういうことが思いつくのかもしれない。交易所の設置コストは完全に初期値としか思っていなかった。

 実装が遅くていろいろ考察を試せなかったのも反省点。そもそもふわっとした考察のまま適当に実装し始めてしまったのも良くなかった。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

struct Edge {
    ll from, to, cost;
};
vector<ll> parent;

ll root(ll x) {
    return (parent[x] == x ? x : parent[x] = root(parent[x]));
}

void unite(ll x, ll y) {
    x = root(x);
    y = root(y);
    if (x != y) {
        parent[y] = x;
    }
}

bool same(ll x, ll y) {
    return (root(x) == root(y));
}

int main() {
    ll N, M;
    cin >> N >> M;
    vector<ll> c(N);
    for (ll i = 0; i < N; i++) {
        cin >> c[i];
    }
    vector<Edge> edges(N);
    for (ll i = 0; i < M; i++) {
        ll a, b, r;
        cin >> a >> b >> r;
        a--; b--;
        edges.push_back({ a, b, r });
    }
    for (ll i = 0; i < N; i++) {
        edges.push_back({ i, N, c[i] });
    }

    parent.resize(N + 1);
    iota(parent.begin(), parent.end(), (ll)0);

    sort(edges.begin(), edges.end(), [&](const Edge& lhs, const Edge& rhs) {
        return lhs.cost < rhs.cost;
    });

    ll ans = 0;
    for (Edge e : edges) {
        if (!same(e.from, e.to)) {
            ans += e.cost;
            unite(e.from, e.to);
        }
    }

    cout << ans << endl;
}

AtCoder Regular Contest 028 C - 高橋王国の分割統治

問題

 N頂点の木に対して、各頂点についてその頂点を通らずに通行可能な頂点集合の最大の大きさを求めよ。

解法

 ある頂点を根としたときの答えを求めることを考える。根から行ける各頂点について、その頂点の下にいくつの頂点があるかを深さ優先探索で求め、それらのうち最大値が答えとなる。

 深さ優先探索で数を求めるとき、往復してしまうことを避けるために直前に通った頂点も状態として持つこととする(int dfs(int curr, int pre))。これはある辺に対応しており、メモ化することでO(N - 1)で求めることができる。このときdfs(i, j) = N - dfs(j, i)であることを利用すると効率よく計算できる。

 答えを求める操作も辺の数を2方向に見るだけなのでO(2(N - 1))であり、結局O(2(N - 1)) = O(N)がこの問題全体を解くうえで必要な計算量となってこれは間に合う。実装においてはメモ化にmapを用いたのでさらにlog(2(N - 1))かかるがそれでも問題ない。

反省

 34分16秒(3WA)でAC。最初は眠くて頭が回っていなかったが、25分ごろに30点の部分点解法を出したときに、これをもうちょっと改造すればできそうだということに気が付いた。

 2回TLEを出しながらもなんとか適当な高速化をして通すことができたが、計算量がよくわからない。メモ化さえすれば高速化する前もO(2N)に収まっているような気がしてしまうが……。dfs(i, j) = N - dfs(j, i)であることを利用することでそんなに変わるのだろうか。

 解説スライドを読むと木DPと言っている。解法が木DPと言われる問題は今のところそうと意識しないまま解けてしまっていることが何度かあるが、トポロジカル順が木構造に対応しているDPということだと理解している。

 これをテーブル形式で書けるというのが自分としては驚いてしまう。有向グラフとして扱い、N-1のものから考えているところがミソだということは言われればわかるが、これを解答として出せる気はしない。解ける限りは大人しくメモ化していいだろう。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

ll N;
vector<vector<ll>> connect;
map<pair<ll, ll>, pair<bool, ll>> memo;

ll dfs(ll curr, ll pre) {
    if (memo[{curr, pre}].first) {
        return memo[{curr, pre}].second;
    }
    memo[{curr, pre}].first = true;
    ll result = 1;
    for (ll next : connect[curr]) {
        if (next == pre) {
            continue;
        }
        result += dfs(next, curr);
    }
    memo[{pre, curr}].first = true;
    memo[{pre, curr}].second = N - result;
    return memo[{curr, pre}].second = result;
}

ll solve(ll curr) {
    ll ans = 0;
    for (ll next : connect[curr]) {
        ans = max(ans, dfs(next, curr));
    }
    return ans;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> N;
    connect.resize(N);
    for (ll i = 0; i < N - 1; i++) {
        ll p;
        cin >> p;
        connect[i + 1].push_back(p);
        connect[p].push_back(i + 1);
    }

    for (ll i = 0; i < N; i++) {
        cout << solve(i) << endl;
    }
}

AtCoder Regular Contest 027 C - 最高のトッピングにしような

問題

 ある飲食店ではN種類のトッピングを行うことができる。トッピングiを入手したときに得られる嬉しさはh_iであり、t_i枚のチケットを使うと入手できるが、その中には1枚以上スペシャルチケットを含んでいる必要がある。同じトッピングを複数回入手することはできない。最初持っているスペシャルチケットをX枚、普通のチケットをY枚として与えるので、嬉しさの最大値を求めよ。

解法

 「 dp[i][j][k] = i番目のトッピングまで考えたときに、残りのスペシャルチケットがj枚、普通のチケットがk枚であるときの嬉しさの最大値」としてテーブルを埋めていけばよい。交換するときまずスペシャルチケットは1枚消費し、それ以外はできるだけ普通のチケットを消費し、まだ足りなかったらスペシャルチケットを消費することが最善なのでO(1)で遷移できる。

反省

 12分25秒(0WA)でAC。パッと見でDPだろうなという感じだったし、遷移が簡単なので慣れていないforループでもそこまで時間がかからず実装できた。これくらいのDPはサッと解けるようにしておきたい。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll X, Y, N;
    cin >> X >> Y >> N;
    vector<ll> t(N), h(N);
    for (ll i = 0; i < N; i++) {
        cin >> t[i] >> h[i];
    }

    vector<vector<vector<ll>>> dp(N + 1, vector<vector<ll>>(X + 1, vector<ll>(Y + 1, 0)));
    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j <= X; j++) {
            for (ll k = 0; k <= Y; k++) {
                //交換する
                ll nk = max(k - (t[i] - 1), (ll)0);
                ll nj = j - (t[i] - (k - nk));
                if (nj >= 0) {
                    dp[i + 1][nj][nk] = max(dp[i + 1][nj][nk], dp[i][j][k] + h[i]);
                }

                //交換しない
                dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k]);
            }
        }
    }

    ll ans = 0;
    for (ll j = 0; j <= X; j++) {
        ans = max(ans, *max_element(dp[N][j].begin(), dp[N][j].end()));
    }
    cout << ans << endl;
}