ACPC 2015 Day3 解法 - でも今日はSRMあるから

ACPC2015Day3
University of Aizu Competitive Programming Camp 2015 Day 3
http://judge.u-aizu.ac.jp/onlinejudge/contest_problem.jsp?id=ACPC2015Day3
3時間7問
問題・解法

アニメセット? 各問題で物語がついていて凝ってる．
問題文にそれぞれライターのヨメが登場するみたい．
解説記事の少ない問題こそ解いて解説を書かねば．

概略
A シミュレーション
B DP
C データ構造
D DP
E 幾何
F 文字列アルゴリズム
G グラフ

A : Sendame

問題

攻撃・溜め・防御のあるゲームのシミュレート

解法

各々そのターンの攻撃力出してみた．

#include<cstdio>
#include<algorithm>
using namespace std;

#define win "Isono-kun"
#define lose "Nakajima-kun"
#define draw "Hikiwake-kun"
int N;
char A[111][16], B[111][16];
int p, q;
int main() {
    scanf("%d", &N);
    for (int i=0; i<N; i++) scanf("%s", A[i]);
    for (int i=0; i<N; i++) scanf("%s", B[i]);    
    for (int i=0; i<N; i++) {
	int a, b;
	if (A[i][0] == 'k') {
	    if (p == 0) a = -2;
	    else { a = p; p = 0; }
	} else if (A[i][0] == 't') {
	    a = 0;
	    p = min(5, p+1);
	} else {
	    a = -1;
	}
	if (B[i][0] == 'k') {
	    if (q == 0) b = -2;
	    else { b = q; q = 0; }
	} else if (B[i][0] == 't') {
	    b = 0;
	    q = min(5, q+1);
	} else {
	    b = -1;
	}

	if (a == b) continue;
	if (a == 5) { puts(win); return 0; }
	if (b == 5) { puts(lose); return 0; }
	if (a == -2) { puts(lose); return 0; }
	if (b == -2) { puts(win); return 0; }
	if (a == 0 && b > 0) { puts(lose); return 0; }
	if (b == 0 && a > 0) { puts(win); return 0; }
	if (0 < a && a < b) { puts(lose); return 0; }
	if (0 < b && b < a) { puts(win); return 0; }
	if (a == -1 && b == 5) { puts(lose); return 0; }
	if (b == -1 && a == 5) { puts(win); return 0; }
    }
    puts(draw);
    return 0;
}

B : Match Peas War

問題

ターン制ゲームの勝敗判定

解法

再帰関数にそのターンの人の状態，相手の状態を入力して，そのターンの人が勝てるかどうかを出力させる．
相手に手番を渡した時に一つでも相手負けの場合があるならそのターンの人は勝つことができる．
勝敗をメモ化して同じ計算を回避する．

char mem[6][6][6][6];
char game(int lf, int rf, int ls, int rs) {
    char &c = mem[lf][rf][ls][rs];
    if (lf == 5 && rf == 5) return 0;
    if (c != -1) return c;
    if (lf < 5 && ls < 5 && !game(min(5, ls+lf), rs, lf, rf)) return c = 1;
    if (rf < 5 && ls < 5 && !game(min(5, ls+rf), rs, lf, rf)) return c = 1;
    if (lf < 5 && rs < 5 && !game(ls, min(5, rs+lf), lf, rf)) return c = 1;
    if (rf < 5 && rs < 5 && !game(ls, min(5, rs+rf), lf, rf)) return c = 1;
    return c = 0;
}

int main() {
    memset(mem, -1, sizeof mem);
    int A, B, C, D;
    scanf("%d%d%d%d", &A, &B, &C, &D);
    puts(game(A, B, C, D) ? "ISONO" : "NAKAJIMA");

    return 0;
}

C : Shopping

問題

スーパーにN個のレジがあり，サゾエさん以外にM人の客が買い物をしている．
M人の各人は時刻a[i]にレジc[i]に並びレジが空いたらb[i]時間かけて会計をする．
サゾエさんは時刻Sにスーパーに来る．来てD時間後に初めてレジに並び，自分の会計の順番が来たら時間をかけずに会計を済ませる．
サゾエさんは会計が終わる度にまたD時間後にレジに並び会計することを合計K回行う(K回会計を行う)．
サゾエさんの並ぶレジを考えてなるべく早くサゾエさんのK回の会計を済ませるとその時の時刻を求めよ．

解法

