Codechef Cook 101 Editorial

Codechef Cook 101 で自分が解いた部分までの解説です (Div2 の4問目、Div1の3問目まで)。

各問題にはテストケース数 $T$ の制約があるけど省略しています。

Camp Or Not

概要

競プロキャンプに向けて問題を解く。問題を解くスケジュールは $D \leq 31$ 日決まっていて、 $d _ i$ 日目に $p _ i$ 問を解く予定である ( $1 \leq i \leq D, d _ i \leq 31, p _ i \leq 100$ )。

キャンプの選抜方法の候補は $Q \leq 100$ 個あり、各候補には締め切り $dead _ i$ と必要問題数 $req _ i$ が与えられている。 $dead _ i$ 日目を含むその日までに $req _ i$ 問以上解いていれば、キャンプに行くことができる。

スケジュール通りしたときに、各候補日についてキャンプに行けるかどうかを判定せよ。

解法

制約が小さいので愚直にやってもよいし、累積和を計算してもよい。

提出コード : Solution: 25750755 | CodeChef

Yalalovichik Numbers

概要

10進数で桁数が $D$ の数 $N$ が与えられる ( $D \leq 10 ^ 5$ , $N$ の各桁は0でない)。この数を $i$ 回左に回した数を $L _ i$ とする (例えば $N=123$ のとき、 $L _ 0 = 123, L _ 1 = 231, L _ 2 = 312$ )。

このとき $L _ 0, L _ 1, \ldots L _ {D-1}$ の順で結合した数を $M=10 ^ 9+7$ で割った余りを求めよ ( $N=123$ なら 123231312 が答え)。

解法

答えは

$(L _ 0 * 10 ^ {(D-1)D} + L _ 1 * 10 ^ {(D-2)D} + \ldots + L _ {D-1} * 10 ^ {0 \cdot D}) \bmod M$

となる。10のベキの方は簡単に計算できるため $x _ i := L _ i \bmod M$ が分かれば良い。

まず $x _ 0 = N \mod M$ はそのまま計算できる。次に $x _ {i+1}$ については、 $x _ i$ の先頭の桁を $d _ i$ とすると $x _ {i+1} = (x _ i * 10 - d _ i * 10 ^ D + d _ i) \bmod M$ という関係が成り立つので、 $d _ i$ さえ分かれば $i=0,1,2,\ldots$ と順に求めることができる。

今、 $N$ を順番に左に回しているので $d _ i$ は $N$ の $i$ 桁目である。 $N$ は文字列として与えられているので $d _ i$ はすぐに求められる。

提出コード : Solution: 25751450 | CodeChef

Yalalovichik Strings

概要

文字列 $T$ のすべての部分文字列(連続)の集合と $T$ のすべての部分列(連続とは限らない)の集合が一致するとき、文字列 $T$ は Yalalovichik string であるという。

長さ $N$ の文字列 $S$ が与えられる ( $N \leq 10 ^ 6$ )。 $S$ の空でない部分文字列のうち Yalalovichik string であるものの個数を求めよ。

解法

どのような文字列が Yalalovichik string になるかを考える (以降、省略してY文字列と呼ぶ)。

まず1種類の文字が続く場合 (aaaaaa など) は明らかにY文字列になる。そして文字列が2種類の連からなるとき (aaaabb など) もY文字列になる (どのように部分列をとっても a*b* の形になるため)。

逆に文字列が3種類以上の連からなるときはY文字列になることができない。 $S$ が $S = c _ 0 \ldots c _ 0 c _ 1 \ldots c _ 1 c _ 2 \ldots$ と3つ以上の連からできているとする。このとき部分列として $c _ 0 \ldots c _ 0 c _ 2 \ldots$ を選ぶと、これは $S$ からどのように部分文字列を選んでも一致させることができないからである。

このことから $S$ の部分文字列のうち

aaa... のように1種類の文字からなる文字列
a...ab...b のように2種類の連からなる文字列

のどちらかの形をした部分文字列の総数が答えになる。重複を考慮して数えなければならないが、1 と 2 は独立に考えることができる。

