2020-01-11

Codeforces Round #613 (Div. 2): E. Delete a Segment

Codeforces

https://codeforces.com/contest/1285/problem/E

問題
区間を1つ選んで削除した後に残った重なる区間をunionする。
unionした後に残る区間の数を最大化せよ。

解法
全区間をunionした後に残る区間の数は、区間を始点ソートして昇順ループまたは降順ループを回して求めることができる。
それらをいい感じにハイブリッドすると通った。

int n;
pair<int, int> seg[200000];
int last[200000];
int cnt[200000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int t;
	cin >> t;
	rep(_, t) {
		cin >> n;
		rep(i, n) {
			int a, b;
			cin >> a >> b;
			seg[i] = make_pair(a, b);
		}
		sort(seg, seg + n);

		int inf = 1000000001;
		int ans = 0, c = 0;
		int las = -inf;
		rep(i,n) {
			if (las < seg[i].first) {
				c++;
			}
			las = max(las, seg[i].second);
			last[i] = las;
			cnt[i] = c;
		}
	
		vector<int> vec;
		for (int i = n - 1; i >= 1; i--) {
			int num = cnt[i - 1];
			num += lower_bound(all(vec), last[i - 1], greater<int>()) - vec.begin();
			ans = max(ans, num);

			while (!vec.empty() && vec.back() <= seg[i].second) {
				vec.pop_back();
			}
			vec.push_back(seg[i].first);
		}
		ans = max<int>(ans, vec.size());

		cout << ans << endl;
	}
	return 0;
}

2019-03-10

Educational DP Contest / DP まとめコンテスト

AtCoder

https://atcoder.jp/contests/dp

A Frog 1

dp[i] = 足場iに着くまでの最小コスト　とすると

足場i-1か足場i-2から飛んでくる場合の2通りなので

dp[0] = 0

dp[i] = min(dp[i-1] + $|h_i - h_i-1|$ , dp[i-2] + $|h_i-h_i-2|$ )

となり。iの昇順にdp[i]を計算する。

B Frog 2

同上

C Vacation

その日に取れる選択は前日の活動にのみ依存するので

dp[i][j] = i-1日までに直前の活動がjの時の最大幸福度

D Knapsack 1

dp[i][w] = 品物iまでの中から選び合計重さがwになるときのの最大価値

E Knapsack 2

dp[i][v] = 品物iまでの中から選びに合計価値がvになるときのの最小重さ

F LCS

dp[i][j] = s[1..i]とt[1..j]の最長共通部分列長

G Longest Path

トポロジカルソートしてDPでも解ける

メモ化再帰のほうが楽

H Grid 1

GridDP dp[x][y] = (x,y)に到達する経路の数

I Coins

確率DP dp[i][j] = i枚投げてj枚表が出る確率

J Sushi

期待値DP

寿司が同じ個数の皿を区別する必要がないのでdp[１個の皿の枚数][2個の皿の枚数][3個の皿の枚数] = 期待値とする

K Stones

２人ゲームは相手に必敗の状態を押し付ければ勝ちなので

dp[k] = 必勝か必敗

として各dp[k]は dp[k - x] が必敗となるx<aが存在するかで更新していく

L Deque

dp[残ってる先頭][残ってる最後尾] = X - Y

残ってる区間の長さからどちらのターンかわかるので最小化あるいは最大化する手を選ぶ

M Candies

dp[i][j]=i-1人目まで配って計j個配った時の場合の数　区間和差分　O(NK)

飴を0~a[i]個までの範囲で配れるため区間に足しこむ処理が必要。

長さa[i]の区間和を更新していくか、いもす法を使う。

N Slime

区間DP O(N^3)　蟻本P121

O Matching

O(N^2 * 2^N )だとTLEする。

dp[マッチンング済み女性のビット集合] = 場合の数

として昇順にループを回し

「popcount(女性のビット集合) 番目の男性」と「各相性の良い女性」で遷移するとO(N * 2^N )になる

P Independent Set

木DP

葉から塗っていくときある頂点を塗れるかは子が白か黒かにのみ依存する。

dp[頂点][白か黒か] = 場合の数

Q Flowers 2

データ構造

dp[H] = 末尾の花の高さがHのときの美しさの総和の最大値

とすると花を左から見ていくことで dp[h[i]] = max(dp[h[i]], dp[0 ~ h[i]-1] + 1)

となる。区間のmaxをの取得と更新は binary indexed tree や segment treeといったデータ構造を使うことでO(log N)になる。

R Walk

行列累乗　蟻本P183

S Digit Sum

digit DP

上の桁から数字を決めていくときの状態遷移には2通りあり、具体的には

K=12345 で123...まで決まっているとき4桁目は4以下しか選べないのに対して

