https://www.codechef.com/MAY17
Chef and his daily routine
CESから成る文字列が与えられる。
それは1日のある時刻での作業を時系列順で伝えている。
その人は一日を料理する(C),食べる(E)、寝る(S)の順でこなす。
正しく時系列順で伝えられているかどうか判定せよ。
Courses in an university
N個の授業があり、i番目の授業を履修する為には[0,i)の中から少なくともA[i]個、履修してある必要がある。
全部の授業を履修可能にするために履修しなくても良い授業の最大個数は？
Median of adjacent maximum numbers
2N個の配列Aがある。
ここから、B[i] = max(A[2i-1], A[2i])として配列Bを作る。
配列Aを上手くシャッフルして配列Bの中央値を最大化したい。
中央値の最大値と、その時の配列Aを答えよ。
Chef and Sub Array
0と1からなる長さNの配列Aがある。
これについてP個のクエリに答える。
- '?' : 配列中のある連続するK個に含まれる1の数の最大値を答える
- '!' : 配列を左にシフトする
Chef and Subsequences
N個の配列Aがある。
この配列の部分列のうち、その積がK以下であるものは何通りか。
Blocked websites
N個の文字列がある。
各文字列は
- ＋:通す
- －:通さない
が決まっている。
フィルタリングは文字列を使うが、prefixが同じ文字列を通さないようにできる。
フィルタリングの文字列の長さの総和を最小化して、フィルタリングの文字列を決めよ。
Gotham PD
（問題文がかなり複雑なので本文を読んだほうがいいです）
N頂点の木がある（頂点は1～Nというわけではないので注意）。
各頂点には鍵があり、頂点Rを根とした木を構築している。
Q個のクエリを処理する。
しかし、このクエリは暗号化されており、初期鍵は0で全てxorすることで復元できる。
- 0 u v k : 鍵kを持つ頂点uを作り、親は頂点vとする
- 1 v k : 頂点vから頂点Rへのパスの全ての鍵について key[i] xor kを計算し、その最小と最大を返す。最小と最大のxorが次のクエリの鍵となる
Long Sandwich
長さNのサンドイッチがある。
これをK以下のまとまりになるよう切る。
まとまりの個数を最小としたときの、切り方は何通りあるか(mod M)。
以下、解説
Chef and his daily routine
https://www.codechef.com/viewsolution/13436771
隣接する同じ文字を1文字に圧縮する。
そうすると全体がCES,CE,CS,ES,C,E,Sのいずれかになれば"yes"
Courses in an university
https://www.codechef.com/viewsolution/13437046
例えば10個の授業があり、ここから5個履修するとして、後半の授業に影響をより及ぼしたい場合は、最初から5個履修すれば良い。
後は何個履修すべきかを全探索するのだが、「i個履修して、残りの授業がそれによって履修可能になるか」を高速に判定したい。
これは、ちょっと考えると、「max{j=i...N-1}A[j] <= i」の判定と等価であると分かる。
後は区間maxが取れればいいので、セグメント木を使うとAC
Median of adjacent maximum numbers
https://www.codechef.com/viewsolution/13437264
考察の正当性が保証できない解法です。
配列Bの中央値を最大化するためには、配列Bに含まれる数はなるべく大きい方が良い。
そこで、配列Aを昇順ソートしておき、B[i] = max(A[i], A[N + i])で配列Bを作るように配列Aを作り直す。
このようにすると、配列Bは配列Aの大きい方からN個取り出した配列となり、これ以上配列Bに含まれる数を大きくできないことは明らかである。
あとは、これの中央値を取ってきて、作り直した配列Aを答えると答え。
Chef and Sub Array
https://www.codechef.com/viewsolution/13440363
オーバーフロー対策として、N<=Kの時は全ての答えが1の数になるので、場合分けして処理しておく。
まず左にシフトを高速化することを考える。
これはよくある手法なのだが、
- シフトする操作をオフセットの操作であると考える
- 円状にデータが操作されるものは同じものを2つつなげた配列で処理する
と言うものがある。以下に例を示す。
例) 1234 データ上では2つつなげて持っておき、offsetを0としておく。 12341234 ---- 左にシフトすると言うのはoffsetをデクリメントする操作と等しいので、 12341234 ---- のように解釈できる（ 0 - 1 = 3 (mod 4) ）
これでシフトは高速化されたので、後はカウントについて考える。
O(NK)解法
愚直な全探索をする。
左を全探索して、その間の1をループで回してカウントする。
O(N)解法
Subtask #1が通る解法だが、1をループで回してカウントするのは無駄なので、累積和などを使って、O(1)で取ってこれるようにする。
他にも尺取り法を使うことで、O(NK)をO(N)に落とすこともできる（こちらも自然な考え方）
O(logN)解法
前計算が必要になるが、左について全探索し、答えを求めておく(O(N),pre関数)
そして、取ってくる時は全探索する予定の左の結果の最大が取ってこれれば良いので、
予め計算しておいたやつを区間maxのセグメント木に入れておいて、取ってくる。
これで大分高速化できるので、AC
Chef and Subsequences
https://www.codechef.com/viewsolution/13454555
Subtask #1
全列挙して確かめれば良い
Subtask #2
N<=30というのは半分全列挙っぽい感じがある。
前半と後半で分けて、作りうる積を求めておく。
前半の作りうる積について全探索して、掛けてK以下になるように後半を何通り取れるかを高速に処理していく。
これは後半をソートしておき、upper_bound辺りでダメな所の境界線を探して、掛けてK以下となる個数を割り出していけばいい。
Blocked websites
https://www.codechef.com/viewsolution/13462390
前日解いたyukicoderで出てきた感じの知識が使えそうな場面だったのでさっくりいった。
prefixが同じだどうだって話なので、LCPを使って解く。
Subtask #2
まず文字列を昇順ソートし、隣り合った文字列のLCPをとっておく。
こうすることで、任意の2つの文字列のLCPがその間のLCPの最小値と等しくなる。
後は、全ての-の文字列について、上下に+が始めてくる文字列を探し、その間のLCPの最小値+1をフィルタの文字列の長さとして採用する。
この時に、その文字列の長さを超えてしまったら、フィルタリングが作れないということなので、-1を出力する。
本当は初めて+が出て来る所を二分探索しないと間に合わないかなと思うのだが、愚直に探していっても間に合う。
Gotham PD
https://www.codechef.com/viewsolution/13455494
Subtask #1
愚直にやる。
題意を理解しているかを確かめるためのサブタスク。
Long Sandwich
https://www.codechef.com/viewsolution/13471478
Subtask #1/2
uwiさんのすごい記事がある。
ここの「値(素因数分解) (n<10^7, r,m:任意)」をはっつけただけ
