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

hamayanhamayan's blog

ずんだアロー [yukicoder 921]

https://yukicoder.me/problems/no/921

解説

https://yukicoder.me/submissions/396568

同じ大きさの場合は消えないので全部ずんだ餅にできる。
基本的には、「ず餅ず餅」みたいな感じにすればよさそう。
影響するのは2つ前くらいなので、ちょっと前くらいを見ればいい。
DP[i] := 最後にi番目のずんだ餅を食べたときにずんだ餅にできる最大個数
DP[i] = i番目の餅の個数 + max(DP[i - 2], DP[i - 3])が更新式になる。
A[i]=A[i-1]を満たすならば、DP[i] = i番目の餅の個数 + max(DP[i - 2], DP[i - 3], DP[i - 1])もOK
4個前を最後に使うパターンは2個前を使えば最大になるので、これ以降は考える必要はない。

int N, A[101010], dp[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    
    rep(i, 0, N) {
        int ma = 0;
        if (0 < i and A[i - 1] == A[i]) chmax(ma, dp[i]);
        if (0 <= i - 1) chmax(ma, dp[i - 1]);
        if (0 <= i - 2) chmax(ma, dp[i - 2]);
        dp[i + 1] = ma + 1;
    }

    int ans = 0;
    rep(i, 0, N + 1) chmax(ans, dp[i]);
    cout << ans << endl;
}

あかあお [yukicoder 920]

https://yukicoder.me/problems/no/920

解説

https://yukicoder.me/submissions/396330

XYZの制約が小さいので、個数で全探索できそう。
白色のボールが何個赤色になるかを全探索しよう。
赤にならない白ボールは青にすればいい。
あとは、紫色のボールはmin(赤ボール, 青ボール)だけ作れるので、
それの最大値が答え。

int X, Y, Z;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> X >> Y >> Z;
    int ans = -1;
    rep(dr, 0, Z + 1) {
        int red = X + dr;
        int blue = Y + (Z - dr);
        chmax(ans, min(red, blue));
    }
    cout << ans << endl;
}

ゼッケンの交換 (Swapping Bibs) [第15回日本情報オリンピック 予選(オンライン) B]

https://atcoder.jp/contests/joi2016yo/tasks/joi2016yo_b

解説

https://atcoder.jp/contests/joi2016yo/submissions/8343032

操作は複雑だがN,Mのサイズは小さい。
全ての操作回数を考えるとNM回くらいなので、シミュレーションしても間に合う。
シミュレーションしよう。
交換はswap関数を使うと自然に書ける。

int N, M, A[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) cin >> A[i];
    rep(k, 1, M + 1) rep(i, 0, N - 1) if (A[i] % k > A[i + 1] % k) swap(A[i], A[i + 1]);
    rep(i, 0, N) cout << A[i] << endl;
}

ゾンビ島 (Zombie Island) [第15回日本情報オリンピック 予選(オンライン) E]

https://atcoder.jp/contests/joi2016yo/tasks/joi2016yo_e

前提知識

解説

https://atcoder.jp/contests/joi2016yo/submissions/8344819

まずは危険な街を特定しよう。
これはゾンビの街からKステップで到達可能な所であるが、到達可能性検証といえばBFSなので、
ゾンビの街の複数点を始点とするBFSでKステップ移動し、危険な街を特定しよう。

これで街を訪れたときのコストは特定できた。
後は宿泊費の合計の最小値だが、グラフで最短コストはダイクストラっぽいので、
ダイクストラできそうか考えるとできるので、ダイクストラやると答え。
頂点Nでは一泊する必要はないので、その分は引くこと。

int N, M, K, S, P, Q;
vector<int> E[101010];
bool zombie[101010];
//---------------------------------------------------------------------------------------------------
bool danger[101010];
int dist[101010];
void bfs() {
    queue<int> que;

    rep(i, 0, N) {
        if (zombie[i]) {
            dist[i] = 0;
            que.push(i);
        }
        else dist[i] = -1;
    }

    while (!que.empty()) {
        int cu = que.front(); que.pop();

        fore(to, E[cu]) if (dist[to] < 0) {
            dist[to] = dist[cu] + 1;
            que.push(to);
        }
    }

    rep(i, 0, N) if (1 <= dist[i] and dist[i] <= S) danger[i] = true;
}
//---------------------------------------------------------------------------------------------------
bool vis[101010];
ll D[101010];
ll dijk() {
    rep(i, 0, N) D[i] = infl;
    rep(i, 0, N) vis[i] = false;

    min_priority_queue<pair<ll, int>> que;

    D[0] = 0;
    que.push({ 0, 0 });

    while (!que.empty()) {
        auto q = que.top(); que.pop();

        ll cst = q.first;
        int cu = q.second;

        if (cu == N - 1) {
            if (danger[cu]) return cst - Q;
            else return cst - P;
        }

        if (vis[cu]) continue;
        vis[cu] = 1;

        fore(to, E[cu]) {
            if (zombie[to]) continue;

            ll cst2 = cst;

            if (danger[to]) cst2 += Q;
            else cst2 += P;
            
            if (chmin(D[to], cst2)) que.push({ D[to], to });
        }
    }

    return -1;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> K >> S >> P >> Q;
    rep(i, 0, K) {
        int c; cin >> c; c--;
        zombie[c] = true;
    }
    rep(i, 0, M) {
        int a, b; cin >> a >> b; a--; b--;
        E[a].push_back(b);
        E[b].push_back(a);
    }

    bfs();
    cout << dijk() << endl;
}