122..だとすべての数字をとりうる。

dp[i][一度でも各桁を下回ったかのフラグ][数字の総和 mod D] = 場合の数として

T Permutation

先頭から順に決めていくとき状態遷移は最後に使った値の残ってる値の中での順位によってまとめることができる。

dp[i][j] = i個まで使って最後に使った値より大きい値がj個あるときの場合の数

O(N^2)で解ける

U Grouping

ビット演算で部分集合列挙するテク　O(3^N)　蟻本P144

V Subtree

全方位木DP

逆元はないので左右からの累積和を使う

全方位木DPについてはググって

W Intervals

dp[i] = i番目を最後に1にしてからj 番目を1にしたときのスコアの最大値

としてdpテーブルをsegtreeで更新していき、各jについてのdpテーブルを計算する。

X Tower

$s_i+w_i$ で非自明ソートしてDPするやつ

Y Grid 2

太郎君の経路数 = 壁を無視した全経路数 - 壁を１か所でも通る経路の数

なので壁を１か所でも通る経路をDPで求める。

壁iに来る経路の数は $\binom{X_i+Y_i}{X_i}$ となるが左上にも壁がある場合そこから来る経路もあるため重複して数えることになる。

そのためまず壁を $(X_i, Y_i)$ で辞書順ソートすることで左上の壁が小さいインデックスに来るように移動させる。

dp[i] = 初めて到達する壁が壁iであるような経路の数

としてdp[i]は $\binom{X_i+Y_i}{X_i}$ から左上にある壁j(j < i) を見ていき dp[j] * $\binom{X_i-X_j+Y_i-Y_j}{X_i-X_j}$

を引いていくことで重複なく計算できる。

最後に各dp[i]から(H,W)までの経路の総和が壁を１か所でも通る経路の数になる。

Z Frog 3

Convex Hull Trick

蟻本読んで

2019-02-10

Codeforces Global Round 1

https://codeforces.com/contest/1110

A. Parity

多倍長偶奇判定

B. Tape

テープの長さは全体の長さからテープのない区間の長さを引いたものなのでソートしてb[i]-b[i-1]から貪欲

C. Meaningless Operations

gcd(x, 0) = x なので2冪-1 でないならビットを全部立てたもの

2冪-1 なら２番目に大きい約数

D. Jongmah

同じ順子3個は面子3個に置き換えられるため3個以上考える必要はない。

dp[i][j][k] = i番目まで見て、1つ前を始点とした順子をj個、２つ前を始点とした順子をk個作った時の最大個数　

とする3*3状態の動的計画法

余ったものは面子にしていく

E. Magic Stones

$c'_i = c_i - c_{i-1}$ とすると操作は $c'$ の隣り合う要素のスワップになる

したがって $c, t$ に対して隣接差をとってソートして一致するか判定すればよい。

割と典型らしい

類題: https://dwacon5th-final-open.contest.atcoder.jp/tasks/dwacon5th_final_b

2018-09-22

AtCoder Grand Contest 027 B - Garbage Collector

https://beta.atcoder.jp/contests/agc027/tasks/agc027_b

まずゴミを捨てる回数mを決めた時の最適な捨て方を考えます。

考えやすいようにm台のロボットを並列に動かして、行きのエネルギー（位置０からそれぞれのロボットが拾う一番遠いゴミまでの移動）を無視して帰りのエネルギーだけ考える。

ある地点を通るときのゴミの個数の分布が{0,2}の場合、ゴミを別のロボットに渡して{1,1}とすることでエネルギーの総和を減らすことができる。一般にゴミの個数をk-1個からk個に増やした時の増加エネルギー $(k+1)^2-k^2=2k+1$ は狭義単調増加であるため、ゴミの個数が2個以上離れているロボットがいればゴミを受け渡すことである地点を通るために必要なエネルギーの総和を減らすことができ、均等にゴミを持たせるのが良いとわかる。ゴミを均等に持たせた状態は位置0に帰るまで維持できるので明らかに最適である。

行きのエネルギーを1とした場合、ゴミを均等に持つために行きの移動量が増えたとしても1しか増えないのでトータルで損にはならず、それぞれの地点でゴミを均等に持てばいいという結論に影響はない。

最適なゴミを捨てる回数mを求めるのは勘で三分探索をやった(未証明)

ちゃんとmを全探索することを考えるとロボットがある個数のゴミを持って移動する範囲は区間になっているので累積和を計算しておくと計算量が調和級数で $O(N \log N)$ になる

2016-01-14

ハル研究所プログラミングコンテスト2015

