2020-05-23

素敵な宝箱 - yukicoder No. 1060

立式する.

私が i 番目の宝石を合計 x 個とるとする.
i 番目の宝石は計 Si 個あるとする.
X - Y は, $x^2 - (S_{i} - x)^2 = 2 S_{i} x - S_{i}^2$
(x = $A_{1'i} + ... + A_{k'i}$ )

宝箱ごとに, すべての宝石 i に関して 2 Si x の合計を求める.
私は, 大きい順に 1 つとばしで得る.

最後に, すべての宝石 i に関して Si^2 を引く.

ソースコード
 https://yukicoder.me/submissions/486237

2020-05-18

重みつき unionfind

重み付き unionfind で何ができるか.

任意の 2 つの要素で, どちらがどれだけ大きいかという情報を持つことができる.

以下の問題文を参考に.
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_B&lang=jp

まず, 重みなし unionfind とコードを比べてみよう

struct UnionFind {
  vector<int> data;
  int n;
  UnionFind(int n) : data(n, -1), n(n) {}
  bool connect(int x, int y) {
      if ((x = root(x)) == (y = root(y))) return false;
      if (data[x] > data[y]) swap(x, y);
      data[x] += data[y]; data[y] = x; n--;
      return true;
  }
  bool issame(int x, int y) { return root(x) == root(y); }
  int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
  int size(int x) { return -data[root(x)]; }
  int size() { return n; }
};

unionfind - tac_12のブログより

struct WeightedUnionFind {
  vector<int> data;
  vector<ll> ws;
  int n;
  WeightedUnionFind(int n) : data(n, -1), ws(n) { }
  bool connect(int x, int y, ll w) {
    w += weight(x); w -= weight(y);
    if ((x = root(x)) == (y = root(y))) return false;
    if (data[x] > data[y]) swap(x, y), w = -w;
    data[x] += data[y]; data[y] = x; ws[y] = w;
    return true;
  }
  bool issame(int x, int y) { return root(x) == root(y); }
  int root(int k) {
    if (data[k] < 0) return k;
    int par = root(data[k]);
    ws[k] += ws[data[k]];
    return data[k] = par;
  }
  int size(int x) { return -data[root(x)]; }
  int size() { return n; }
  ll diff(int x, int y) { return weight(y) - weight(x); }
  ll weight(int t) { root(t); return ws[t]; }
};

一方の頂点の数の大きさが他方の頂点の数の大きさよりどれだけ大きいかで, 「数の大きさ」を重みと呼ぶ.

diff(int x, int y) は, 頂点 y の重み - 頂点 x の重みを返す.

root(int k) では, 根に近い方から再帰的に根の頂点番号をもらうわけだが, 同時にその頂点の重みを求める.
根は, その頂点番号を返すだけなので, 重みは変わらない.
根の重みは常に 0 である.

ある 2 頂点の重みの差を求めるとき, 根に対する相対的な重みを利用する.

根以外の頂点で, どう重みを持ち, どう重みを計算するのか.
connect では引数で, 頂点 y の重みが頂点 x の重みよりどれだけ大きいかが与えられる.
すなわち, ある 2 頂点の重みの差である.
頂点の重みは, 根からの相対的な重みであり, 根の重みは 0 なので, 根が根でなくなるタイミングを除いて root の ws[k] += ws[data[k]] は非 0 を足されない.
根が根でなくなるタイミングについては後に考える.

重みなし unionfind において, 各頂点常に正しい根の情報を持っているとは限らず, root を呼ばれたタイミングで正しい根を持つように, weight を呼ばれたタイミングで root を呼び, 正しい根と重みの情報を得る.

connect について説明する.
重みなし unionfind と同じく, x の集合の根は根のまま.
ここで, y の集合の根が根でなくなる.
x の集合の重みは基準の x の根の重みが 0 のままなので変わらないが, y の集合の重みは全体を変える必要がある.
満たされるべき条件は, connect の引数で与えられる.
すなわち, 2 集合の, 根とは限らない頂点 x, y に関して, x の重み + w = y の重み.
ここで, x の集合と y の集合の繋がり方であるが, x の集合の根に y の集合の根が繋がる.
y の集合の根の重みは 0 からどう変わるか.
結論から言うと, w + x の重み - y の重みである.
root(y) で y の重みを計算したら, x の重み + w になっていたらいい.
root を見ると, 根の情報が更新される前に根の重みが足される.
更新される前の根の重みは w + x の重み - y の重みになったのであった.
よって, y の重み + (w + x の重み - y の重み) = x の重み + w.
結局, y の集合全頂点の重みが w + x の重み - y の重みされているので, y の集合内での相対的な重みは変わっていない.

参考
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3810883#1

2020-05-17

unionfind

前提知識
構造体, dfs

