AOJ 2156 Magic Slayer

問題概要

N 体のモンスターがいる.それぞれの体力は HP_i である.
自分が使える単体魔法と全体魔法がM個与えられる.それぞれの魔法には消費MPとダメージ量が決まっている.
この時,敵を全滅させるのに必要な最小のMPを求めよ.

・制約
1 <= N <= 100
1 <= HP_i <= 10^5
1 <= M <= 100
0 <= MP_j <= 99
0 <= damage_j <= 999999

解法

典型DP.この問題は実質ドラクエの「まんたん」と同じ.
まず,単体魔法しか無い場合は,それぞれの敵に対して個別にDPすればいいというのはすぐ分かる.
最終的に単体魔法だけ考えればいいことにできれば楽.なので,先に全体魔法によってあるダメージを与えるときに必要な最小のMPを求めておく.
cost[0][i] := 単体魔法だけ用いたときに,i 以上のダメージを与えるために必要な最小のMP.
cost[1][i] := 全体魔法だけ用いたときに,ちょうど i のダメージを与えるために必要な最小のMP.
これらを前計算しておけば,「ちょうど i だけ全体魔法でダメージを与えたときに,全滅させるのに必要な最小MP」は,「全体の体力から i だけ引いた後,単体魔法だけで全滅させるのに必要な最小MP」となるので,ここまでくればあとはやるだけ.
計算量は O((N+M)HP).

全部が全体(ないし単体)魔法のケース(1WA食らった.if で対処)や,単体魔法はあるけど全てダメージ0の場合(1WA食らった.ダメージ0の魔法をあらかじめ取り除くことで対処)などのコーナーケースに注意しよう.

ソースコード

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
using P = pair<int, int>;

constexpr int INF = 1e9;

int main() {
    int N;
    while(cin >> N, N) {
        vector<int> hp(N);
        int max_hp = 0;
        for(int i=0; i<N; ++i) {
            cin >> hp[i];
            max_hp = max(max_hp, hp[i]);
        }
        int M;
        cin >> M;
        vector<vector<P>> s(2);
        for(int i=0; i<M; ++i) {
            string name, target;
            int mp, dam;
            cin >> name >> mp >> target >> dam;
            if(dam == 0) {
                continue;
            }
            s[target == "All"].emplace_back(mp, dam);
        }
        vector<vector<int>> cost(2, vector<int>(max_hp+1, INF));
        cost[0][0] = cost[1][0] = 0;
        for(int k=0; k<2; ++k) {
            for(int i=0; i<s[k].size(); ++i) {
                for(int j=0; j<=max_hp; ++j) {
                    int t = min(max_hp, j+s[k][i].second);
                    cost[k][t] = min(cost[k][t], cost[k][j] + s[k][i].first);
                }
            }
        }
        for(int j=max_hp; j>=1; --j) {
            cost[0][j-1] = min(cost[0][j-1], cost[0][j]);
        }
        if(s[0].size() == 0) {
            cout << cost[1][max_hp] << endl;
        } else {
            int res = INF;
            for(int i=0; i<=max_hp; ++i) {
                if(cost[1][i] == INF) {
                    continue;
                }
                int t = cost[1][i];
                for(int j=0; j<N; ++j) {
                    int rest_hp = hp[j] - i;
                    if(rest_hp <= 0 || cost[0][rest_hp] == INF) {
                        continue;
                    }
                    t += cost[0][rest_hp];
                }
                res = min(res, t);
            }
            cout << res << endl;
        }
    }
}

TopCoder SRM 710 Div2 Hard MinMaxMax

問題概要

頂点数 N, 辺の数がM の連結グラフが与えられる.
それぞれの頂点と辺には重みがつけられていて,i 番目の頂点の重みは vi, i 番目の頂点の重みは wi である.
異なる2つの頂点 u, v の間のコストを,u-v パスのうちで,(パスに含まれる頂点の重さの最大値) * (パスに含まれる辺の重さの最大値) の最小値と定義する.
各 (u, v) に対するコストの総和を求めよ.

・制約
2 <= N <= 300
N-1 <= M <= min(2500, N(N-1)/2)
1 <= wi <= 10^6
1 <= vi <= 10^6
多重辺やループは存在しない.

解法の前に