サゾエさんの並び方に関係なくM人の客の会計の時間は固定される．サゾエさんの会計はその隙間に割り込ませればいい．
つまり，サゾエさんが会計をする時になったらN個のレジで最も早く空くところを求めれば良い．
レジの空く時間をRMQでもって，時間順に各人の行動を更新する．
レジの数Nが大きいが，誰も使わないレジを高々1つしか必要ないのでmin(N, M+1)個のみ考えればよい．

struct RMQ {
    typedef long long T;
    static const T INF = 1LL<<60;
    int N, M; // M == 2**k && M > N
    vector<T> A; vector<int> I; // A[N] == INF
    RMQ(int N_=1): N(N_), M(2<<__lg(max(1, N))), A(N+1, INF), I(M*2, N) {
        for (int i=0; i<N; i++) I[i+M] = i;
        for (int i=M; --i;) I[i] = I[i*2];
    }
    RMQ(const vector<T> &v): N(v.size()), M(2<<__lg(N)), A(v), I(M*2, N) {
        A.push_back(INF);
        for (int i=0; i<N; i++) I[i+M] = i;
	for (int i=M; --i;) I[i] = (A[I[i*2+1]] < A[I[i*2]]? I[i*2+1]: I[i*2]);
    }
    void modify(int i, T v) {
	A[i] = v;
	for (i=(i+M)/2; i>=1; i/=2)
            I[i] = (A[I[i*2+1]] < A[I[i*2]]? I[i*2+1]: I[i*2]);
    }
    int min_i(int x, int y) { return min_i(x, y, 1, 0, M); }
    int min_i(int x, int y, int k, int l, int r) {
	if (r<=x || y<=l) return N;
	if (x<=l && r<=y) return I[k];
        int p = min_i(x, y, 2*k, l, (l+r)/2), q = min_i(x, y, 2*k+1, (l+r)/2, r);
        return (A[q] < A[p]? q: p);
    }
    T min_v(int x, int y) { return A[min_i(x, y, 1, 0, M)]; }
};
const RMQ::T RMQ::INF;

LL N;
int M, K, D, S;
int A[100011], B[100011], C[100011];

map<int, int> mp;
int getR(LL x) {
    if (mp.count(x) == 0) mp.insert(make_pair(x, mp.size()));
    return mp[x];
}

int main() {
    scanf("%lld%d%d%d%d", &N, &M, &K, &D, &S);

    int cnt = 0;
    LL wait = S + D;
    REP (i, M) {
	LL x;
	scanf("%d%d%lld", A+i, B+i, &x);
	C[i] = getR(x);
    }
    
    int L = min(N, (LL)M + 1);
    RMQ rmq(vector<LL>(L, 0));

    for (int i=0; cnt<K; cnt++) {
	while (i<M && A[i] <= wait) {
	    LL t = rmq.min_v(C[i], C[i]+1);
	    rmq.modify(C[i], max(t, (LL)A[i]) + B[i]);
	    i++;
	}

	{
	    LL t = rmq.min_v(0, L);
	    wait = max(t, wait) + D;
	}
    }

    printf("%lld\n", wait - S - D);
    
    return 0;
}

D : Myampus Sequence

問題

M個の関数(0..N-1)がある
各i番目の関数は2通りの命令のうち，どちらか一方だけをランダムに実行する

整数a[i]を画面に出力する
b[i]番目の関数を実行したのち，c[i]番目の関数を実行する

関数0を実行した時，長さNの数列xが出力されることがあり得るか判定せよ．

解法

にゃんぱすー
CYK法で解く．

dp[i][j][t] := 数列x[i..j)を関数tが出力することがあるか true/false

更新は
if x[i] == a[t]:
    dp[i][i+1][t] = true
   
if dp[i][k][b[t]] && dp[k][j][c[t]]:
    dp[i][j][t] = true

dp[0][N][0] がtrueならばyes

ソースコードではtを配列のインデックスにせず，trueになるtだけビットを立てる
O(N^3 M).

int N, M, X[111], A[11], B[11], C[11];

int dp[111][111];
int main() {
    scanf("%d", &N);
    REP (i, N) scanf("%d", X+i);
    scanf("%d", &M);
    REP (i, M) scanf("%d%d%d", A+i, B+i, C+i), B[i]--, C[i]--;

    REP (i, N) REP (j, M) if (X[i] == A[j]) dp[i][i+1] |= 1<<j;
    for (int i=N-1; i>=0; i--) {
	for (int j=i+1; j<=N; j++) {
	    for (int k=i+1; k<j; k++) {
		REP (t, M) {
		    if (dp[i][k] & (1<<B[t]) && dp[k][j] & (1<<C[t]))
			dp[i][j] |= 1<<t;
		}
	    }
	}
    }

    puts(dp[0][N]&1? "Yes" : "No");
    
    return 0;
}

