Topcoder SRM 721 Div1 Medium - GraphAndPairs

問題記録 Topcoder SRM SRM #721 構築ゲー

問題概要

整数d, kが与えられる。最短距離がdであるような頂点のペアがちょうどk個あるような無向グラフを構成せよ。ただしすべての辺の距離は1とし、辺・頂点とも最大で1000個までとする。

2 <= d <= 50

1 <= k <= 50000

解法

(D-1)個の頂点を一直線につないだグラフを考える。このグラフの両端にn個ずつ頂点をくっつけると両側の距離がちょうどdになるので、条件を満たすペアはn2個になる。このようなグラフを独立に何個も作っていくことにすれば、結局kを平方数の和で表す問題に帰着する。貪欲でやっても最大ケースで800個程度しか頂点を使わないので十分収まる。ただしd=2がコーナーケースで、ひとつの頂点を中心に他の点をくっつけていく形になるので、その場合の処理は分けて書く必要がある。

感想

なんか全然思いつかなかったです

コード (C++)

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
#define REP2(i,m,n) for (int i=m;i<(n);i++)
typedef long long ll;

class GraphAndPairs  {
public:
    vector<int> construct(int D, int K) {
        vector<int> ans;
        
        if (D == 2) {
            for (int n = 0; n < 1000 && K > 0; ++n) {
                int m = n;
                int s = 0;
                for (n = n + 1; n < 1000 && s <= K; ++n) {
                    ans.push_back(m);
                    ans.push_back(n);
                    K -= s;
                    s += 1;
                }
            }
        } else {
            for (int n = 0; n < 1000 && K > 0; ) {
                int m1 = n;
                int m2 = n + D - 2;
                for (n = n + 1; n <= m2; ++n) {
                    ans.push_back(n - 1);
                    ans.push_back(n);
                }
                int cnt;
                for (cnt = 1; n < 1000 && K - cnt * cnt >= 0; cnt += 1, n += 2) {
                    ans.push_back(n);
                    ans.push_back(m1);
                    ans.push_back(n + 1);
                    ans.push_back(m2);
                }
                cnt -= 1;
                K -= cnt * cnt;
            }
        }

        int mx = 0; for (auto a: ans) mx = max(mx, a);
        ans.push_back(mx + 1);
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

Topcoder SRM 721 Div1 Easy - RememberWords

Topcoder SRM SRM #721 問題記録

問題概要

ある連続した期間の前半d1日で合計w1個の単語を覚え、後半d2日で合計w2個の単語を覚えたい。任意の連続する2日間において覚える単語の数が高々1しか変わらないように単語を覚えるという制約のもとで、このような単語の覚え方が可能か判定せよ。

d1, d2, w1, w2 <= 109

解法

2分探索で前半、後半それぞれの1日に覚える単語数としてありえるものの最大・最小を求める。求めた最大最小の範囲内にある数はすべて端にもっていくことができるので、それで前半と後半を差1以内でつなげることができるかを見ればよい。

最小値は公差1の等差数列の初項になるはず（x, x+1, ... x+d-1という形を試していって、和がはじめにwを超えるときのxが最小値）なのでそれで2分探索をする。最大値も同じように公差-1の等差数列の初項になっているはずだが、こちらの場合は途中で項が0にぶつかる可能性があるので若干面倒。数列の項数をmin(d, 初項)でとればそのケースをカバーできる。

感想

書き直したら通ったけどなんで落ちたのかよくわからない

コード (C++)

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
#define REP2(i,m,n) for (int i=m;i<(n);i++)
typedef long long ll;

class RememberWords  {
public:
    string isPossible(int d1, int d2, int w1, int w2) {
        ll d1min = binsearch_min(d1, w1);
        ll d1max = binsearch_max(d1, w1);
        ll d2min = binsearch_min(d2, w2);
        ll d2max = binsearch_max(d2, w2);

        cout << d1min << " " << d1max << " " << d2min << " " << d2max << endl;
        return (d1min - 1 > d2max || d1max + 1 < d2min) ? "Impossible" : "Possible";
    }

    ll sm(ll a, ll n, ll d) {
        return n * (2 * a + (n - 1) * d) / 2;
    }
    
    ll binsearch_min(ll d, ll w) {
        ll hi = 1000000000;
        ll lo = -1;
        while (hi - lo > 1) {
            ll mid = (hi + lo) / 2;
            ll s = sm(mid, d, 1);
            if (s >= w) hi = mid;
            else lo = mid;
        }
        return hi;
    }

    ll binsearch_max(ll d, ll w) {
        ll hi = 1000000001;
        ll lo = 0;
        while (hi - lo > 1) {
            ll mid = (hi + lo) / 2;
            ll s = sm(mid, min(d, mid), -1);
            if (s <= w) lo = mid;
            else hi = mid;
        }
        return lo;
    }
    
};

Typical DP Contest L - 猫

問題記録 AtCoder TDPC

http://tdpc.contest.atcoder.jp/tasks/tdpc_cat

問題概要

1～Nまでの番号がついたN匹の猫がいる。任意の猫2匹の組合せには親密度が設定されており、各猫の幸福度は自分との距離が1以内のところにいるすべての猫との親密度の和で定義される。1次元の数直線上の実数座標に猫を番号順に座標が大きくなっていくよう並べたときの各猫の幸福度の総和の最大値を求めよ。

N <= 1000

解法

dp(i, j) = i番目の猫まで置き、i番目の猫と(j～i-1)番目の猫が距離1以内にいるときの最大幸福度

猫は番号順に左から並べるという制約があるので、猫iが距離1以内に含む可能性のある猫の集合は(0～i-1), (1～i-1), ..., i-1, 空集合, というパターンだけである。これらのパターンでの親密度の増え方は普通の累積和で前計算しておけるのでdpの更新時にはO(1)でできる。前処理, DPともにO(N2).

感想

最初あんなに短い問題文を誤読して順番自由と思い込みムズすぎ！！！！！！！！！！！となって解説を漁ってしまいました……

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;

void main() {
    auto N = readln.chomp.to!int;
    auto A = N.iota.map!(_ => readln.split.map!(to!long).array).array;
    auto B = new long[][](N + 1, N + 1);
    foreach (i; 0..N) foreach (j; iota(i, -1, -1)) B[i][j] += B[i][j+1] + A[i][j];
    auto dp = new long[][](N + 1, N + 1);

    foreach (i; 0..N) {
        dp[i+1][i+1] = - (1L << 59);
        foreach (j; 0..i+1) {
            dp[i+1][i+1] = max(dp[i+1][i+1], dp[i][j]);
            dp[i+1][j] = dp[i+1][i+1] + B[i+1][j] * 2;
        }
    }

    dp[N].reduce!max.writeln;
}

Typical DP Contest K - ターゲット

問題記録 AtCoder TDPC

http://tdpc.contest.atcoder.jp/tasks/tdpc_target

問題

半径ri, 中心(xi, 0)のN個の円が与えられる。この中からどの2円をとっても片方がもう片方の内部に厳密に含まれるようにいくつかの円を選ぶとき、選べる円の最大数を求めよ。

解法

円cとx軸上の2交点を小さい順にLc, Rcとすると円iが円jの内部に含まれるためにはLj < Li かつ Ri < Rj となることが必要十分条件である。よってLで円をソートし、最長減少部分列を求めれば答えが出る。

感想

自力で解けず。円の位置関係の式をこねくりまわして全然わからんとなっていた。いや確かにDPは典型だけどもねきみ

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;

immutable int INF = 1 << 29;

void main() {
    auto N = readln.chomp.to!int;
    auto C = N.iota.map!(_ => readln.split.map!(to!int).array).array;
    C.sort!"a[0] - a[1] < b[0] - b[1]"();

    auto LIS = new int[](N + 1);
    LIS.fill(-INF);
    LIS[0] = INF;

    for (int i = 0; i < N; ) {
        Tuple!(int, int)[] tmp;
        do {
            auto lb = LIS.assumeSorted!"a > b".lowerBound(C[i][0] + C[i][1]).length.to!int;
            tmp ~= tuple(lb, C[i][0] + C[i][1]);
            ++i;
        } while (i < N && C[i][1] - C[i][0] == C[i-1][1] - C[i-1][0]);

        foreach (t; tmp)
            LIS[t[0]] = max(LIS[t[0]], t[1]);
    }

    (N + 1).iota.filter!(i => LIS[i] != -INF).reduce!max.writeln;
}

Typical DP Contest I - イウィ

問題記録 AtCoder TDPC 区間DP

http://tdpc.contest.atcoder.jp/tasks/tdpc_iwi

問題概要

iとwの2種類の文字のみからなる文字列Sが与えられる。Sのある連続部分文字列が"iwi"となっているとき、その部分を取り除く操作を行うことができる。Sに対して最大何回この操作を行えるか求めよ。

|S| <= 300

解法

区間DPをする。dp(l, r) = Sの連続部分文字列S[l..r]に対して行える最大操作回数とおく。

まず区間の長さが3以下の場合は自明で、その区間に対応する部分文字列がiwiなら1でそれ以外なら0である。これら初期値をもとに区間を伸ばしながらDPを更新していく。更新は以下の2パターンを考えるとわかりやすいかもしれない。

(1) 独立に消せる形

iwiiwiのような形の文字列は左右のiwiを独立に消せる。ゆえにdpの更新では左の区間と右の区間の値を単純に足せばいい。実装は区間内の区切り位置を全探索する形でやればok

(2) 連鎖が起きる形

iwiwiiのような文字列では真ん中のiwiを消すと外側のiw iがくっついてそれも消せるようになる。重要なのはこうした連鎖が必ず「中が全部消せる→外にiwiが残ったのでそれも消せる」という流れで起きることである。ここで中が全部消せるかどうかはそれまでのdpの値を見ればわかる（例えば長さの6の区間のdp値が2ならその区間は全消しできる）。ゆえに外側の長さが合計で3, 中の長さが区間の長さ-3になるような区切りを全部みてこういう形になっているかどうか判定すればよい。

以上でO(N3)で答えが出る。

感想

できてしまうとなんかそんなに難しく見えないんだけどやってる最中はすごく難しく感じたし結局解説を見た

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;

void main() {
    auto S = readln.chomp;
    auto N = S.length.to!int;
    auto dp = new int[][](N + 1, N + 1);

    foreach (len; 3..N+1) {
        foreach (l; 0..N-len+1) {
            int r = l + len;
            int nlen = len - 3;
            foreach (a; l..r)
                dp[l][r] = max(dp[l][r], dp[l][a] + dp[a][r]);
            foreach (a; l..l+len-nlen+1) {
                int b = a + nlen;
                if ((b - a) % 3 == 0 && dp[a][b] == (b - a) / 3)
                    dp[l][r] = max(dp[l][r], dp[a][b] + (S[l..a] ~ S[b..r] == "iwi"));
            }
        }
    }

    dp[0][N].writeln;
}

Typical DP Contest H - ナップザック

問題記録 AtCoder TDPC

http://tdpc.contest.atcoder.jp/tasks/tdpc_knapsack

問題概要

N個のものがあって、それぞれに重さw・価値v・色cが設定されている。重さ合計の最大値Wと使える色の種類の最大値Cが与えられるので、その範囲内で価値の合計が最も高くなるような組合せを選んだときの価値の最大値を求めよ。

N <= 100

W <= 10000

C <= 50

解法

普通にDPをやろうとすると「重さ」と「使った色の種類」を状態に取ってやることになるが、これだと状態数がO(W2C)、遷移がO(NW2C)になって全然間に合わない。

まず必要なのは各色ごと別個にDPを行うことである。つまり色の条件を無視して重さだけで普通のナップザック問題を解くようなDPをやる。これである一色について各重さごとの価値を出すことができる（＝ひとつひとつのものを個別にみる必要がなくなり、色単位で考えていくことができるようになる）。

次に（使った色数、重さ）を状態にしてまたDPをやる。色を順番に舐めながら、i色目を使う時には0～(i-1)色目のDPに対して更新をかけ、使った色が一色増えたという扱いにすればよい。以上でC色まで使ったときの重さW以下の最大値が出せる。

最初のDPがO(NWC), 次のDPが(WC2)で十分間に合う。

感想

自力では解けず。2NをN2に落とすというところを考えると典型といえる……のか？？？

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0], W = s[1], C = s[2];
    auto WV = new Tuple!(int, int)[][](55);
    foreach (i; 0..N) {
        s = readln.split.map!(to!int);
        WV[s[2]] ~= tuple(s[0], s[1]);
    }


