B: Branch Assignment
n 頂点 r 辺の重み付き有向グラフがある。頂点はv_1 ... v_nとする。
そのうち、v_1 ... v_bのb個の頂点はbranch (支店）が置いてあり、v_{b+1}にはheadquarter(本店)がある。
支店をs個のグループに分割したい(s <= b)。
月に一度、各支店は同じグループに属する、自分以外の支店にメッセージをおくる。
メッセージの送信は同じグループ内の全ての組合せに対して独立に行われ、送信者から本店に最短コストで送り、本店から受信者に最短コストで送る。
全体のコスト総和を最小にするようなグループ分割を求め、その最小コストを出力せよ。
グループは少なくとも1つの支店がある必要がある。
A: Balanced Diet
Dannyはm種類の菓子を一つづつ食べる。今までの菓子iを食べた個数をs_iとする。
各菓子iの個数は割合f_iに近い値にしたい。
正確には、今まで食べたお菓子の総数をnとすると、任意のお菓子iは
を満たす必要がある。
すでに、k個のお菓子を食べており、それらは度のタイミングでも条件を満たしている。
今後、最適な順番で菓子を食べることで、最大でいくつのお菓子を食べることができるか求めよ。
無限に食べることができるならばそれを指摘せよ。
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 グラフ
攻撃・溜め・防御のあるゲームのシミュレート
各々そのターンの攻撃力出してみた．
#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; }
ターン制ゲームの勝敗判定
再帰関数にそのターンの人の状態，相手の状態を入力して，そのターンの人が勝てるかどうかを出力させる．
相手に手番を渡した時に一つでも相手負けの場合があるならそのターンの人は勝つことができる．
勝敗をメモ化して同じ計算を回避する．
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; }
スーパーに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; }
M個の関数(0..N-1)がある
各i番目の関数は2通りの命令のうち，どちらか一方だけをランダムに実行する
関数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; }
星とは十角形で，内角が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; }
与えられた文字列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; }
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; }
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ランキングもあるしコード隠した方がいいのなら消す。
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; }
まず、初項a、公差dの長さNの等差数列Aがある。
M個の操作を順に行い、最後に数列のK番目の値を出力せよ。
操作は2種類ある
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; }
文字列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; }
イカの世界は厳しい。
グリッドグラフがあり、ゲソ太はセルSからセルGに移動したい。
各セルは味方・中立・敵・壁の4種類の状態がある。
隣接する味方のセルには1秒で移動可能。
隣接する中立のセルには2秒で移動可能。
敵・壁のセルには移動できない。
また、前方3セルを2秒かけて味方のセルに変更できる。ただし壁のセルや壁を越えた先のセルは変更できない。
最短の時間を求めよ。
グリッドグラフ上の最短経路問題。
4方向各3セルへ辺を張る。この時、セルの状態を変化させる操作を行う場合と行わない場合の2通りを張る(もしくはコストの小さい方だけ張る)。
DはDijkstra。
31日間、毎日映画を1つ見る。
n個の映画があり、i番目の映画はa[i]日目からb[i]日目まで上映している。
i番目の映画を見ると、初めて見るなら100幸福を得、2回目以降は50幸福得る。
幸福の合計を最大化せよ。
どの日も少なくとも1つの映画を行っている制約があるので、同じ映画を見ないと考えても等価。
その日上映してるもので、まだ見たことないもので、終了が最も早いものを貪欲に選べば良い。
ラッキーナンバーは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; }
長さ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; }
グリッドグラフ。8近傍に1秒で移動可能。
N個の爆弾が置いてあり、それぞれ導火線と、時刻0での着火座標がある。
導火線の火は1秒で1セル進む。
ある時刻に導火線の火のあるセルに居るならばその火は消える。
全ての導火線の火を消すとき、最短時間を出力せよ。
N <= 5
dist[H][W][2^N] の状態最短経路問題。
BFSで求める。
立方体の部屋を並べたマンション。
最初、すべての部屋には明かりが付いている。
m個の操作
を全て行った時、明かりのついた部屋は幾つあるか。
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;
}
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を貼るだけ。
(ライブラリコピペ非推奨らしいので軽実装な物を選ぶべき)
標準で平衡二分木のある言語を選ぶのは選択肢として有用だろうか。
考え中。
(x, y)を含む三角形を数える関数ができれば(x1, y1)、(x2, y2)両方を含む三角形は差分で打ち消されるから考えなくてもいいと思うが、簡単に書けないだろうか。
整数の多重集合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;
}
2014-2015 Winter Petrozavodsk Camp, Andrew Stankevich Contest 47 (ASC 47)
Solutions
サイト
http://codeforces.com/gym/100608
問題文
http://codeforces.com/gym/100608/attachments/download/3181/20142015-winter-petrozavodsk-camp-andrew-stankevich-contest-47-asc-47-en.pdf
4人で4時間くらい参加。この記事は終了後に他人のコード見て思ったことがほとんど。
B,G,JがDPの良い問題だと思う。
二次元平面上にドローンがn体、砦がm城、塔がt基ある。
ドローンD、砦F, 2つの塔T1, T2について線分(D, F)と線分(T1, T2)が交差するような集合 { D, F, T1, T2 } が幾つあるか求めよ。
ただし、全てのドローンのy座標は正で、全ての砦および塔のy座標は負であることが保証されている。
どの3点も同一直線上にないことが保証されている。
n <= 1500
m <= 1500
t <= 1500
各砦について独立に数え上げる。
砦一つを中心としてドローン達と塔達を角度で平面走査する。
交点の個数をセグメントツリーで管理する。詳しくは理解していない。
あるab文字列Sについて、任意のi (1 <= i < |S|) について長さiの接頭辞と長さiの接尾辞が異なるならばSをBorderlessと呼ぶ。
2つの整数n, kが与えられるので長さnのab文字列の中で辞書順k番目のBorderlessな物を求めよ。
n <= 64
k <= #{ 長さnのBorderlessなab文字列 }
辞書順最小は貪欲。
先頭から一文字づつ決め打ちした時に、Borderlessがk個以下かどうか判定していく。
例えば
f("aab??"):=Borderlessになるような'?'の埋め方の場合の数
という問題になる。
この問題をDPで解く。
dp[i+1] := S[0..i]がBorderlessになるような'?'の埋め方の組合せ数
とすると、
dp[i+1] = 2^(S[0..i]の'?'の個数)
- (S[0..0] と S[i..i] が同じBorderless文字列の組合せ)
- (S[0..1] と S[i-1..i] が同じBorderless文字列の組合せ)
- (S[0..2] と S[i-2..i] が同じBorderless文字列の組合せ)
...
- (S[0..(i+1)/2] と S[i-(i+1)/2..i] が同じBorderless文字列の組合せ)(S[0..j] と S[i-j..i] が同じBorderless文字列の組合せ)
は dp[j+1]*(2^(S[j+1..i-j-1]の'?'の個数)) で求められる。
Combinatorial Objectというデータ構造及びその集合の記法を定義している。
例
L(P(L(P(L(L(B)),B)),P(B,L(P(P(B,B),P(B,B))))))
整数kが与えられるので、Combinatorial Object集合を一行で出力せよ。
ただし、その集合は重さが(0,1,2,3,4,5)のデータ構造はそれぞれ(1,1,2,5,14,k)通りあるものでなければならない。
120 <= k <= 140
不明
埋め込み
アルファベット26文字のための決定性オートマトン(DFA)について考える。
1単語wだけを認識するDFAは、wの長さをnとするとその最小の状態数はn+2 (初期状態+各文字を読んだ状態+デッドエンド) である。
以下の条件を満たす2つのDFA X, Yを出力せよ。
ただしそのようなX, Yが存在しないならそれを指摘せよ。
どこか1文字の直後に*を入れるとwを認識しつつ、状態数が1減る。
なぜならその文字を読んだかどうかの状態が不要になるから。当然w以外の文字列も認識する。
例えば
aabc : 状態数6 aabc* : 状態数5 aab*c : 状態数5 aa*bc : 状態数5 a*abc : aa*bcに直さないとDFAにならない a*bc : 状態数4
aa*bcとa*bcの積集合はw以外にも存在するのでこの2つは選ばないように、違う文字の最後に*を入れたDFAを2つ選べば良い。
wが全て同じ文字であった場合はX, Yは存在しない。
以下の条件を満たすn x nの魔方陣に似たものを出力せよ。
3 <= n <= 30
ある素数pがどの行・列についても一つになるように配置する(つまり1~nの順列)と良さそう。
n奇数の場合は
1 2 3 5 7 1 11 13 17 19 7 1 2 3 5 11 13 17 19 1 5 7 1 2 3 X 13 17 19 1 11 3 5 7 1 2 17 19 1 11 13 2 3 5 7 1 19 1 11 13 17
のように右下がり斜めと右上がり斜めを重ねれば良い
偶数の場合はもう少し不規則な物にする必要がある。n x n の正方形を3, 4つ掛けても良い。
Interactive.
木がある。コンテスタントとジャッジが交互に木の頂点に色を塗っていくゲームを行う。
木の頂点数<=1000
4色もあるのでどうとでもなる。
(隣接する頂点に塗られている色の種類が多い順, 次数が高い順)、の辞書順で勝てる。
0~b-1の出るb面ダイスがある。
アリッサとベンが2種類のゲームを行う。
どちらのゲームも二人はそれぞれd桁のセルを持っている。
サイコロを振って出た目を見た後、空いているセルにその数を書く。これをmoveと呼ぶ。
二人とも全てのセルが埋まったとき、大きい数になっている人が勝ち。
1つ目のゲームは
2つ目のゲームは
それぞれのゲームで互いに勝率を最大にする行動をとったとき、アリッサの勝率を両方答えよ。
d <= 10
b <= 10
(b+1)^d <= 3000
(b+1)^d が1人のプレイヤーの状態数そのものなので、DPで解く。
n頂点のグラフGについて
V(u, i)を頂点uからの距離がiのである頂点集合とする。
D(u, i)をbag{ deg(x) | x in V(u, i) } とする。bagは多重集合の意味、deg(x)はxの次数。
D(u)をリスト[ D(u, 0), D(u, 1) , ... , D(u, n-1) ] とする。これをuのdegree profileと呼ぶ。
Gの全ての頂点についてのdegree profileの多重集合をGのdegree profileと呼ぶ。
整数nが与えられるので、次の条件を満たす2つのグラフG, Hを出力せよ。
ただしそのようなG, Hが存在しないならばそれを指摘せよ。
この2つのグラフはdegree profileが互いに等しく、同型でない。
しかし、各頂点についてdegree profile が異なるという条件を満たさない。
3 <= n <= 100
不明
頂点数6のヒントになりそうなものが問題文中にあるが、頂点のdegree profileが異なると言う条件を満たさない。実は頂点数が6以下の時はG, Hは存在しないらしい。
頂点7の場合を何とか捻出し、それにパスを取り付けて頂点数を調節する解法が出されていたのを確認した。
凸なポリオミノが与えられる。
ただし凸とは、ポリオミノを形作る水平・垂直な線分が途切れて分かれていないこと。
ポリオミノの2つのセルa, bについて、aからbへ移動するのに少なくとも必要な向きを変える回数をturn(a, b)とする。
全てのセルの組合せa, bについてturn(a, b)の最大値をJinxietyと呼ぶ。
Jinxietyを求めよ。
サイズ h*w
h, w <= 2000
DP
凸の条件は言い換えると任意のセルからセルへの移動は右・下とか右・上とかの2方向を切り替えながら進めばよいということ。
左と上だけを使う場合をDPで求める。また上下反転したのち同様に求める。
left[y] := y行目の一番左にあるポリオミノのセルのx座標
up[x] := x列目の一番上にあるポリオミノのセルのy座標
dp[y][x] := セル(x, y)から左と上だけで行ける範囲のセルで、
向きを変える回数の最小値の最大値
dp[y][x] =
0 if (x, y)がポリオミノの外
0 if [0..x-1]*[0..y-1]が全てポリオミノの外
dp[up[x]][left[y]] + 1 otherwise上下反転させた場合も含めて、dpテーブルの最大値がJinxiety。
C++では関数オブジェクトのほうが関数より速い。呼び出しの時間に差がある様子。
数回呼ぶだけなら誤差だが呼ぶ回数が増えるとその速度は有利。
std::sortの比較関数に関数や関数オブジェクトを与える。
bool cmp(int x, int y) { return x < y; }
struct cmp_c { bool operator()(int x, int y) { return x < y; } } cmp;
ファンクタとかファンクショノイドとか呼ばれる。cmpは上の関数のcmpと同じように呼ぶことができる。
auto cmp = [](int x, int y) -> bool { return x < y; };
C++11の記法。関数オブジェクトが作られる。
cmpの型はfunction< bool(int,int) >かと思われるがautoで宣言しないと性能が何故か低下する。
int main() { int N = 1e7; vector<int> v(N); for (int i=0; i<N; i++) v[i] = rand(); clock_t s, t; s = clock(); sort(v.begin(), v.end(), cmp); t = clock(); printf("%f\n", (double)(t-s) / CLOCKS_PER_SEC); return 0; }
int型 1e7個のvectorをソートするだけの時間を測る。
"コールバックなし"はsortのコールバック関数を渡さず昇順ソートした結果。
関数を使った場合だけ遅い。
fibonacci数を二重再帰で定義する。
LL fib(int n) { if (n<2) return n; return fib(n-1) + fib(n-2); }
関数オブジェクトの再帰は4通り考えたので全部書く。
struct fib_c { LL operator()(int n) { if (n<2) return n; return fib_c()(n-1) + fib_c()(n-2); } } fib;
fib_c()でオブジェクトを作りまくって一見遅そうにも見えるが実際は速い。
struct fib_c { LL operator()(int n) { if (n<2) return n; return (*this)(n-1) + (*this)(n-2); } } fib;
struct fib_c { LL operator()(int n) { if (n<2) return n; return this->operator()(n-1) + this->operator()(n-2); } } fib;
struct fib_c { LL operator()(fib_c f, int n) { if (n<2) return n; return f(f, n-1) + f(f, n-2); } } fib;
再帰関数のない言語などで再帰する方法。
ただし呼ぶときにはfib(fib, 45)の様に、第一引数に自身を与える。
おそらくオブジェクトを新しく作っているだけ。
function<LL(int)> fib = [](int n) -> LL { if (n<2) return n; return fib(n-1) + fib(n-2); };
ラムダ式は再帰にする場合autoで宣言できない。
autoで宣言しない場合、ラムダ式は遅い。
その他Yコンビネータ使う方法もあるが面倒。
各実装でfib(45)を計算するのにかかる時間は以下のとおり。
ラムダ式の再帰関数は再帰が比較的浅くても手元の環境だとsegmentation faultした。
関数と関数オブジェクトについては関数オブジェクトの方が若干深くまで再帰できたが、そもそも関数がスタックオーバーフローするなら実装が悪い・誤りだと思った方がいい。
実際関数オブジェクトは関数より速い。実装コストも対して変わらないので関数オブジェクトを使うのも良い。関数の呼び出しがボトルネックになる場合はあまり経験ないが、sortのコールバック関数を関数オブジェクトにする程度の実装はしようと思う。
またラムダ式の再帰は致命的に性能が悪いので避けたい所。
再帰関数は関数オブジェクト自身をコールバック関数にするのが最も速いが、あまり綺麗な実装とは言いづらい。再帰の呼び出しが多くなる場合はループかスタックで対処するほうがよっぽど良い。
余談ではあるが、int列を絶対値でソートしたり、複素数列を角度でソートするような、加工した値を規準にソートしたいときは、専用の比較関数を作るよりも、pairのfirstに加工した値・secondに元の値を置いてソートしたほうが大抵速い。同じ値を何度も絶対値取るのは無駄。
Live Archive
Root :: Regionals 2011 :: Europe - Central
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=526
良問。スペシャルジャッジに対応していない様子なので、一部AC出ない（単にWAなのかも知れないが）。
入出力・ジャッジ解あり
http://contest.felk.cvut.cz/11cerc/solved.html
Boring Card GameとRacing Car Trailが良問。
データ構造好きならStrange Regulationsも。
Live Archive 5879 - Boring Card Game - でも今日はSRMあるから
Live Archive 5880 - Vigenere Cipher Encryption - でも今日はSRMあるから
Live Archive 5881 - Unique Encryption Keys - でも今日はSRMあるから
Live Archive 5882 - Racing Car Trail - でも今日はSRMあるから
Live Archive 5883 - Stack Machine Programmer - でも今日はSRMあるから
Live Archive 5884 - Strange Regulations - でも今日はSRMあるから
Live Archive 5885 - Vigenere Cipher Analysis - でも今日はSRMあるから
Live Archive 5886 - The Grille - でも今日はSRMあるから
Live Archive 5887 - Unchanged Picture - でも今日はSRMあるから
Live Archive 5888 - Stack Machine Executor - でも今日はSRMあるから