E : How To Make Stars

問題にゃ!

星とは十角形で，内角が30度以上60度以下の鋭角と240度以上270度以下の鈍角が交互に現れる，自己公差のない面積正の多角形である．
i (1 <= i <= n)について，面積がS[i-1]より小さくS[i]以上の星を出力せよ．
ただし，出力するn個の星は共有点を持ってはならない．
また全ての座標の絶対値は5000以下でなければならない．

解法にゃ!

とりあえず一つ星を手作業で作ってそれの縮尺を変えて出力すれば良い．
出力の座標はは-5000から5000の10000x10000の夜空に出力する必要がある．
自分の場合，面積100000の最大の星が651x651の正方形に収まることを確認したので，座標を651ずらしながら出力すると15x15個出力できるのでOK．

typedef complex<double> Point;

const double PI = acos(-1);
const double EPS = 1e-6;
double X[] = { 1, 3, 4.1, 4, 6, 4.2, 4, 3, 1, 2 };
double Y[] = { 1, 2, 1, 3, 4, 4.2, 6, 4, 4.1, 3 };
double cross(const Point &x, const Point &y) {
    return imag(conj(x)*y);
}
double area2(const vector<Point> &g) {
    double r = 0;
    for (int i=0; i<(int)g.size(); i++)
	r += cross(g[i], g[(i+1)%g.size()]);
    return abs(r);
}

int N;

int main() {
    // REP (i, 10) {
    // 	Point p(X[i], Y[i]), q(X[(i+1)%10], Y[(i+1)%10]), r(X[(i+2)%10], Y[(i+2)%10]);
    // 	double d = (arg(p-q) - arg(r-q)) / PI * 180;
    // 	while (d < 0) d += 360;;
    // 	printf("%f\n", d);
    // }
    vector<Point> star(10);
    REP (i, 10) star[i] = Point(X[i], Y[i]);
    double A = area2(star) / 2.0;

    scanf("%d", &N);

    int x = 0, y = 0;
    REP (Z, N) {
	int s;
	scanf("%d", &s);

	printf("%d\n", Z+1);
	double scale = sqrt(s / A) + EPS;
	REP (i, 10)
	    printf("%f %f\n", X[i] * scale + x - 5000, Y[i] * scale + y - 5000);

	// vector<Point> Q;
	// REP (i, 10) Q.push_back(Point(X[i] * scale, Y[i] * scale));
	// eprintf("%d %f\n", s, area2(Q) / 2);

	x += 651;
	if (x+651 > 10000) {
	    x = 0; y+= 651;
	}
    }
    return 0;
}

F : Miko Mi String

問題

与えられた文字列Sが，空でない文字列A,Bを用いてS=ABABAとできるならばその時の長さ最小のABを求めよ

解法

にこにー
前日(正確には同日のAM01:30)のcodeforces #321でも出てきたがこの文字列ABをperiod (Sのprefixで，繰り返すとSが現れる文字列)と呼ぶ．
Aの長さを固定し，S=ABABAを満たすことを考えると，Bの長さ及び，ABの長さも決定する．
Sの長さをn，ABの長さをlenとすると，この時AB=S[0..len)がperiodになっているか判定する．
S[0..n-len)=S[len..n)を満たすことと，S[0..len)がperiodであることが同値．
S[a..a+k)とS[b..b+k)が等しいかどうかの判定はSuffix Array, Rolling Hashなども考えられるが，一方がS[0..k)の場合はZ Algorithmが軽量で適している．

char S[1000011];
int z[1000011];
int N;
int main() {
    scanf("%s", S);
    N = strlen(S);
    int l = 0, r = 0;
    for (int i=1; i<N; i++) {
	if (i > r) {
	    l = r = i;
	    while (r<N && S[r-l] == S[r]) r++;
	    z[i] = r-l; r--;
	} else {
	    int k = i-l;
	    if (z[k] < r-i+1) z[i] = z[k];
	    else {
		l = i;
		while (r<N && S[r-l] == S[r]) r++;
		z[i] = r-l; r--;
	    }
	}
    }

    int ans = N;
    for (int i=1; i<N; i++) {
	// A : S[0..i)
	if (N - 3*i > 0 && (N-3*i)%2 == 0) {
	    int j = (N-3*i)/2; // j = len of B
	    if (z[i+j] == N-i-j) amin(ans, i+j);
	}
    }

    if (ans == N) puts("mitomerarenaiWA");
    else {
	S[ans] = 0;
	printf("Love %s!\n", S);
    }
    
    return 0;
}