応募最終日では1位と同スコア同実行時間で2位でした。
・方針
ある時間帯に配達する荷物を決めたときの最小コストは明らかに巡回セールスマン問題(TSP)の応用で解ける。
それぞれの荷物をどの時間帯に割り当てるかは愚直に探索するとO(4^n)で間に合わないが(時間帯,残りの荷物集合)を状態として持つDPでbit演算で部分集合を列挙するテクを使うとO(3^n)で解ける。
最適解を求めることは出来たので以降はずっと高速化。
・探索パターンの削減
自明な事実として時間帯0と時間帯1の荷物集合を入れ替えてもコストは変わらないのでこのような重複パターンの探索を避ける。
例として最大ケースである時間帯指定のない荷物が16個ある場合を考える。
未割り当ての荷物が16個の場合、4つの時間帯はどれも荷物が割り当てられていない。荷物集合はどの時間帯に配達してもコストは変わらないので、1つ目の荷物についてはどの時間帯に割り当てるかを探索する必要がなく3^16から3^15に計算を落とせる。
2つ目の荷物についても荷物が割り当てられていない時間帯を複数探索する必要がなく2通りの分岐で済むので2*3^14になる。
さらに1つ目と2つ目の荷物を同じ時間帯に割り当てた場合を考えると3つ目の荷物の割り当ても2通りの分岐で済み、また同じ時間帯に割り当てたときはさらに再帰的に適用できる。
より実装寄りに説明すると、荷物が割り当てられている時間帯が2つ以上の場合はDPで計算して、そうでない場合はそれぞれの1つでも荷物が割り当てられている時間帯と1つも割り当てられていない時間帯のうち1つに、今注目している荷物を割り当て次の荷物について再帰的に計算した場合の最小コストとなるものを返す。
このように処理すると個数14,13,12,...についてDPの計算が行われておよそ3^14+3^13+3^12+...≒1.5*3^14程度の計算で済む。
・DPの高速化
重複パターンの探索が無駄なのはDPの計算においても同じなので、まだ荷物が割り当てられていない時間帯が複数ある場合は、後ろの時間帯に割り当てれば取り返しがつくので今注目している時間帯ではある荷物を絶対に割り当てないという選択が出来る。これによってその時間帯での計算パターン数を半分に出来る。
最小配達コストのテーブルは頻繁にアクセスされるので時間指定のない荷物はあらかじめ下位のindexにくるようソートしておくとキャッシュに乗りやすい。
・その他高速化
配達先や営業所間の距離はサイズ２のリングバッファを使いA*で探索する。
TSPテーブルなどのサイズが大きい配列はshortで宣言してキャッシュに乗りやすくする。
初期化は必要最小限に。
std::fill_nはfor文まわすより速い。
各荷物集合に対する重さはO(n*2^n)ではなくO(2^n)で計算する。
TSPの計算はO(n^2*2^n)でとても重いので別々の時間帯が含まれる荷物集合などの不要な計算は極力抑える。
TSPの計算は配るDPより集めるDPのほうが速い。

最終方針
途中までこんな感じでDP解法を0.4秒近くまで高速化していた。
o0p1qさんが0.2秒だしてやべぇなTSPの計算しかしてないとしても速すぎるなと思ったので、TSPの計算をあまりせず遅延評価しているというのは察しがついた。
方針は枝刈りでナップザックを下界を見積もって枝刈りするという方法を思い出してやった（分枝限定法というらしい）。
最適解をビューアで見てみると荷物は同じ時間帯に配達するもの同士でかたまっているという幾何的な特徴があり、良い解付近には良い解が、悪い解付近には悪い解が集まっていることが推測できるので枝刈りしやすそうと考えられる。
ということで途中からDP解法を枝刈り解法に変更した。
・下界
下界はそれぞれの時間帯ですでに割り当てた荷物集合に対する配達コストと未割り当ての荷物それぞれに対する下界の和として計算する。荷物集合にある荷物を追加するとき大きく2通りの場合がある。荷物集合が空である場合は営業所と配達先の往復分のコストがかかる。荷物集合が空でない場合は追加する荷物の配達先の直前と直後の位置は営業所または別の配達先にいるので、直前、直後の位置をそれぞれa,b,追加する荷物の位置をcとするとa->bをa->c->bに変更したときのコストの考えられる最小増加分を下界とする。
それぞれの荷物について上記のどのパターンになるかわからないが全パターンの増加コストの最小値なら実コストを超える心配はないので下界として使用することが出来る。
・荷物ソート
枝刈り解法の場合どの順番で荷物を追加するかで枝刈り効率が大きく変わる。
営業所からのマンハッタン距離で降順ソートした場合、クラスタ（同じ時間帯に配達する荷物集合）への距離は近く、または遠くなりやすいのでより枝刈りが効率的に行われると考えられる。最終的には荷物の重さも含めた式でソートした。
・時間帯の探索順序
分枝限定法では今まで見つかった解の最小コストを上界として枝刈りするのでなるべく早く最適解を求めたほうが良い。
各時間帯に荷物を追加した際の増加コストの昇順に探索すると早く最適解が見つかるのでより枝刈りすることが出来る。
・フィールド生成にあわせたA*高速化
ここまでくるともう前処理の距離計算がボトルネックになってきたのでこちらも高速化する必要が出てきた。
フィールドの形は明らかに規則的なのでフィールド生成コードを見ると(odd,odd)の座標は壁ではなく、(even,even)の座標は壁になっていることがわかる。つまり(odd,odd)から1歩移動した先の両肩は必ず壁になっておりそのまま直進するしかできないことが出来ないので再び壁の判定をするのは無駄なことがわかる。なので(odd,odd)の座標しかキューに入れず壁判定の回数を抑えることが出来る。