自分は,最初「ワーシャルフロイドの要領でやるんだろうな~」と思って色々考えてみたものの,実装方針が思いつかず,普段理解せずに使ってたんだなぁと痛感した.(結局解けなかった).

writer解では2つのアプローチが紹介されていて,1つめは Kruskal 法の要領でやっていくもので,2つめはワーシャルフロイドの要領でやっていくものだった.
両方記事にしたいけど,まとめると長いので2つに分ける.
今回は1つ目のアプローチを実装した.

解法1

頂点の重みと辺の重みのどちらも考える必要があるので大変.(単純に,ある頂点に来るための最小コストだけを保存していくような最短経路問題ではない).
なので,とりあえず頂点の最大の重みを固定してしまってから考えると良い.これを vmax とする.
その上で,辺の重みが小さい順にソートしておいて,小さい方から追加していく.この時,辺を追加することで結ばれた連結成分を union-find 木で保存しておく(Kruskal 法と同じ).

追加したい辺が頂点 ai と bi を結んでいたとする.
ai と bi がすでに同じ連結成分に含まれれば,その辺は無視できる(より小さい辺のみでつながっている).また,ai と bi の重みのどちらかが vmax を超えても,その辺を無視する.
それ以外の場合,その辺を追加する.
この時,ai の連結成分 S1 と,bi の連結成分 S2 の各頂点間 (s, t) (s ∈ S1, t ∈ S2) のコストは vmax * (今追加した辺の重み) 以下となることがわかる.なぜなら,S1 と S2 に含まれる頂点の重みは全て vmax 以下であり,かつ今までに追加した全ての辺の重みは,今追加した辺の重みよりも小さいからである.
よって,vmax * (今追加した辺の重み) と,今までにわかっている (s, t) 間の最小コストとを比べて,小さい方を保存しておけばよい.

これを vmax を N 個の頂点で全部試せば,目的の値が得られる.

計算量は O(N^2M) か?これはちょっと自信がない(連結成分のコスト更新の二重ループのコストがピンとこない.下のコードでいうと,va と vb でループを回しているところ.)

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;

constexpr ll INF = 1e18;

class union_find {
public:
    union_find(int n)
        : par_(n, -1)
    {}
    void init(int n) {
        par_.assign(n, -1);
    }

    int root(int x) {
        return par_[x] < 0 ? x : par_[x] = root(par_[x]);
    }

    bool unite(int x, int y) {
        x = root(x); y = root(y);
        if(x == y) {
            return false;
        } else {
            if(par_[x] < par_[y]) { // size(x) > size(y)
                par_[x] += par_[y];
                par_[y] = x;
            } else {
                par_[y] += par_[x];
                par_[x] = y;
            }
            return true;
        }
    }

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

    int size(int x) {
        return -par_[root(x)];
    }

private:
    std::vector<int> par_;
};

class MinMaxMax {
public:
    ll findMin(vector<int> a, vector<int> b, vector<int> w, vector<int> v) {
        const int N = v.size(), M = w.size();
        vector<vector<ll>> d(N, vector<ll>(N, INF));
        vector<P> ww(M);
        for(int i=0; i<M; ++i) {
            ww[i] = make_pair(w[i], i);
        }
        sort(ww.begin(), ww.end());
        for(int i=0; i<N; ++i) {
            vector<int> comp(N);
            union_find uf(N);
            for(int j=0; j<M; ++j) {
                int aa = a[ww[j].second], bb = b[ww[j].second];
                if(uf.same(aa, bb) || v[i] < v[aa] || v[i] < v[bb]) {
                    continue;
                }
                ll now = v[i] * ww[j].first;
                vector<int> va, vb;
                for(int k=0; k<N; ++k) {
                    if(uf.same(k, aa)) {
                        va.push_back(k);
                    } else if(uf.same(k, bb)) {
                        vb.push_back(k);
                    }
                }
                for(int k=0; k<va.size(); ++k) {
                    for(int l=0; l<vb.size(); ++l) {
                        int ca = va[k], cb = vb[l];
                        d[ca][cb] = min(now, d[ca][cb]);
                        d[cb][ca] = min(now, d[cb][ca]);
                    }
                }
                uf.unite(aa, bb);
            }
        }
        ll res = 0;
        for(int i=0; i<N; ++i) {
            for(int j=i+1; j<N; ++j) {
                res += d[i][j];
            }
        }
        return res;
    }
};

