ACPCVC20200520 復習メモ - tinumu's reminder

https://kenkoooo.com/atcoder/#/contest/show/a4ae8851-2cd0-46d7-963e-5aceb43e351d

こんなペースでは大丈夫ではない

A - CARtesian Coodinate

とりあえず、どのような場所が距離が最小になるのかということをわかっておきたい。
まずマンハッタン距離を扱ってるので距離の $x, y$ は独立に考えられる。
そのため $x$ 座標について考えると $\displaystyle \frac{N(N-1)}{2}$ の交点を $x$ でソートしたときに $\displaystyle \left\lceil \frac{N(N-1)}{4} \right\rceil$ 個目の $x$ 座標の所が最小の距離になる所かつ最小の $x$ 座標になる。同様に $y$ 座標も同様に求める。

ここで、真ん中の点を見つければ良いということがわかった。
ではそのような点をどう見つければいいだろうか。

また、 $x$ 座標について探してみる。
ここで気づくべきなのは、 $x=X$ であるような直線より左側にある交点の数は高速に求められるということである。
どうやってやるかというと、 $x \rightarrow -\infty$ の直線との交点たちの $y$ 座標の順番と $x = X$ の直線との交点たちの $y$ 座標の順番を比較する。

$x$ を限りなく小さくすると、それぞれの直線の $y$ 座標の順番は変化しなくなり、傾きの大きさだけが関係するようになる( 傾きが大きいほど $y$ 座標は小さくなる)。

このときの直線の番号を $y$ が大きい順に $1, 2, \cdots, N$ のように振る。
このように振ったら、 $x = X$ のときに $y$ が大きい順に見た時に番号の並びが変化している。
$x = X$ のときの番号の並びの転倒数を取ると、これは $x \leq X$ であるような交点の数と一致している。
f:id:tinumukiti631:20200620030825j:plain
青い線は $x \rightarrow -\infty$ の代わりの直線である(傾きが大きい順に直線の $y$ 座標が並んでいるのでここでは同義になる)。

実際には予め直線を傾きの小さい順にソートしておく(このインデックスが $1, 2, \cdots, N$ で $x \rightarrow -\infty$ についての並びと同義になる)。
$x=X$ のときの交点を $y$ が大きい順にソートしてインデックスの並びを見る。この並びの転倒数を見ると交点の数が分かる。
計算量はソートと転倒数を求めるのがどっちも $\mathrm{O}(N \log N)$ でできるので、この調べは $\mathrm{O}(N \log N)$ で出来ることが分かる。

この調べは $x$ が大きくなれば数も増えるという単調性があるので二分探索することで、交点の数がちょうど半分になるところが分かり、そのような $x$ が最小コストの点であることが分かる。
これを $y$ 座標にも同様に行えば終わり。
計算量は二分探索の回数を $M$ とすると、 $\mathrm{O}(MN \log N)$ になるのかな ( $M$ は $100$ もあれば十分)

長い上にわかりにくい解説を書いてしまったな

B - 101 to 010

操作で連鎖が起こるパターンが $2$ パターンしかなくて、 1111...101 か 101111....1 になる。
このパターンの数は $\mathrm{O}(N)$ 個くらいしか無い。
そのため、パターンとそのパターンを全て消すための操作回数の情報をエッジにしてDPを書けば簡単に求まる。
$dp_i$ … $i$ 文字目まで見たときの操作回数の最大値
パターンの始点と終点、操作回数の情報しか要らなかったりする。

なんか雰囲気意外と簡単な気がする。本番で解けなかったから簡単じゃないんですが…

C - Yet Another Palindrome Partitioning

これdiff が B > C なのがかなり直感に反する

「 $s_i$ の文字を並び替えて回文が出来る」というのは「文字数が奇数である文字の種類の数が $1$ 以下」というように置き換えられる。
$dp_{i,bit}$ : $i$ 文字目まで見ていて、 $j \leq i$ である文字列 $\lbrack 1, j \rbrack$ のそれぞれの種類の文字の文字数が奇数であるかどうかの $bit$ があるときの分割数の最小値
みたいな感じのDPの配列を用意しておく。これ自体は大きすぎて無理だが、値は保存されるので配列を使いまわせて $2^{26}$ 個だけ持っておくだけで良い。
このDPがあると、全体の文字列 $s$ の文字数の偶奇を $xd$ に置いておくと、 $dp \lbrack xd \rbrack$ のところに答えが出てくることになる。
分割毎に $1$ 種類だけ奇数を許しているので、分割させれば、DPの遷移的には $2$ のべき乗を xor したところまで許して伝播できる。

ごめんなさい、これについてはコード載せておきます。全然書けない…
どっかでリトライできたらします(こう言っとけばってのがあるけど多分やらないだろうな)

void Main() {
	string S; cin >> S;
	int xd = 0;
	vint dp(1<<26, INF);
	dp[0] = 0;
	for (auto &s : S) {
		xd ^= (1<<(s-'a'));
		for (int i = 0; i < 26; i++) {
			chmin(dp[xd], dp[xd^(1<<i)]+1);
		}
	}
	cout << max(dp[xd], 1) << endl;
}