(1) はアルファベット $\alpha$ ごとに $S$ 中の $\alpha$ の最長の長さ $l _ \alpha$ をもっておけば、その総数は $\sum _ {\alpha \in {a,b,\ldots,z}} l _ {\alpha}$ になる。

(2) は2種類のアルファベット $\alpha, \beta (\alpha \neq \beta)$ とそれぞれの長さだけが重要になる。そのためすべてのアルファベットの対ごとに、 $S$ 中で取りうるすべての長さの組の集合 $P _ {\alpha, \beta}$ を計算する。例えば aaabb と aabbb の2種類の部分文字列が $S$ に現れるとき、 $P _ {a,b} = \{(3,2), (2,3)\}$ となる。

$f(P _ {\alpha, \beta})$ を $\alpha, \beta$ をこの順に少なくとも1つずつ使って作れる文字列の個数としよう。上の例だと $f (P _ {a,b}) = |\{ab, abb, abbb, aab, aabb, aabbb, aaab, aaabb\}| = 8$ になる。

基本的には各 $(x,y) \in P _ {\alpha, \beta}$ について $x*y$ の和を取ればよいが、これだと重複を数えてしまうことがある　(上の例だと ab, abb, aab, aabb の4種類)。この問題は2次元平面上に点 $(x, y)$ がいくつか与えられ、各点ごとに点と原点を隅に持つ長方形を描いたときの面積の総和を求めることと等価である。これはそれぞれの点 $(x,y)$ をx座標でソートして、x座標が小さい方から順に点を見ていくことで計算できる。

異なる $\alpha, \beta$ は独立に計算できるため、求める総数は $\sum _ {\alpha,\beta \in {a,b,\ldots,z}, \alpha \neq \beta} f(P _ {\alpha, \beta})$ である。

計算量はソートの部分が一番重くて $O(N \log N)$ である (アルファベットの個数は定数個なので)。

実装は $S$ を最初にランレングス符号化しておくと簡単になる (気がする)。

提出コード : Solution: 25753643 | CodeChef

Swag Subsets

概要

長さ $N$ の数列 $A _ 1, A _ 2, \ldots, A _ N$ と $B _ 1, B _ 2, \ldots, B _ N$ が与えられる。

集合 ${1,2,\ldots,N}$ の空でない部分集合 $S$ について、その swagness $v _ s$ を以下のように定める。

$v _ S = (\max _ {p \in S}{A _ p})(\max _ {p \in S}{B _ p})$

このとき $X = \sum _ {S \subseteq \{1,2,\ldots,N\}, S \not=\emptyset}{v _ s}$ を $10 ^ 9+7$ で割った余りを求めよ。

解法

簡単のために $A _ i, B _ i$ はすべて相異なるとする。

まず B を無視した問題 $v _ s = \max _ {p \in S}{A _ p}$ の総和を求めることを考える。数列 $A$ の順序に意味はないのでソートして $A _ 1 \lt \cdots \lt A _ N$ と仮定してもよい。

このとき $v _ S = A _ N$ となる $S$ は $2 ^ {N-1}$ 個ある ( $N$ を取ればそれ以外は取っても取らなくても良いので)。同様に $v _ S = A _ {N-1}$ となる $S$ のとり方は $2 ^ {N-2}$ 通りある ( $N$ は取らず $N-1$ は取る、それ以外はどちらでもよい)。

これは $v _ S = A _ 1$ となるまで同じように考えることができるので、答えは

$X = 2 ^ 0 A _ 1 + 2 ^ 1 A _ 2 + \cdots + 2 ^ {N-1} A _ N$

である。

もとの問題も今の考え方と同じようにする。まず $A _ i, B _ i$ のペアを $A _ i$ をキーでソートして $A _ 1 \lt \cdots \lt A _ N$ にする。 $B$ についてはソートされているとは限らない。

また、 $B$ の値だけでソートした列を $B' _ 1 \lt \cdots \lt B' _ N$ とする。

