方針 O(Qsqrt(N))で間に合いそうなので平方分割を試す クエリは[l, r)で0-indexedとする。 f(x, i) = 106i ord(S[x][i])(0<=i

与えられた頂点のK個からなる部分集合について、最適なPの座標はx座標の中央値となる。 なので、Pの候補は与えられた頂点のx座標に限られる。 これらx座標を昇順に見ていく。(以下、x[k]<x[k+1]とする) P=x[0]としてとりあえず近いK個を集合Lに入れておく。残った頂点は集合Rに入っているとする。 x[k] -> x[k+1]と変化したとする。x[k]のときの最適な構成Lから、x[k+1]のとき</x[k+1]とする)>…

grundy数を出力して図にしてみる。 十分大きな整数について、そのgrundy数が34周期になっていることがわかる。 int dp[201]; int g(int n) { if (dp[n] != -1)RT dp[n]; set<int> S; for (int i = 0; i < n; ++i) { int l = max(0, i - 1); int r = max(n - 2 - i</int>…

int n; cin >> n; vector<mint> pw(n + 1), a(n + 1); pw[0] = 1; rep(i, n) { pw[i + 1] = pw[i] * 2; int x; cin >> x; a[i + 1] = x; } mint re, b; rep(i, n) { b = b * 2 + a[i]; re += (b + a[i + 1])*pw[n - 1 - i]; } cout << re << endl;</mint>

再帰で解く。 とりあえず、d[x]は最大の深さの分まで求めればいい。それ以降は0が続くので。 頂点xのxを除くすべての子孫についてdが計算済みとして、d[x]を計算する。d[x]のすべての子供だけを見ればd[x]が求まる。つまり、すべての子供yについてd[x][i+1] …

とりあえず最大の入力以下の自然数の約数を列挙しておく。入力中最大の自然数をMとして、M以下の各自然数について、その倍数を見ていく。調和数を考えるとの計算量とわかる。 各データセットについて、別々に処理する。 A, B, Cのうち、少なくともひとつの約…

単一始点最短経路問題で、すべての頂点に最短で到達するのに必要な辺だけを選ぶと木になることが知られている(最短経路木)。 なので、この問題では最短経路木を列挙すればいいことがわかる。根でない頂点vに最短距離で到達した時、直前の頂点をuとする。d(x)…

f(x) を「中央値をxとする部分文字列の数」とする。f(m)が解。 とおくと を得る。 あとは、g(y)を求めるだけ。g(y)の値は、中央値がy以上の部分文字列の数を表す。 部分文字列の中央値がy以上である必要十分条件は (y以上の値の数)>=(y未満の値の数) とわか…

数列なので中央値mはちょうど1つだけある。mの位置に注目すると、条件を満たす部分文字列は、mから左へ0以上、右へ0以上の長さだけ伸ばしたものに限られる。 部分文字列がmの左側へl, 右側へrだけ伸ばしたものであるとする。また、m以外の値はmとの大小関係…

ある非負整数が3の倍数かどうかは、各桁の値の和が3の倍数かどうかを調べればいい。なので dp[i][j] := 「もとの数字の上位i桁まで確定して、今作っている数の桁の和を3で割ったあまりがjであるときの最大の仕切りの数」 のようなDPを解く。 int dp[200005][…

一人しかいない場合を考えてみる。その人が見る花壇の長さをa, その花壇に含まれるバラの数をx, ユリの数をyとおく。 x+y=aの条件でxyを最大にしたい。 を得る。 よってaが偶数の時で最大。 aが奇数のときで最大。 簡単のためとすると、x, yの値はとなる。要…

愚直なDPを考えてみる。 f(i, j, k) = 「i人目まで確定して、前の人がj円払った時、合計金額がk円である場合の数」 これでは間に合わない。 とりあえず、最初の人の募金額を0~Sの範囲で総当たりして固定し見てよう。先の人も含めて、少なくともその額を支払…

最適解が2点以上含む場合は、そのうちの2点を通る円でその最適解を必ず構成できる。 最適解を構成する頂点の集合をSとする。(|S|>=2)。Sの外側の点だけを拾って凸包を構成する。ただし、Sの点が一直線上に並ぶ場合は線分を構成する。これをTとおく。Sの点を…

ライブラリがあれば楽にとけるやつ。HL分解して、マークしたかどうかはBinary Indexed Treeなどを使うだけ。 vector<vi> G(N); FOR(i, 1, N) { int p; cin >> p; --p; G[p].push_back(i); } HLDecomposition hld(G); // 0ならばマークされていない。 // そうでな</vi>…

K番目の解をanswer(K)と表すことにする。 とおくと が解。 f(x)の条件の部分をもう少し緩くしてみる。 とおくと、後者の(i, j)の集合は、前者のそれを含むので が成り立つ。更に、 のときが成り立つ。したがって以下が成り立つ。 g(x)が簡単に求まるとしてan…

BとCの間区切りを総当たりで固定する。 このとき、前半部分と後半部分の両方ともできるだけ均等に分けるのが最適。なぜか。 AとBの区切りを考えてみよう。AとBをできるだけ均等に（差が最小になるように）分けたときの小さい値をlow, 大きい値をhighとする。…

B[i] = A[i] - iとおく。 入力例2ではB[i]は以下のような値をとっている。なお図ではb=2と仮置きしている。 であるから、 これは上図では点と直線y=bの距離の和を求めればいいことがわかる。 直線bを上下に動かしてみると以下の事がわかる。 一番上の点より…