CodeChef August Challenge 2016

700点でした。

Chef and Chocolate

必ず nm-1 ターンで終わるので nm-1 の偶奇を見ればいい。nm-1ターンで終わることは帰納法で示せるが、直接的に示す方法は思いつかなかった。

Chef and Round Run

サイクルに含まれている頂点の数を数えればいい。サイクルの検出には、入次数 0 の頂点を削除するという操作を連鎖的に行えばサイクルだけが残ることを使った。

Chef and Circle Run

作れる経路は Start→x→Start→Goal→y→Goal の形以外存在しないということを考えると、連続部分列の和の最大化の問題に帰着できる。これは動的計画法で O(n) で解ける。

Chef and His Garden

高さの上下関係が変わるタイミングだけ調べればよい。

Funny gnomes

隣接行列を A としたとき Ak を求めれば x から k 回の移動で到達できる頂点が分かる。しかしこれをクエリ毎に計算するのは無理がある。

本当に欲しいのは v Ak (vはv[k]=1でそれ以外 0 のベクトル)なので、これを計算しよう。v Ak=v A0 A1 A2 A4 A8 ... とできるので、O(n2 log k) で計算できる。

これで通るのかもしれないが、ビット並列で行列積を高速化させると安心。

Maximum Grid

ゴリ押し。グリッドの最大幅を L としたときの値を f(L) としたとき、 f(L) は単調増加なので二分探索できる。

f(L) を求めるにはグリッドの右端を n 通り(x[0]..x[n-1])試せばいい。line sweep でいい感じのセグメント木を更新していくと計算できる。(x[i],y[i]) が追加されたら y[i]~y[i]+L の範囲に 1 を加算させればいい。

最大値クエリで点が存在しない座標を無視するように仕組んだけど、よく考えると必要ないかも…。無視を考慮するためには、区間内にいくつの点が存在するかという情報を付加させた。

A Good Problem

ビット並列ゴリ押し。小さい値から順に見ていって、隣が自分より小さかったら merge していく。いま見ている値が v で、マージするグループが L, R のとき、x∈L, y∈R かつ部分集合のペアになっている数 cnt が得られれば ans += v*cnt をしていくことで答えが得られる。

問題なのは cnt の求め方である。union-find のノードに mp[v]:=グループ内にあるvの個数 を持たせておく。mp の更新だけならマージテクでできる。cnt はマージテクをしながら計算できるのではないだろうか。

cnt を高速に計算するには、区間 [l,r] にある v の subset or superset の個数が O(1) 程度で分かればいい。

a[i] が v の subset or superset かどうかを表すフラグを dp[v][i] に格納しよう。これは簡単な DP で構成することができるが、普通にやると 105*214 のメモリが必要になり無理がある。値はブール値なのでビット並列で /64 を効かせれば間に合う。

さらに得られた dp[v] の累積和も計算する。これも /64 が効くので計算できる。

これらを使えば O(1) で区間内の v の subset or superset の個数を計算できる。

いつもより全体的に難しい気がする。最近コンテスト以外で問題を解いてないから弱ってるかもしれない。