struct UnionFind {
  vector<int> data;
  int n;
  UnionFind(int n) : data(n, -1), n(n) {}
  bool connect(int x, int y) {
      if ((x = root(x)) == (y = root(y))) return false;
      if (data[x] > data[y]) swap(x, y);
      data[x] += data[y]; data[y] = x; n--;
      return true;
  }
  bool issame(int x, int y) { return root(x) == root(y); }
  int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
  int size(int x) { return -data[root(x)]; }
  int size() { return n; }
};

size() では, n を返す.
n は, 集合の個数.
最初, 頂点数.
どれも connect されていないので, すべてが大きさ 1 の集合.

size(int x) では, 頂点 x を含む集合の大きさを返す.
data[root(x)] = data[x を含む集合のグラフの根].
実は, data[根] は, その根を含む集合の大きさの負の数である.
例として, 最初, すべての頂点が大きさ 1 の集合で, 任意の頂点 v に対し, data[v] = -1.

各頂点の根は, root(int x) を呼び出されるタイミングで求める.
data[x] < 0 になるまで, 再帰的に root を呼ぶ.
根が呼ばれたら, 頂点番号 x を返すだけ.
根の data には, 根を含む集合のサイズの負の数が入っているが, これには触れられない.
根に近い方から, 根の頂点番号をもらい, 伝搬させていく.
再帰的に呼ばれた頂点の親は根に変えられ, 深さ 1 になっている.

コンストラクタの UnionFind(int n) : ... についても触れておく.
n が与えられて, data を, サイズが n で, すべてを -1 で初期化する.
また, UnionFind 内の変数 n に, 与えられた n を代入する.
書き方の問題だが, 別に UnionFind(int n) : n(n) { data = vector(n, -1); } でもいい.
UnionFind(int n) { n = n; data = vector(n, -1); } はダメ.

issame は, x, y 各々根を求めて同じか, すなわち, x, y が同じ集合の頂点か調べる.

connect を見る.
x, y 各々根を求めて, 同じなら既に同じ集合.
違う集合の頂点なら, 繋げる.
どう繋げるか.
頂点数が小さい方の根を, 頂点数が大きい方の根に繋げる.
x, y は根になっているとして, x の集合のサイズが 4, y の集合のサイズが 3 とする.
data[x] = -4 < -3 = data[y] より, swap しない.
x の集合に y の集合を繋げる.
data[x] = -4 - 3 = -7.
data[y] = x で, y の親が x になった.
n-- とあるが, n は集合の個数で, y の集合が x の集合に合併されたので, 1 減った.

複雑な例を図示しようとしたが, 頻繁に root が呼ばれるので, 大抵深さ 1 になる.

2020-05-14

Bracket Sequencing - abc 167 f

#かっこ列 #kyopro_friends さん #貪欲法

開いてる ")" が少ない文字列から左から埋めた方がいいか?

開いてる ")" というのは, 相手の "(" がいない ")"

ある時点で, "(" の数より ")" の数が多くなってはダメだから
それの相手の "(" が手前にいないとかっこ列にならない

次の方法で分析する
開いてる ")" の数は, 始め 0 として, "(" が来たら +1, ")" が来たら -1 する

f:id:tac_12:20200514154630p:plain:w300
f:id:tac_12:20200514152613p:plain:w300
f:id:tac_12:20200514154651p:plain:w300

折れ線グラフで, ペアになってるかっこの部分を引っこ抜く
上図の, 囲ったオレンジの部分

ペアになってるとこを全て引っこ抜くと谷になる
山があれば, ペアが残ってる

そして, その谷の下がってる部分が開いてる ")" の数

実は, 一番小さいところの数字である
上図の上から, -3, -2, 0

閉じてる ")" は, 相方の "(" による +1 を -1 する

かっこ列の条件は,
1. "(" と ")" の数が等しいこと,
2. すべての ")" に相方がいること

上の表現方法でいうと,
1. 最後の数字が 0 であること
2. 途中で負にならないこと

1. は文字列の順番に関係ない

開いてる ")" の数は 2. に関係するか?

開いてる ")" の数が小さい順に文字列を並べるのであった
すなわち, 最下点の数字が大きい順に並べる

では, 最下点の数字が同じ場合はどうするか
一番右端の数字が大きいほど, 次の文字列以降負の数が出にくい
スタート地点が高くなるから

さて, 一番右端の数字より最下点の数字を優先させていいか

下のテストケース 1 を見る
一番右端の数字より最下点の数字を優先して失敗する例
f:id:tac_12:20200514161007p:plain:w500

どうすべきか具体例で考えよう
2 つを比較する

最下点が -2 で右端が 5 の文字列 1 と, 最下点が -1 で右端が -1 の文字列 2 はどっちを先にすべきか

-2 するのが許されていて, -3 するのが許されていない状況にしよう
文字列 1 を先にすると, 高さが +5 になり, もちろん文字列 2 を置ける