ロシアの旗 (Russian Flag) [第15回日本情報オリンピック 予選(オンライン) C]

https://atcoder.jp/contests/joi2016yo/tasks/joi2016yo_c

解説

https://atcoder.jp/contests/joi2016yo/submissions/8343183

どこから考えようかという話だが、全探索できそうな所が無いか探そう。
ゴールの形はそんなに状態が無い。
上からwhite行が白で、そこから更にblue行が青であるという風に考えると、
状態空間はO(N2)くらいで、余裕。
あとは、適切にマスを書き換えるが、これは色があってない所を数えると、その個数が最適な書き換え回数となる。
この書き換え回数の最小値が答え。

count(sy, ty, c) := [sy,ty)行の矩形領域にある種類cのマスの個数
この関数は二次元累積和を使ってもいいが、愚直にループでやっても間に合う。

int N, M;
string B[50];
//---------------------------------------------------------------------------------------------------
int count(int sy, int ty, char c) { // [sy, ty)
    int res = 0;
    rep(y, sy, ty) rep(x, 0, M) if (B[y][x] == c) res++;
    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) cin >> B[i];

    int ans = inf;
    rep(white, 1, N) rep(blue, 1, N) {
        int red = N - white - blue;
        if (0 < red) {
            int tot = 0;
            tot += white * M - count(0, white, 'W');
            tot += blue * M - count(white, white + blue, 'B');
            tot += red * M - count(white + blue, white + blue + red, 'R');
            chmin(ans, tot);
        }
    }
    cout << ans << endl;
}

ShoppingSpree [SRM 770 Div1 Med]

https://community.topcoder.com/stat?c=problem_statement&pm=15702

N種類のシャツがあり、それぞれshirtValue[i]を持つ。
M種類のジーンズがあり、それぞれjeansValue[i]を持つ。
D種類のペアがあり、(i番目のシャツ, j番目のジーンズ)のようにそれぞれ1種類を指す。
K枚クーポンがあり、1枚クーポンを使うと、D種類あるペアのいずれかのパターンでシャツとジーンズを買える。
i番目のシャツが1枚以上買われていればshirtValue[i]点取得する。
j番目のジーンズが1枚以上買われていればjeansValue[i]点取得する。
最適に購入して点数を最大化せよ。

1≦N,M,K,D≦100
1≦shirtValue[i], jeansValue[j]≦106

前提知識

解説

マッチングっぽい雰囲気を感じるし、制約もフローっぽいので、そっち方面で考えていると最小費用流で解けると思いつく。
以下のようなフローを構築して、流量Kを流す。

0~N-1 : シャツ頂点
N~N+M-1ジーンズ頂点
N+M (=st) : 始点
N+M+1 (=st2) : 流れきれない流量を流す始点
N+M+2 (=gr) : 終点
N+M+3 (=gr2) : 流れきれない流量を流す終点

遷移先 流量 コスト 参考
st → 0~N-1 1 -shirtValue[i]
st → st2 0 シャツに流し切れない量をこっちに流す
st2 → 0~N-1 -MAX シャツに流し切れない量をこっちに流す
0~N-1 → N~N+M-1 1 -MAX そういうペアがあれば張る
N~N+M-1→ gr 1 -jeansValue[j]
N~N+M-1→ gr2 0 ジーンズに流しきれない量をこっちに流す
gr2→ gr -MAX ジーンズに流しきれない量をこっちに流す

あとは、全部のコストに+MAXをして、流量Kを流す。
で、2K-mcfが答え。
D<Kの場合があるので注意。

struct ShoppingSpree {
    int maxValue(int k, vector <int> shirtValue, vector <int> jeansValue, vector <int> shirtType, vector <int> jeansType) {
        int n = shirtValue.size();
        int m = jeansValue.size();
        int d = shirtType.size(); // d is the number of types

        chmin(k, d);

        ll NG = 1000000;
        MinCostFlow<205, ll> mcf;
        int st = n + m;
        int st2 = n + m + 1;
        int gr = n + m + 2;
        int gr2 = n + m + 3;

        mcf.add_edge(st, st2, 100, NG);
        rep(i, 0, n) mcf.add_edge(st, i, 1, NG - shirtValue[i]);
        rep(i, 0, n) mcf.add_edge(st2, i, 100, 0);
        rep(i, 0, d) mcf.add_edge(shirtType[i], n + jeansType[i], 1, 0);
        rep(i, 0, m) mcf.add_edge(n + i, gr, 1, NG - jeansValue[i]);
        rep(i, 0, m) mcf.add_edge(n + i, gr2, 100, NG);
        mcf.add_edge(gr2, gr, 100, 0);

        ll ans = mcf.mincost(st, gr, k);
        ans = NG * (k * 2) - ans;
        return ans;
    }
};