G : Travel Support

問題

N個の都市からなるグラフがある．
K人の人々はそれぞれ自分の入る都市から移動して都市1に移動したい．
辺のある都市を移動するにはその辺のお金と1日の時間がかかる．
各人はちょうどライブの日に都市1に着くように自分の都市を出発し，最もお金の掛からないように移動する．
そのような道順が複数ある場合は最も日数がかからない物を選び，それでも複数あるなら，人口の少ない都市を優先的に選んで移動する(要は経路は一意に定まる)．

K人の人々について，
人iは都市x[i]から出発する．また，ライブのd[i]日前に交通費の援助としてお金p[i]円をもらう．
交通費を貰う前に移動する場合や援助だけでは足りない場合は自分のお金を払う必要があるが，いくら用意する必要があるかそれぞれ求めよ．

解法

まず最短経路問題と経路復元を解く．コストは金額と日数の辞書順比較で，移動先の頂点の比較には人口も考慮する．
経路をダブリングするとある頂点からd日移動した時の頂点をO(log n)で求める事ができるので，d[i]日前の頂点を見つけることができる．

ダブリングとは，それぞれの頂点に付いて，都市1への移動するときの1日後の位置，2日後，4日後，... 2^i日後の位置を求めておく方法．

nxt[i][t] := 都市iから都市1へ移動する時，2^t日後にいる都市
tはlog N程度まで求める．
Dijkstra で最短経路問題を求めながらnxt[i][0] つまり，1日後の都市を求める．

テーブルをすべて埋める．
for (int t=0; t<19; t++)
    for (int i=0; i<N; i++)
        nxt[i][t+1] = nxt[nxt[i][t]][t];

頂点iからd日移動したときに居る都市jは
j = i;
for (int t=0; d >= (1<<t); t++)
    if (d & (1<<t)) j = nxt[j][t];

で求めることができる．

交通費援助が貰える日まで移動して，そこまででかかるコストとそこからかかるコストをわけて考えれば良い．

const int MAXV = 100011;
int N, M;
int T[MAXV];
struct Edge {
    int dst;
    LL cst;
    bool operator<(const Edge &y) const {
	return cst > y.cst;
    }
};
vector<Edge> G[MAXV];

int day[MAXV];
LL yen[MAXV];
int nxt[MAXV][20];

int main() {
    scanf("%d%d", &N, &M);
    REP (i, N) scanf("%d", T+i);
    REP (i, M) {
	int a, b, c;
	scanf("%d%d%d", &a, &b, &c);
	a--; b--;
	G[a].push_back((Edge){ b, c });
	G[b].push_back((Edge){ a, c });
    }


    priority_queue<Edge> Q;
    memset(yen, 0x3f, sizeof yen);
    yen[0] = 0;
    Q.push((Edge){ 0, 0 });
    while (!Q.empty()) {
	Edge e = Q.top(); Q.pop();
	if (yen[e.dst] < e.cst) continue;

	EACH (f_, G[e.dst]) {
	    const Edge &f = *f_;
	    if (yen[f.dst] > e.cst + f.cst ||
		(yen[f.dst] == e.cst + f.cst && day[f.dst] > day[e.dst] + 1) ||
		(yen[f.dst] == e.cst + f.cst && day[f.dst] == day[e.dst] + 1 && T[nxt[f.dst][0]] > T[e.dst])) {
		yen[f.dst] = e.cst + f.cst;
		day[f.dst] = day[e.dst] + 1;
		nxt[f.dst][0] = e.dst;
		Q.push((Edge){ f.dst, yen[f.dst] });
	    }
	}
    }

    REP (t, 19) REP (i, N) nxt[i][t+1] = nxt[nxt[i][t]][t];
    
    scanf("%d", &M);
    REP ($, M) {
	int x, d, p;
	scanf("%d%d%d", &x, &d, &p);
	x--;
	LL pay = 0;
	if (d >= day[x]) {
	    pay = max(0ll, yen[x] - p);
	} else {
	    int y=x;
	    for (int i=0; (day[x]-d) >= (1<<i); i++) {
		if ((day[x]-d) & (1<<i)) y = nxt[y][i];
	    }
	    pay = yen[x] - min(yen[y], (LL)p);
	}
	printf("%lld\n", pay);
    }
    return 0;
}