    auto dp = new int[][](55, 10101);

    foreach (c; 1..55) {
        foreach (c2; iota(c-1, -1, -1)) {
            auto tmp = dp[c2].dup;

            foreach (wv; WV[c]) {
                int w = wv[0], v = wv[1];
                foreach (i; iota(10100, -1, -1))
                    if (tmp[i] > 0 && i + w <= W)
                        tmp[i+w] = max(tmp[i+w], tmp[i] + v);
                if (w <= W)
                    tmp[w] = max(tmp[w], v);
            }

            foreach (i; 0..10101)
                dp[c2+1][i] = max(dp[c2+1][i], tmp[i]);
        }
    }

    dp[C][0..W+1].reduce!max.writeln;
}

Typical DP Contest J - ボール

問題記録 AtCoder TDPC

http://tdpc.contest.atcoder.jp/tasks/tdpc_ball

問題概要

一次元の座標xiにN個の目標物が設置されている。座標xを狙ってボールを投げると等確率でx-1, x, x+1のいずれかにボールが飛んでいき、そこに目標物があればそれを倒せる。狙う座標を最適に選んだとき、すべての目標物を倒すために必要なボール投げ回数の期待値を求めよ。

1 <= N <= 16

0 <= xi <= 15

解法

座標の範囲が狭いので、座標xiに目標物がある/ないの状態をbit列で表せばbitDPができる。遷移がよくわからんが、雰囲気で以下のようにやったら通ってしまった。

  1. 狙う座標の周囲3マスに全部目標物があるとき
    • どれか1個が倒れた状態に1/3で遷移 + 1 (1回投げれば必ず1個は倒れるので)
  2. 周囲2マスに目標物があるとき
    • どちらか1個が倒れた状態に1/2で遷移 + 1.5 (どちらか2つにボールが行くのは2/3なので、その逆数）
  3. 周囲1マスに目標物があるとき
    • その1個が倒れた状態に1/1で遷移 + 3 （1/3の逆数）

通した後もモヤモヤしてたが以下の記事を読んだらすべてが腑に落ちた。

http://pekempey.hatenablog.com/entry/2016/02/05/002257

自己遷移を含む場合（この問題でいうところの何もないところにボールを投げてしまうケース）、遷移を数式で表して式変形するというテクが使えるというのが重要ポイントだったっぽい。

感想

期待値DPの基本的な流れは 期待値(次の状態) × 遷移確率 で、「次の状態」が自己遷移になっている場合には式を立てて解く、という感じで理解しておけばいいんだろうか。

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;

void main() {
    auto N = readln.chomp.to!int;
    auto X = readln.split.map!(to!int).array;


    auto mem = new real[](1 << 16);
    mem.fill(-1);

    real dfs(int mask) {
        if (mem[mask] >= 0)
            return mem[mask];
        if (mask == 0)
            return 0;

        real ret = 1L << 59;

        foreach (i; 1..15) {
            int b = (mask & (0b111 << (i - 1))) >> (i - 1);
            int nmask = mask & ~(0b111 << (i - 1));
            real tmp = 1L << 59;
            
            if (b == 0b111) {
                tmp =
                    dfs(nmask | (0b011 << (i - 1))) / 3 +
                    dfs(nmask | (0b101 << (i - 1))) / 3 +
                    dfs(nmask | (0b110 << (i - 1))) / 3 + 1;
            } else if (b == 0b011) {
                tmp =
                    dfs(nmask | (0b001 << (i - 1))) / 2 +
                    dfs(nmask | (0b010 << (i - 1))) / 2 + 1.5L;
            } else if (b == 0b101) {
                tmp =
                    dfs(nmask | (0b001 << (i - 1))) / 2 +
                    dfs(nmask | (0b100 << (i - 1))) / 2 + 1.5L;
            } else if (b == 0b110) {
                tmp =
                    dfs(nmask | (0b010 << (i - 1))) / 2 +
                    dfs(nmask | (0b100 << (i - 1))) / 2 + 1.5L;
            } else if (b.popcnt == 1) {
                tmp = dfs(nmask) + 3.0L;
            }
            
            ret = min(ret, tmp);
        }

        mem[mask] = ret;
        return ret;
    }

    
    int mask = 0;
    foreach (x; X)
        mask |= (1 << x);
    writefln("%.9f", dfs(mask));
}