Codechef October Challenge 2017 参加日記
78位/10487人。これくらいの順位で安定するのが今年の抱負（改）。
以下、易問は省略する。
Chef and a great voluntary Program
リンゴa個、バナナb個をn人にいずれか一個ずつ配りたい。このとき、リンゴを配られた人は、直前x人が続けてリンゴだったら不満に思う。同じように、バナナを配られた人は、直前y人がバナナだったら不満に思う。不満を解消するには、リンゴまたはバナナを配る直前にキウイを渡せばよい。キウイの数を最小にせよ。
1 <= n <= 10^5
1 <= x, y <= n
a<=bとすると、配布の方法は2パターンしかない。
１、a, bひとつ以上, a, bひとつ以上...
２、bひとつ以上, a, bひとつ以上, a...
よって、aを一個ずつに分けて、その間にbを入れていけばよい。
https://www.codechef.com/viewsolution/15764132
無向グラフを考える。このグラフにはN個のサイクルがあり、それぞれA[i]個のノードで構成されている。各サイクルにおいて、i番目のノードは(i + 1) % A[i]のノードとつながっている。さらに、グラフ全体をみると、N個のサイクルによって大きな１つのサイクルを構成している。つまり、i番目のサイクルは、i % N + 1番目のサイクルと、いずれかのノードで繋がっている。
すべてのエッジに重みが付いているとき、サイクルc1のノードv1と、サイクルc2のノードv2の最小コストを求めよ
なお、クエリ(c1, v1, c2, v2の組み合わせ）はQ個発行される。
1 <= N, Q <= 10^5
1 <= A[i] <= 10^5
1 <= A[1] + A[2] + ... + A[N] <= 10^5
単純なノードのみで構成されるサイクルn[0], n[1], ... n[k]を考えたとき、次のようにエッジコストの累積和を求めておけば、任意の2点間の最小コストはO(1)時間で求めることができる。
n[0], n[0]+n[1], ... Sum(n[0:k]), Sum(n[0:k])+n[0], ... 2xSum(n[0:k])
これを小さいサイクルと外側の大きなサイクルに適用すればO(1)で回答できる。
https://www.codechef.com/viewsolution/15784456
N個の数列があり、それぞれの数列は好きなようにシフトすることができる。このとき、i番目の数列の末尾の値をx、次の数列の最初の値をyとしたとき、|x - y|*iの合計値を最大化せよ。
数列の長さの合計は10^6を超えない
1 <= 値 <= 10^6
まず自明な観察として、実際に数列をシフトする必要はない。使うのは数列の先頭と末尾だけなので、ある位置jを末尾に使うとすると、先頭になるのはi+1である。
あとは次のDPを立てれば求めることができる。
dp[i, j]: 0..iまでで、数列iについて位置jを選んだときの最大値
https://www.codechef.com/viewsolution/15799713
(Challenge) Connecting computers
チャレンジ問題。ノード数1000の連結グラフを構築したときの最小コストを求めよ。
・各ノード間のコストはすべてランダムに与えられる
・各ノードについて、Degreeに応じたコストがかかる（Degreeの大小とコストの大小は連動しない）
制限時間はT=5で5秒。
Editorial想定解は連結を保持したままの山登り法。これが正解かなとは思ったが、連結を保持したまま高速に回すやり方が分からず保留（したままコンテスト終了）。次点解がクラスカル法＋αで、自分の実装もこれで平凡な得点に終わってしまった。
二次平面上にN本の部分直線がある。部分直線iは(i,0)から(i,A[i])へ引いてある。このとき、次のQ個のクエリに答えよ。
・+ i X => 直線iのA[i]をXだけ増やす
・? i L R => R-L+1本のX軸に平行なビームを発射する。j番目のビームは(i-0.5, L+j-1.5)から発射される。ビームは直線にぶつかると消える。このとき、ビームがあたる直線の本数をプリントせよ
1 <= N <= 10^6
1 <= Q <= 10^5
x <= X <= 10000
1 <= A[i] <= 10^9
1 <= L <= R <= 10^9
平方分割を使う。このとき、１つのセグメント内ではA[i]が増加している分のみ保持すればよい（それ以外のものはビームが当たりようがない）。するとセグメント内は単調増加になるので、現在のビーム範囲で当たる最も短い（左の）直線と、最も長い（右の）直線が二分探索で求められる。
計算量はO(QSqrt(N)LogN)でぎりぎり間に合う。
https://www.codechef.com/viewsolution/15803230