解法2

わかりやすい記事があったので,引用して終わりとします.
kmjp.hatenablog.jp

AOJ 2442 Convex-Cut

問題概要

N 個の頂点からなる凸多角形が与えられる.このとき,ある点があって,その点を通る任意の直線がこの多角形を二等分することができるだろうか?できる場合は,その点の座標を求めよ.

自分が解いた時の流れ

任意の直線で二等分だからかなり制約がきつそう.点対称とかそんなんじゃないの?(適当)
→なんか通った

多少厳密(?)な証明

仮にそういう点Pがあったとして,Pを通り,それぞれ異なる直線を2本引く.
すると,明らかに,この多角形は4つの領域A, B, C, Dに分割される.
f:id:Suikaba:20170322131835p:plain
A+B = C+D かつ A+D = B+C より,A = C かつ B = D であることがわかる.つまり,向かい合う領域の面積が等しい.
ここで,向かい合う領域が共に三角形となるように直線を引くことができる(図の右側).そして,図のように辺の長さを a, b, c, d とおくと,向かい合う領域の面積が等しいことから a * b == c * d が成り立つ.ここで,2本の直線を限りなく近づけていくと,a ≒ b, c ≒ d と近似できるので,a == d と考えることができる.
これはつまり,点Pに直線を一本引いたときに,凸多角形と2点で交わるが,その2点は点Pに関して点対称の位置にあるということ.直線は任意に引けるので,結局,凸多角形の辺上の任意の点は点Pに関して点対称(凸多角形が点対称)であるということ.

よって,Nが奇数のときは点対称にならないのでNA.
Nが偶数のときは,点対称となっているかを調べればよい.これは i 番目の頂点と i + N/2 番目の頂点を調べていけば十分.

計算量は O(N).

ソースコード

#include <iostream>
#include <vector>
#include <iomanip>
#include <cmath>
using namespace std;
 
constexpr double eps = 1e-10;
 
int main() {
    int N;
    cin >> N;
    vector<double> x(N), y(N);
    for(int i=0; i<N; ++i) {
        cin >> x[i] >> y[i];
    }
    if(N % 2 == 1) {
        cout << "NA" << endl;
    } else {
        double px = (x[0] + x[N/2]) / 2, py = (y[0] + y[N/2]) / 2;
        bool ok = true;
        for(int i=0; i<N; ++i) {
            double vx = px - x[i], vy = py - y[i];
            ok &= fabs(px + vx - x[(i+N/2) % N]) < eps && fabs(py + vy - y[(i+N/2)%N]) < eps;
        }
        if(ok) {
            cout << fixed << setprecision(10) << px << " " << py << endl;
        } else {
            cout << "NA";
        }
    }
}

AOJ 2303 Marathon Match

問題概要

N 人のランナーがマラソンをする.コースの長さは L で,休憩所が途中に M 箇所存在する.i 人目のランナーは,どの休憩所でも全く同じ Pi パーセントの確率で休憩を取る.一度の休憩で Ti だけ時間を使う.また,それぞれのランナーは速度 Vi (一定)で走り続けるものとする.
このとき,i 人目のランナーが優勝する確率を求めなさい.ただし,複数人が同時に最初のゴール者となった場合,優勝したとはみなさない.

・制約
1 <= N <= 100
0 <= M <= 50
1 <= L <= 100000
0 <= Pi <= 100
0 <= Ti <= 100
0 <= Vi <= 100

解法

N, M が小さいので,愚直に確率を求めに行けばいい.具体的には, i 番目の人が j 回休憩したときに,優勝する確率を求め,それらを足していく.
このとき,j 回休憩する確率を求めないといけないが,これはパスカルの三角形の要領(普通にDP)で求めることができる.これは前計算しておけば良い.
i 番目の人が j 回休憩した時,t := L / Vi + Ti * j だけの時間がかかる.この時,k ( != i ) 番目の人が何回以上休憩すれば i 番目の人より遅くゴールするかを考えて,そのそれぞれの回数休憩する確率を足していけば,k 番目の人が i 番目の人より遅くゴールする確率が求まる.
これを i 番目以外の全てのランナーについて考え,掛け合わせれば,i 番目の人が優勝する確率を求めることができる.
ただし,Vk で割ったり,Tk で割ったりする場合があるので,Vk == 0 や Tk == 0 の場合は特別な処理をしないといけない.
また,同時にゴールした場合を省く必要があることもわすれない.