$A _ N = \max _ {p \in S}{A _ p}$ となる $S$ のとり方は、 $N$ を取りそれ以外はどちらでもよいので $2 ^ {N-1}$ 通りある。また $B _ N$ をすでに選んでいるので $B _ N \leq \max _ {p \in S}{B _ p}$ が成り立つ。それらのうち

$B _ N \lt \max _ {p \in S}{B _ p}$
$B _ N = \max _ {p \in S}{B _ p}$

で場合分けする。

また $k$ を

$B' _ 1 < \cdots < B' _ {k-1} < B' _ k = B _ N < B' _ {k+1} < \cdots < B' _ N$

となる数とする。

ある集合 $S$ について(1) が成り立つ条件は $B' _ k$ よりも右側にある数に対応する添字を取るときである。 $B' _ l$ を $B' _ k$ より右にあるものとして、 $B' _ {l} = \max _ {p \in S}{B _ p}$ となる場合を考える。これは $l$ より右にあるものは取らず、 $l$ (とすでに選んでいる $N$ )を選び、それ以外はどちらでもよい取り方になるので、 $S$ の選び方は $2 ^ {l - 2}$ 通りある。

つまり任意の $k \lt l \leq N$ について $B' _ {l} = \max _ {p \in S}{B _ p}$ となる $S$ の取り方は $2 ^ {l-2}$ 通りある。よって (1)の場合の求める数は $A _ N * (2 ^ {k-1} B' _ {k+1} + 2 ^ {k} B' _ {k+2} + \cdots + 2 ^ {N-2} B' _ {N})$ である。

(2) が起きるのは $k$ より右側はすべて取らず、左側はどちらでもよい取り方になるので、 $2 ^ {k-1}$ 通りある。よって求める数は $A _ N * B' _ k * 2 ^ {k-1}$ となる。

以上から $A _ N = \max _ {p \in S}{A _ p}$ となるときの答えは (1), (2) を合わせて

$A _ N * (2 ^ {k-1} B' _ {k+1} + 2 ^ {k} B' _ {k+2} + \cdots + 2 ^ {N-2} B' _ {N}) + A _ N * B' _ k * 2 ^ {k-1}$

である。

次に $A _ {N-1} = \max _ {p \in S}{A _ p}$ となる場合を計算したい。これは $B'$ の列から $B' _ k$ を削除してから、同じ方法で計算することができる。

以上より $X$ の計算方法は分かった。あとはこれを高速に計算できるように実装する必要がある。数列 $B' _ 1, \ldots, B' _ N$ に対して、上で必要になる操作は

与えられた区間 $[l,r)$ について $2 ^ 0 B' _ l + 2 ^ 1 B' _ {l+1} + \cdots 2 ^ {r-l-1} B' _ {r-1}$ を求める (上の計算式と少し違うが、全体に $2 ^ {何か}$ を掛けて調整できるためok)
要素の削除

の2種類。しかし(2) の要素の削除を考えると面倒なので、 $B' _ i$ が0 となる部分は無視するように (1) の計算方法を下のように変える。これで(2)の処理も簡単になる。

与えられた区間 $[l,r)$ の $B' _ l, B' _ {l+1}, \ldots B' _ {r-1}$ のうち、非0 の要素を集めたものを $B'' _ 0, B'' _ 1, \ldots B'' _ k$ として $2 ^ 0 B'' _ 0 + 2 ^ 1 B'' _ {1} + \cdots + 2 ^ {k} B'' _ {k}$ を求める
$B' _ i = 0$ にする。

(1)の計算は次のように言い換えられる。要素 $e _ i = (x _ i, c _ i):= (B' _ i, B' _ i \neq 0\ ?\ 1 : 0)$ とし、その上の演算 ${\circ}$ を $e _ i \circ e _ j := (B' _ i + 2 ^ {c _ i} B' _ j, c _ i + c _ j)$ で定める。このとき(1)の計算は $e _ l \circ e _ {l+1} \circ \cdots \circ e _ {r-1}$ の第一成分と一致する。