Codechef November Challenge 2017 参加日記

143位/8136人で目標の2桁順位は達成できず。回答人数の多いCSUBQで部分点だったのが痛かった。以下、易問は省略する。

長さNの文字列Sについて、Nが整数Pの倍数であり、かつSをPごとに分割したときすべてのP[i]が一致しているものを、周期がPである、と定義する。NとPが与えられたとき、文字aとbのみを使って、周期がPかつ全体で回文になる、長さNの文字列を作れ。ただし、文字列にはaとbの両方を使う必要がある。
1 <= P, N <= 10^5

UnionFindを使う。最終的な文字列をSとすると、全体で回文なので、
S[0] = S[len-1]
S[1] = S[len-2]...
とグループ化できる。
また、各分割文字列A,B...について
A[0] = B[0] ...
A[1] = B[1] ...
とグループ化できる。
全ての文字が同一グループになってしまったらImpossible、そうでないならグループごと適当にabを当てはめればよい。
https://www.codechef.com/viewsolution/16049370

Chef Hates Palindromes

アルファベットの最初のA文字のみを使い、長さNの文字列Sを作成せよ。このとき、最長の回文部分文字列をなるべく短くせよ。
1 <= N <= 10^5

まず明らかな観察として、A=1のときはaのみの文字列を返すしかなく、A>=3ならabcabcabc...を返せばよいことがわかる。よって、A=2の場合のみ考えればよい。
なるべく部分的な回文を短くしたいので、Nがある程度大きいなら
a|ab|b|ab|a|ab|...
のように構築すれば、最長の回文文字は長さ4になって最小となる。
("ab"で囲んでしまえば、その内部にある文字を中心とした回文は、それ以上大きくは作れないので)
Nが小さい(<=8)場合の回答はすべて列挙してしまうのが早い。
https://www.codechef.com/viewsolution/16058582

Chef and Intersection Line

チャレンジ問題。整数の配列A[M][N][N]が与えられる。このとき、二次平面上の点P[1],P[2],P[3],...P[M]を回答せよ。ただし
・P[i] - P[i - 1]の線は、それ以前のいずれの線とも交差してはならない（隣の線と一点でのみ一致する）
・k番目の点に(i, j)ついて、得点A[i][j][k]が加算される
・合計点をなるべく多くするのが目標
N = 50
1 <= A[k][i][j] <= 100
M = 50のテストセットと、M = 500のテストセットがある
制限時間は2.5秒
(テストケースの生成ロジックは省略）

以下の方針で90点程度の結果だった。
・有効解を貪欲的に作成する（点数はあまり気にしない）
・ランダムに点を選んで山登り
・次の点は、M=50のセットでは盤面のほぼすべてから、M=500は狭いので上下3ポイント以内くらいから選ぶ
盤面が100x100しかないので、M=500はかなり狭くあまり改善の余地がなかったように思う。
https://www.codechef.com/viewsolution/16235791

Chef and Subarray Queries

長さNの整数列Aと、整数L、Rが与えられる。Aの初期値はすべてゼロである。次のクエリに答えよ。
・タイプ１：A[x]をyに更新する
・タイプ２：Aの範囲[l, r]にあるサブ配列すべてにおいて、最大値がL以上R以下となるものの数を出力
1 <= N <= Q <= 5 * 10^5
1 <= L <= R <= 10^9
1 <= x <= N
1 <= y <= 10^9

本番では平方分割と二分探索を駆使して52ptの部分点だった。想定解はセグメント木を使う。以下の解説がわかりやすかった。
hamayanhamayan.hatenablog.jp
セグメント木のノードごとに
・Count：対応する要素数
・Answer：ノード単体での解答
・MinLeft/MinRight：ノード左(右)端に続く、連続するL未満の数の数
・MaxLeft/MaxRight：ノード左(右)端に続く、連続するR以下の数の数
の情報を持つ。すると、Answerは以下のように計算できる。

cur.Answer = left.Answer + right.Answer;
cur.Answer += left.Max_Right * right.Max_Left;
cur.Answer -= left.Min_Right * right.Min_Left;

MaxLeft/MaxRightを「連続するL以上R以下の数」にすると計算が面倒になってしまうようだ。
https://www.codechef.com/viewsolution/16282630

Product on the segment by modulo

長さNの整数列と整数Pが与えられる。以下のQ個のクエリに答えよ。
・区間[L, R]の要素すべての積 mod Pを出力
1 <= N <= 10^6
1 <= Q <= 2 * 10^7

本番では累積和（imos法？）的に解いたが、当然Pが素数でないと通らないので部分点だった。
想定解ではSparse tableのようにデータを持つ。
・A[k, i]: i以下で2^kの倍数となる最大のインデックスからiまでの積
・B[k, i]: iから、iより大きくて2^kの倍数となる最小のインデックスまでの積
こうすると、B[k, L]とA[k, R]で重複がないkを選ぶことができれば、各クエリに対してO(1)で回答できる。k=1から増やしていけば簡単に見つけることができる。（証明は公式Editorialにある：https://discuss.codechef.com/questions/116821/segprod-editorial)
Sparse tableはこちらが分かりやすかった。
http://tookunn.hatenablog.com/entry/2016/07/13/211148

Lovers Gift

N個の都市が、双方向に繋がった木の形のグラフで表される。都市はそれぞれ1からNでDistinctにスコア付けされる。次のクエリに答えよ。
クエリ１: 都市Cに銀行がオープンする
クエリ２: 都市Cから1つ以上の銀行を経由し、2番目にスコアの大きい都市を訪れる。ただし同じ道は通れない。このスコアを出力せよ
1 <= N, M(クエリ数) <= 100000

想定解は素集合を使って求める。この方法は本番でも思いついていたが、計算量が大きく不可能と判断してしまっていた。
・銀行がすべてオープンした状態にして、後ろからクエリを発行する
・銀行を経由しないグループを１つの集合とする
・集合ごと、「集合外で1番目と2番目に大きなスコア(m1とm2)」を管理する
・銀行がクローズするたび、集合をマージ
こうすれば、クエリ2ごとに
・Cに銀行があればN-2を解答
・それ以外ならm2を解答
すればよい。
マージ後のm1、m2は、単純にm1からデクリメントして探していく。これだと間に合わなそうだが、マージするたびにm1の初期値がどんどん小さくなるので問題ない。