文字列 2 を先にすると, 高さが -1 されて, 文字列 2 は置けない
高さが計 -1 - 2 = -3 になるところが出る

-2 すら許されていないとする
文字列 1 は先に置けない
文字列 2 を先においても, 文字列 1 は置けない

一般的に考える
最下点が 0 以上で右端も 0 以上の場合
問答無用で先に並べていい

最下点が負で右端が 0 以上の場合
この文字列を置くことで最下点が負になってしまうとする
残りの 2 つの場合の文字列を先においても, スタート地点の高さは減ってしまうので結局無理
よって, この場合の文字列の中で, 並びを考える

スタート地点 - 最下点が負にならないのであれば, どの順番でもいい
なぜなら, 途中で負にならないのであれば, 結局高さが右端の値だけ大きくなるので, 足せるなら足す
+1 + 2 も +2 + 1 も変わらない

実は, 上 2 つの場合をまとめると, 右端の値が 0 以上であるなら, 最下点の数字が大きい順である
先に最下点が小さいのを置くくらいなら, 最下点が大きいのを置くことができて, スタート地点の数字を大きくできる

今まで左から文字列をつなげてきたが, 残り 2 つの場合は, 右から文字列をつなげれば, 上 2 つの場合と同じようにできる

左からつなげるなら, 最下点が小さい順

ソースコード
 https://atcoder.jp/contests/abc167/submissions/13186315

テストケース
5

4
(((
)))((
))(
)

2
)(
)(

3
)
(
)))(((

4
))(
)(
)
((

5
)))((
)((
(
)(
)

Yes
No
No
Yes
No

2020-05-11

Colorful Blocks - abc 167 e

#数え上げ

まず, 超素朴な dp を書いてみる O(N^3)
https://atcoder.jp/contests/abc167/submissions/13093316

遷移をまとめられそう O(N^2)
https://atcoder.jp/contests/abc167/submissions/13094970

dp[i][j] : i 番目のブロックを見ていて, これまでの隣り合う同じ色のブロックの数の和が j
f:id:tac_12:20200511152418p:plain:w500

もう 1 段くらい書いたら見えてくる

場合の数の経路の問題に似ている

ソースコード
 https://atcoder.jp/contests/abc167/submissions/13096583

別解

参考 : 公式 youtube editorial

隣り合うブロックで同じ色の数は決め打ち (探索) する
x とする

f:id:tac_12:20200511153335p:plain:w300
隣り合うブロックが同じ色なら連続部分を囲ってる
3 つ以上連続する場合書いてない...

K = 0 なら,
M * (M - 1) * (M - 1) * ...
= M * (M - 1)^(N - 1)

最初以外はその手前の色以外

今回, 囲った部分単位で見る

囲みの個数は N - x
最初囲みの個数は N で, 隣と同じ色になるごとに 1 減る

よって, M * (M - 1)^(N - x - 1)

あとは, 隣り合うブロックで同じ色の数は決め打ちしたが, どこにするか決めてない

ブロック間 N - 1 箇所から x 箇所選ぶ

https://atcoder.jp/contests/abc167/submissions/13115233

2020-05-08

Editor - #603 div2 e

#かっこ列

stack 2 本

f:id:tac_12:20200508154204p:plain:w300

ソースコード
 https://codeforces.com/contest/1263/submission/79348572

遅延セグ木 2 本 (TLE, 速くできる?)

()
1 0 0 ... となる

)(
-1 0 0 ... となる

min をとれる遅延セグ木で, 負の数があれば -1

また, 最後が 0 出ないのもだめ
これは, 最後の index だけの query で確かめられる

答えるのは深さの max なので, max の遅延セグ木を用意する
(min の遅延セグ木で, 符号逆の入れるとか)

ソースコード
 https://codeforces.com/contest/1263/submission/79147883

2020-05-08

Résumé Review - #639 div2 f

bi が x (= bi + 1) になったとする
$\Delta_i (x) = x(a_i - x^2) - (x - 1)(a_i - (x - 1)^2)$
$= a_i - 3x^2 + 3x - 1$

上に凸な曲線で, x = 1/2 で最大値をとる
x ≥ 1 で減少する

貪欲に n つから一番大きな $\Delta_i (x)$ が得られる i を探すのを k 回する

$\Delta_i (x)$ は減少するだけだから貪欲に大きいのをとっていい
一番大きいのを取らなかったら, 一番大きいのを取るのに変えて悪くなることはない

一番大きい ( $\Delta_i (x)$ が) のが i とする
二番目に大きい j の以下になるまでは bi を +1 し続ける

二分探索で, n つに共通の $\Delta_i (x)$ の下限 A を決める
ある i, j で A が異なれば, 下限が大きい方を下限が小さい方になるまでとった方がいい

ソースコード
 https://codeforces.com/contest/1345/submission/79301978