University of Aizu Competitive Programming Camp 2015 Day 2
問題・解法
http://judge.u-aizu.ac.jp/onlinejudge/contest_standing.jsp?id=ACPC2015Day2
5時間 12問
1日目は参加してない。公式の解説とか上がるのかな。
問題文は全て意訳。AOJランキングもあるしコード隠した方がいいのなら消す。
A : Divisor
問題
N (<=12)個の約数を持つ最小の自然数を出力せよ。
解法
int C(int x) { int r = 0; for (int i=1; i<=x; i++) if (x % i == 0) r++; return r; } int n; int main() { scanf("%d", &n); for (int i=1; ; i++) { if (C(i) == n) { printf("%d\n", i); return 0; } } return 0; }
B : Array Update
問題
まず、初項a、公差dの長さNの等差数列Aがある。
M個の操作を順に行い、最後に数列のK番目の値を出力せよ。
操作は2種類ある
- 0 y z : swap(A[y], A[z])
- 1 y z : A[y] <- z
N <= 10^8
M <= 10
解法
Aを陽に持つのはメモリが厳しい気がする。
操作に関係ないA[i] はa+d*(i-1)で求め、操作が行われたところだけmapで記憶する。
int N, A, D, M, K; map<int, LL> mp; int x, y, z; LL giveMe(int i) { if (mp.count(i) == 0) { mp[i] = A + (LL)D * (i-1); } return mp[i]; } int main() { scanf("%d%d%d%d", &N, &A, &D, &M); REP (i, M) { scanf("%d%d%d", &x, &y, &z); if (x == 0) { LL p = giveMe(y), q = giveMe(z); mp[y] = q; mp[z] = p; } else { mp[y] = giveMe(z); } } scanf("%d", &K); // REP (i, N) eprintf("%lld ", giveMe(i+1)); eprintf("\n"); LL ans = giveMe(K); printf("%lld\n", ans); return 0; }
C : String Compression
問題
文字列Sが与えられる。
012345は0-5、efghijはe-i、のように圧縮できる。
Sを任意に並び替えて圧縮を行うとき、長さの最小値を出力せよ。
解法
各文字の出現頻度を出すだけ。貪欲に。
char S[111]; int C[256]; int update(char p, char l) { int ret = 0; while (true) { int len = 0; for (char c=p; c<=l; c++) { if (C[c] == 0) break; else { C[c]--; len++; } } if (len > 3) { ret += len - 3; } else { break; } } return ret; } int main() { scanf("%s", S); int N = strlen(S); REP (i, N) C[S[i]]++; for (int c='a'; c<='z'; c++) N -= update(c, 'z'); for (int c='0'; c<='9'; c++) N -= update(c, '9'); printf("%d\n", N); return 0; }
D : Squid Ink
問題
イカの世界は厳しい。
グリッドグラフがあり、ゲソ太はセルSからセルGに移動したい。
各セルは味方・中立・敵・壁の4種類の状態がある。
隣接する味方のセルには1秒で移動可能。
隣接する中立のセルには2秒で移動可能。
敵・壁のセルには移動できない。
また、前方3セルを2秒かけて味方のセルに変更できる。ただし壁のセルや壁を越えた先のセルは変更できない。
最短の時間を求めよ。
解法
グリッドグラフ上の最短経路問題。
4方向各3セルへ辺を張る。この時、セルの状態を変化させる操作を行う場合と行わない場合の2通りを張る(もしくはコストの小さい方だけ張る)。
DはDijkstra。
E : Movie
問題
31日間、毎日映画を1つ見る。
n個の映画があり、i番目の映画はa[i]日目からb[i]日目まで上映している。
i番目の映画を見ると、初めて見るなら100幸福を得、2回目以降は50幸福得る。
幸福の合計を最大化せよ。
解法
どの日も少なくとも1つの映画を行っている制約があるので、同じ映画を見ないと考えても等価。
その日上映してるもので、まだ見たことないもので、終了が最も早いものを貪欲に選べば良い。
F : Lucky Number
問題
ラッキーナンバーは0~N-1の数で、毎日変化する。
ある日のラッキーナンバーAなら次の日のラッキーナンバーBは
B = ( A + j ) % N （ただし j は 0 <= j < N かつ （j / K 切り捨て） が偶数となる全ての整数である )
jはランダムに選ばれる。Nは2Kの倍数。
Q個の質問に答えよ。
質問 a b c は
ある日のラッキーナンバーa、b日後のラッキーナンバーcであるような b+1 日間のラッキーナンバーの選ばれ方の場合の数。
N <= 5000
K <= 5000
Q <= 100000
a < N
b <= 5000
c < N
解法
動的計画法。
c' := c - a (mod N) とずらして、aが0である場合のみ考える。
dp[i][j] := i日後の値がjである場合の数 最終的に答えはdp[b][c']
値0の次の日は[0, 1, .., K-1], [2K, 2K+1, .., 3K-1], .., [ .., N-K-1]。
つまり最初のK個に加算、次のK個は飛ばす、次のK個に加算...。
累積和でO(NM)でdpのテーブルを作って各クエリはO(1)、問題全体の計算量はO(MN+Q)。
int N, M, K, Q; Mint dp[5011][5011]; Mint buf[15011]; int a, b, c; int main() { scanf("%d%d%d%d", &N, &M, &K, &Q); dp[0][0] = 1; int J = 0; while (J < N) J += 2 * K; REP (i, M) { memset(buf, 0, sizeof buf); REP (t, N) { buf[t] += dp[i][t]; buf[t+K] -= dp[i][t]; if (t+J < 2*N) buf[t+J] -= dp[i][t]; if (t+J+K < 2*N) buf[t+J+K] += dp[i][t]; } REP (t, 2*N) if (t+1 < 2*N) buf[t+1] += buf[t]; REP (t, 2*N) if (t+2*K < 2*N) buf[t+2*K] += buf[t]; REP (t, N) dp[i+1][t] = buf[t] + buf[t+N]; } REP (_, Q) { scanf("%d%d%d", &a, &b, &c); c = (c - a + N) % N; printf("%d\n", dp[b][c].get<int>()); } return 0; }
G : String Conversion
問題
長さnの文字列Sを同じ長さの文字列Tに変換したい。
操作は
はじめに任意に並び替える(コスト0)。
次に2種類のアルファベットを選んで全て入れ替える(コスト0)。繰り返し何度行ってもいいが、順番に行う。
最後に1文字を任意の1文字に書き換える。書き換える度にコスト1。
解法
悲劇的な問題文を除けばDEFより簡単かも。
Sで出現頻度の多い文字はTで出現頻度の多い文字にしておきたい。
int N; char buf[100011]; int A[26], B[26]; int main() { scanf("%d", &N); scanf("%s", buf); REP (i, N) A[buf[i]-'a']++; sort(A, A+26); scanf("%s", buf); REP (i, N) B[buf[i]-'a']++; sort(B, B+26); int ans = 0; REP (i, 26) ans += abs(A[i] - B[i]); printf("%d\n", ans/2); return 0; }
H : Bomb Removal
問題
グリッドグラフ。8近傍に1秒で移動可能。
N個の爆弾が置いてあり、それぞれ導火線と、時刻0での着火座標がある。
導火線の火は1秒で1セル進む。
ある時刻に導火線の火のあるセルに居るならばその火は消える。
全ての導火線の火を消すとき、最短時間を出力せよ。
N <= 5
解法
dist[H][W][2^N] の状態最短経路問題。
BFSで求める。
I : Lights of Apartment
問題
立方体の部屋を並べたマンション。
最初、すべての部屋には明かりが付いている。
m個の操作
- x座標がkの部屋の明かりをすべて消す
- y座標がkの部屋の明かりをすべて消す
- z座標がkの部屋の明かりをすべて消す
を全て行った時、明かりのついた部屋は幾つあるか。
解法
2 hundred over
包除原理。
各操作で対象となる部屋をそれぞれA, B, Cすると
all - A - B - C + (A&B) + (B&C) + (C&A) - (A&B&C)
部屋の総数は高校数学でO(1)。
リカちゃんとハルトくんの共通部分なんかは図形数で求められるので、ひとりずつ頑張る。
LL T2(LL N) { return N * (N+1) / 2; }
LL T3(LL N) { return N * (N+1) * (2*N+1) / 6; }
LL T4(LL N) { return N * (N+1) / 2 * N * (N+1) / 2; }
int N, M;
VI E, S, B;
LL F[50011], F2[50011], G[50011];
int main() {
scanf("%d%d", &N, &M);
REP (i, M) {
int x, z;
scanf("%d%d",& x, &z);
if (x == 0) E.push_back(z);
if (x == 1) S.push_back(z);
if (x == 2) B.push_back(z);
}
LL ans = T4(N);
EACH (e, S) {
if (*e > N) continue;
ans -= T3(N) - T3(*e-1);
F[*e] += 1;
F2[*e] += T2(N) - T2(*e-1);
}
REP (i, N+1) {
F[i+1] += F[i];
F2[i+1] += F2[i];
}
EACH (e, B) {
if (*e > N) continue;
ans -= T3(N) - T3(*e-1);
ans += F[*e] * (T2(N) - T2(*e-1));
ans += F2[N+1] - F2[*e];
G[*e] += 1;
}
REP (i, N+1) G[i+1] += G[i];
EACH (e, E) {
LL d = sqrt(2.0 * *e + 0.25) - 0.5;
while (T2(d) < *e) d++;
if (d > N) continue;
ans -= d*d;
ans += F[d] * d;
ans += G[d] * d;
ans -= F[d] * G[d];
}
printf("%lld\n", ans);
return 0;
}
J : String Crossing
問題
N個の文字列S[0] .. S[N-1]がある。
Q個のクエリを順に実行する。
クエリは2種類
1 a b c d: (S[a], S[c]) := (S[a][0..b) + S[c][d..), S[c][0..d) + S[a][b..)) 2 a b c: S[a][b] := c
最後にN個の文字列を出力せよ。
解法
RopeとかCordとか。
ノードにcharを持たせて平衡二分木Seq。
merge/splitが必要なので実装が楽なTreapかRBSTを貼るだけ。
(ライブラリコピペ非推奨らしいので軽実装な物を選ぶべき)
標準で平衡二分木のある言語を選ぶのは選択肢として有用だろうか。
K : Point in The Triangle
問題
解法
考え中。
(x, y)を含む三角形を数える関数ができれば(x1, y1)、(x2, y2)両方を含む三角形は差分で打ち消されるから考えなくてもいいと思うが、簡単に書けないだろうか。
L : Combination and Multiplication
問題
整数の多重集合Aの部分集合で、その和がKになるものを全て求め、その要素の積の全ての積を出力せよ。
解法
動的計画法。
部分集合の場合の数を求めるだけなら個数制限付きナップサック問題である。
このDPを求めるときに、一緒に積を求めれば良い。
dp[i+1][j] := (X[i]までの数を使って合計がjの場合の数, その部分集合の積) 最終的な答えはdp[N][K].second 初期値はdp[0][0] = (1, 1), dp[0][j] = (0, 1) dp[i][j] = (f, s) にxをy個加算する場合、xはf個の集合にy個づつ付くので dp[i+1][j+x*y].first += f dp[i+1][j+x*y].second *= s * pow(x, f*y)
このままではO(NK^2)以上なので、この更新を個数制限付きナップサックでやれば良いO(NK * pow)。
dp[i][j].firstはpowの肩に来る値になる。1999が素数なので1998でmodとっても良いはず、powの計算量を消せる。
LL powMod(LL x, LL y, LL m) {
LL r = 1;
for (; y; y>>=1) {
if (y&1) r = r * x % m;
x = x * x % m;
}
return r;
}
const LL MOD = 1999;
const int MAX = 10000;
LL inv[MAX+1];
void init() {
inv[1] = 1;
for (int i=2; i<=MOD; i++) inv[i] = inv[MOD%i] * (MOD-MOD/i) % MOD;
}
int N, K;
int X[111], Y[111];
typedef pair<int, int> Pii;
Pii dp[111][30011];
Pii operator*(const Pii &x, const int &y) {
return Pii(x.first, (LL)x.second * powMod(y, x.first, 1999) % 1999);
}
Pii operator+(const Pii &x, const Pii &y) {
return Pii((x.first + y.first) % 1998, x.second * y.second % 1999);
}
Pii operator-(const Pii &x, const Pii &y) {
return Pii((x.first - y.first + 1998) % 1998, x.second * inv[y.second] % 1999);
}
int main() {
init();
scanf("%d%d", &N, &K);
REP (i, N) scanf("%d%d", X+i, Y+i);
REP (i, N+1) REP (j, K+1) dp[i][j] = Pii(0, 1);
dp[0][0] = Pii(1, 1);
REP (i, N) {
REP (s, X[i]) {
Pii d(0, 1);
int pp = powMod(X[i], Y[i], 1999);
for (int j=s; j<=K; j+=X[i]) {
d = d * X[i] + dp[i][j];
dp[i+1][j] = dp[i+1][j] + d;
if (j - Y[i] * X[i] >= 0) d = d - dp[i][j-Y[i]*X[i]] * pp;
}
}
}
printf("%d\n", dp[N][K].second);
return 0;
}