コード　no title

2015-05-20

Codeforces Round #303 (Div. 2 only)

Codeforces

http://codeforces.com/contest/545
A-Toy Cars
塗りつぶすだけ

B-Equidistant String
概要
長さnの0,1からなる文字列s,tが与えられる。
s,tと編集距離が等しい文字列を出力、存在しないなら"impossible"と出力せよ。
解法
ある位置のsとtの数字が異なる場合だけ変化させたときに編集距離の差が2増減する。
よってsとtの編集距離/2の分だけsの数字をtにあわせればいい。

C-Woodcutters
概要
n本の木のx座標 $x$ と高さ $h$ が与えられる。木を左に切り倒した場合は $￥[x_i-h_i,x_i￥]$ 、右に倒した場合は $￥[x_i,x_i+h_i￥]$ を占有する。
切り倒す場所に既に木がないときだけ木を切り落とせる。切り落とせる木の最大数を求めよ。
解法
xの昇順に考えたとき、左に倒せる場合は倒したほうが明らかに最適、
左に倒せず右に倒せる場合は右に倒さなかった場合の最適解が倒した場合の最適解を上回ることはないので貪欲に倒していけばいい。

D-Queue
概要
キューに人が並んでいる。それぞれの人に対応するには $t_i$ 時間かかることがわかっている。対応開始までに $t_i$ 時間以上待たされるとがっかりする。
人を並び替えて達成できるかっがりしない人の最大数を求めよ。
解法
validな解を $b$ として $b_i > b_j (i<j)$ となる $i,j$ が存在するときswapしても解として成り立つので、ソートされた解だけを考えればいいというよくあるパターン。
また任意の要素をより小さい値に置き換えても解として成り立つ。
よって昇順にソートして貪欲にキューの後ろに加えられるなら加える。

E-Paths and Trees
概要
始点の頂点番号と重みつき無向グラフが与えられる。
始点からの最短距離を変えないような重みの和が最小となる全域部分グラフの辺を求めよ。
解法
ダイクストラして最短距離を構成するのに明らかに不必要な辺を除くとDAGになる。
あとはDAG上で最小全域有向木を求めればいい。方法は各頂点について始点方向に接続する辺のうち重みが最小のものだけ残して残りは削除すればよい。一般の最小全域有向木ライブラリでも通るらしい。

2015-01-23

AtCoder Beginner Contest #017

AtCoder

コンテストページ http://abc017.contest.atcoder.jp/
解説 http://www.slideshare.net/chokudai/abc017
A - プロコン
3つの課題の配点と得点割合が与えられて合計もとめるだけ
B - choku語
choku語は空文字列またはchoku語の末尾に"ch","o","k","u"を連結した文字列と定義されるのでchoku語かどうか判定せよ。
解法は各文字列の先頭文字がすべて異なるので先頭からマッチングするだけ
C - ハイスコア
解説のとおりある宝石を選び方についての最適解を列挙すればいい。Xを覆う区間というのはli<=X∧X<=riとなる区間でありこのままだと2次元の問題となり面倒だが補集合を考えるとX<li∨ri<Xとなる区間の集合となりX<liを満たす区間とri<Xを満たす区間は重複しないことからそれぞれ独立に求めればよくて1次元の問題になる。よって宝石Xを獲得しない選び方の最適解は(X<liを満たす区間の個数+ri<Xを満たす区間の個数)として求めることができる。
D - サプリメント
解説のとおり左端の位置についてサプリメントを摂取できる最大の右端の位置は広義単調増加となるので尺取法でO(N+M)で列挙できる。組み合わせの計算については各iについてdp[i]の値を足しこむ範囲は必ずiより後ろなのでいもす法を使いながら計算すればO(N+M)で解ける。