・反省
(ちゃんと考慮してたのに,最後に述べた点で2回WAくらいました.小数に対する処理が甘かった.そもそも何回以上休憩すればオッケーかを求める必要はなくて,とりあえず全部試してオーバーしてたら無視すれば Tk で割ったりする必要は無い.無駄なことをしてしまった.)

計算量は O(N^2M^2) となる.

ソースコード

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
using namespace std;

constexpr double eps = 1e-10;

int main() {
    int N, M, L;
    cin >> N >> M >> L;
    vector<vector<vector<double>>> cmb(N, vector<vector<double>>(M+1, vector<double>(M+1)));
    for(int i=0; i<N; ++i) {
        cmb[i][0][0] = 1;
    }
    vector<double> P(N), T(N), V(N);
    for(int i=0; i<N; ++i) {
        cin >> P[i] >> T[i] >> V[i];
        P[i] /= 100;
    }
    for(int i=0; i<N; ++i) {
        for(int j=1; j<=M; ++j) {
            for(int k=0; k<=j; ++k) {
                cmb[i][j][k] = cmb[i][j-1][k] * (1 - P[i]) + (k-1 >= 0 ? cmb[i][j-1][k-1] * P[i] : 0);
            }
        }
    }
    for(int i=0; i<N; ++i) {
        if(V[i] == 0) {
            cout << 0 << endl;
            continue;
        }
        double res = 0;
        for(int j=0; j<=M; ++j) {
            double t = L / V[i] + T[i] * j;
            double p = cmb[i][M][j];
            for(int k=0; k<N; ++k) {
                if(i == k || V[k] == 0) {
                    continue;
                }
                double tt = L / V[k];
                if(T[k] == 0 && tt - t <= 0) {
                    p = 0;
                    break;
                }
                int cnt = (T[k] == 0 ? 0 : ceil(max(0.0, t - tt) / T[k]));
                if(tt + T[k] * cnt - t < eps) {
                    cnt += 1;
                } 
                double pp = 0;
                for(int l=cnt; l<=M; ++l) {
                    pp += cmb[k][M][l];
                }
                p *= pp;
            }
            res += p;
        }
        cout << fixed << setprecision(10) << res << endl;
    }
}

AOJ 2157 Dial Lock

問題概要

数列の連続した区間に同じ数を足し引きする操作によって,ある数列を目的に数列に一致させたい.このとき,目的を達成する最小の操作回数を求めよ.

制約 : 数列の長さは10以下.

解法

全探索.前から順番に,数字を合わせて行けば良さそう.
なぜなら,数字をずらしていく操作列を考えたときに,それらの順番を入れ替えても最終的な状態は変化しないから.
しかし,例えば最初の数字を複数回の操作で合わせるような操作を考える必要があるだろうか?
これは考える必要が無いことが分かる.なぜなら,例えば3回の操作(それぞれ,区間 [0, a],[0, b],[0, c] を操作する.ただし,a < b < c としてよい.a == b なら無駄だし,最初に述べたように操作順は自由で良いため.)で最初の数字をあわせることを考える.
このとき,それぞれの操作で,x, y, z だけずらすとする.この時,[0, a] は x + y + z だけ,(a, b] は y + z だけ,(b, c] は z だけずれたことになる.これは,[0, a] を x + y + z だけ,(a, b] を y + z だけ, (b, c] を z だけずらす操作と同値であり,これらの操作回数は等しい.
これはつまり,ある桁をあわせることを目標とする時,その桁を一回の操作で合わせることだけ考えればよいことにほかならない.
以上から,前の桁から目的の数字に合わせ,かつ先頭の数字は一回の操作で合わせることを考えればよいことになる.
あとは,注目している区間の先頭の数字を合わせるためにずらす操作を,どの区間で行うかを全探索すれば,最終的な答えが求まる.ずらした後隣の数字を考えるので,DFSで実装すると楽.
計算量は O(k!) である.ただ,以下の実装だと string のコピーが無視できないかもしれない(それでもぎりぎり間に合う).

ソースコード

#include <iostream>
#include <string>
using namespace std;