DeleteArrays [SRM 770 Div1 Easy / Div2 Hard]

https://community.topcoder.com/stat?c=problem_statement&pm=15738

パラメタより生成される3つの数列A,B,Cがある(正式は問題文参照)。
以下の操作のいずれかを何度も行うことができる。

  • 配列A,Bから要素を1つずつ消す。コストは(x + 消した要素の総和)
  • 配列B,Cから要素を1つずつ消す。コストは(y + 消した要素の総和)
  • 配列A,Cから要素を1つずつ消す。コストは(z + 消した要素の総和)

最適に要素を消して、残った数の総和を最小化せよ。
その上で、消すのにかかったコストも最小化せよ。

2≦A,B,Cの要素数≦105
1≦x,y,z,ABCの要素≦109 (ちょっと改変してるけど、問題ない)

解説

A,B,Cの要素数をa,b,cとする(問題でもそうだが)。
a+b+cが奇数であれば、必ず1つは残る。
どれを残すべきかは、3つを全て試して一番いいものを採用しよう。
doDeleteメソッドでは、それをやっていて、実際に解いているのは、solveメソッド。

まず、余ってしまうパターンを考えると、a,b,cの中で最大のものがそれ以外の和よりも大きい場合である。
その場合は、最大のものの一部が消化できない(なるべく小さい数を消化できないものとして残そう)。
a,b,cの中で最大のものがそれ以外の和と等しければ、最大のものとそれ以外でマッチングを行うことで全て消化できる。
a,b,cの中で最大のものがそれ以外の和より小さいならば、3種類の操作を1回ずつ行い、全部2個減らす。 減らした段階で改めて、a,b,cの中で最大のものとそれ以外の和の大小関係を考えよう。

これで、残った数の総和の最小化は達成できた。
あとは消すのにかかったコストの最小化だが、結構難しい問題に見える。
消すのにかかるコストは残りの総和を最小化したときには一定になると仮定して、普通に計算する。
それで祈ってだすと通る。

struct DeleteArrays {
    pair<ll, ll> solve(vector<ll> A, vector<ll> B, vector<ll> C, ll x, ll y, ll z) {
        int a = A.size();
        int b = B.size();
        int c = C.size();
        ll ans1 = 0, ans2 = 0;

        int ma = max({ a, b, c });
        if ((a + b + c - ma) < ma) {
            int d = ma - (a + b + c - ma);
            if (max({ a, b, c }) == a) {
                rep(i, 0, d) ans1 += A[a - 1 - i];
                a -= d;
            }
            else if (max({ a, b, c }) == b) {
                rep(i, 0, d) ans1 += B[b - 1 - i];
                b -= d;
            }
            else if (max({ a, b, c }) == c) {
                rep(i, 0, d) ans1 += C[c - 1 - i];
                c -= d;
            }
        }

        rep(i, 0, a) ans2 += A[i];
        rep(i, 0, b) ans2 += B[i];
        rep(i, 0, c) ans2 += C[i];

        while ((a + b + c - max({ a, b, c })) > max({ a, b, c })) {
            ans2 += (x + y + z);
            a -= 2;
            b -= 2;
            c -= 2;
        }

        ma = max({ a, b, c });
        if (max({ a, b, c }) == a) {
            ans2 += x * b;
            ans2 += z * c;
        }
        else if (max({ a, b, c }) == b) {
            ans2 += x * a;
            ans2 += y * c;
        }
        else if (max({ a, b, c }) == c) {
            ans2 += y * b;
            ans2 += z * a;
        }

        return { ans1, ans2 };
    }
    vector<long long> doDelete(int a, int b, int c, long long x, long long y, long long z) {
        vector<ll> A(a), B(b), C(c);
        A[0] = 33; A[1] = 42;
        rep(i, 2, a) A[i] = ((5 * A[i - 1] + 7 * A[i - 2]) % 1000000007) + 1;
        B[0] = 13;
        rep(i, 1, b) B[i] = ((11 * B[i - 1]) % 1000000007) + 1;
        C[0] = 7; C[1] = 2;
        rep(i, 2, c) C[i] = ((5 * C[i - 1] + 7 * C[i - 2]) % 1000000007) + 1;
        sort(all(A), greater<ll>());
        sort(all(B), greater<ll>());
        sort(all(C), greater<ll>());

        pair<ll,ll> ans = { infl, infl };

        if ((a + b + c) % 2 == 1) {
            pair<ll,ll> cand;
            vector<ll> tmp;

            tmp = A;
            tmp.pop_back();
            cand = solve(tmp, B, C, x, y, z);
            cand.first += A[a - 1];
            chmin(ans, cand);

            tmp = B;
            tmp.pop_back();
            cand = solve(A, tmp, C, x, y, z);
            cand.first += B[b - 1];
            chmin(ans, cand);

            tmp = C;
            tmp.pop_back();
            cand = solve(A, B, tmp, x, y, z);
            cand.first += C[c - 1];
            chmin(ans, cand);
        }
        else ans = solve(A, B, C, x, y, z);

        return { ans.first, ans.second };
    }
};