int dfs(int i, string s, string const& g, int cnt) {
    if(i >= s.size()) {
        return cnt;
    }
    if(s[i] == g[i]) {
        return dfs(i+1, s, g, cnt);
    }
    int res = 1e9;
    int t = (g[i] - s[i] + 10) % 10;
    for(int j=i; j<s.size(); ++j) {
        s[j] = '0' + ((s[j] - '0' + t) % 10);
        res = min(res, dfs(i+1, s, g, cnt+1));
    }
    return res;
}

int main() {
    int k;
    while(cin >> k, k) {
        string s, g;
        cin >> s >> g;
        cout << dfs(0, s, g, 0) << endl;
    }
}

AOJ 2182 Eleven Lover

問題概要

ある自然数 N が与えられる.その連続部分文字列(0から始まるものを除く)で,11の倍数となるものはいくつあるか?

制約: N の桁数は 80000 以下.

解法

DP で解くことができる.dp[i][j] := 先頭から i 桁目まで見たときに,11 で割ったあまりが j となるものの総数,と定義する.
ここで,ある整数 n を 11 で割った余りの計算をたとえば 17891 を例にして考えてみる.
先頭から順番に見ていけばよく,まず 1 % 11 = 1 となる.
次に 1 * 10 + 7 % 11 = 6.
6 * 10 + 8 % 11 = 2.
2 * 10 + 9 % 11 = 7.
7 * 10 + 1 % 11 = 5.
となり,あまりは5となる.これを利用して dp で計算する.
つまり,dp[i+1][(j*10+d)%11] += dp[i][j] を計算していけば良い.ただし,d は現在見ている(i 桁目の)数字である.
また,dp[i+1][d] += 1 とすれば,i桁目を左端とした場合を含めることができる.ただし,0から始まるものは省かなければならない.
答えは dp[i][0] の総和である.

ソースコード

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    string n;
    while(cin >> n, n != "0") {
        vector<vector<int>> dp(n.size()+1, vector<int>(11));
        int res = 0;
        for(int i=0; i<n.size(); ++i) {
            int m = n[i]-'0';
            if(m != 0) {
                dp[i+1][m] += 1;
            }
            for(int j=0; j<11; ++j) {
                dp[i+1][(j*10+m)%11] += dp[i][j];
            }
            res += dp[i+1][0];
        }
        cout << res << endl;
    }
}

ARC070 D - No Need

arc070.contest.atcoder.jp

解法(証明?)

a[i] を降順にソートする.
今,a[i] が不必要かどうかを判定したいとする.この時,Si := a[1] + a[2] + ... + a_[i] とおく.
また,a[n] から a[i + 1] までの和で表現できる K 未満の数がわかっているとする.(dpで保存)
その中の任意の数 t について,t + Si < K であるならば,それは不必要な数である.
必要条件は明らか.なぜなら,t + Si < K が成り立つならば,a[i] を用いた和で K 以上となるものは,存在しないか,あるいはもともと K 以上であるかのどちらかだからである.
十分条件について示す.これは対偶を取れば良い.つまり,「必要な数ならば t + Si >= K が成り立つ」を示せば良い.
t + a[i] >= K ならば,a[i] を取り除けば K 未満となる和の作り方が存在することになるので,t + a[i] < K であると考えて良い.
ここで,数列 a が降順にソートされていることに注目すると,ある j があって t + (a[j] + ... + a[i]) >= K かつ t + (a[j + 1] + ... + a[i]) < K がなりたつ.この時,a[i] > a[j] だから, t + (a[j] + ... + a[i - 1]) < K が成り立つ.これは a[i] が必要な数であることに他ならない.
以上より,示された.

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
using ll = long long;
 
int main() {
    int N, K;
    cin >> N >> K;
    vector<int> a(N);
    for(int i=0; i<N; ++i) {
        cin >> a[i];
    }
    ll sum = accumulate(a.begin(), a.end(), 0LL);
    sort(a.rbegin(), a.rend());
    int res = 0;
    vector<bool> dp(K);
    dp[0] = true;
    for(int i=0; i<N; ++i) {
        bool f = false;
        for(int j=0; j<K; ++j) {
            f |= dp[j] && j+sum >= K;
        }
        if(!f) {
            res++;
        }
        sum -= a[i];
        for(int j=K-1-a[i]; j>=0; --j) {
            dp[j+a[i]] = dp[j+a[i]] | dp[j];
        }
    }
    cout << res << endl;
}