2024-09-02

Codeforces Round 970 (Div. 3)に参加した

競プロアルゴCodeforces

Codeforces Div. 3の参加記．

9月1日に開催されたCodeforces Round 970 (Div. 3)に参加した．ABCDEFGの7完で489位．

A - Sakurako’s Exam

問題概要

$a$ 個の $1$ と $b$ 個の $2$ からなる長さ $a+b$ の数列がある．数列の要素それぞれに対して+または-のいずれかの符号を付けることができるとき（形式的には，それぞれに対して $-1$ 倍するかしないかを選べるとき），数列の要素の総和を $0$ にすることができるか？

制約

$0\leq a,b<10$

考えたこと

「高速だが考察が必要な解法よりも、計算量は劣るが考察のいらない解法を」の精神で愚直に解いた．

+と-の内訳を全探索する．要素の中に $+1$ が $x$ 個 $(0\leq x\leq a)$ ， $+2$ が $y$ 個 $(0\leq y\leq b)$ 含まれるとき，数列の総和は

1\cdot x+(-1)\cdot (a-x)+2\cdot y+(-2)\cdot (b-y)=2x+4y-a-2b

となるので， $(x, y)$ のそれぞれに対して上の値が $0$ になるか判定すればよい．計算量は $O(ab)$ である．

提出：https://codeforces.com/contest/2008/submission/279078644

B - Square or Not

問題概要

問題文

0または1からなる長さ $n$ の文字列 $s$ が与えられる．このとき，以下の条件をすべて満たすような正の整数 $r, c$ が存在するか判定せよ．

$rc=n$
$r=c$
マス $(i, j)\;(1\leq i\leq r, 1\leq j\leq c)$ に $s_{(i - 1)c+j}$ が書き込まれているような $r\times c$ のグリッドは美しい（beautiful）グリッドである．

ここで，マスに0または1が書き込まれているグリッドが美しいとは，グリッドの周上のマスにすべて1が，そうでないマスにすべて0が書き込まれていることをいう．

制約

$2\leq n\leq 2\times 10^5$
$s_i$ は0または1

考えたこと

明らかに，そのような $r,c$ が存在するためには $n$ は平方数でなければならない．このとき $r,c$ は一意に定まるので， $r=c=\sqrt{n}$ として条件を満たすかどうかを愚直にチェックすればよい．計算量は $O(n)$ になる．

提出：https://codeforces.com/contest/2008/submission/279087603

C - Longest Good Array

問題概要

問題文

整数 $l, r\;(l\leq r)$ が与えられる．以下の条件をすべて満たすような長さ $n$ の数列 $(a_i)$ が存在するような $n$ の最大値を求めよ．

数列 $(a_i)$ は狭義単調増加．すなわち，任意の $1\leq i < n$ に対し $a_i < a_{i+1}$ が成り立つ．
数列 $(a_i)$ の階差は狭義単調増加．すなわち，任意の $1 < i < n$ に対し $a_i - a_{i-1} < a_{i+1} - a_i$ が成り立つ．
任意の $1\leq i\leq n$ に対して $l\leq a_i\leq r$ ．

制約

$1\leq l\leq r\leq 10^9$

考えたこと

要素がすべて $r$ 以下という条件を守りつつ数列の長さをできるだけ大きくしたいので，できるだけ要素の増加を小さく抑えたい．よって

\begin{align*} a_0&=l\\ a_1&=l+1\\ a_2&=l+1+2\\ &\vdots\\ a_n&=l+1+2+\cdots +n \end{align*}

とするのが最適で，あとは

l+1+2+\cdots +n\leq r

すなわち

\frac{1}{2}n(n+1)\leq r-l

であるような $n$ の最大値を求めればよい．提出コードでは二分探索をした．

提出：https://codeforces.com/contest/2008/submission/279213495

D - Sakurako’s Hobby

問題概要

問題文

$1,\cdots, n$ の順列 $(p_1,\cdots, p_n)$ が与えられる．整数 $i$ が整数 $j\; (1\leq i,j\leq n)$ に到達可能であるとは， $x=i$ から始めて，整数 $x$ を $p_x$ に置き換えるという操作を $0$ 回以上行うことによって $x=j$ にすることができることをいう．

0または1からなる長さ $n$ の文字列 $s$ が与えられる． $s_i$ が0のとき整数 $p_i$ は黒色に，1のとき整数 $p_i$ は白色に塗られていることを示す（ $(p_i)$ は順列なので，この定義により $1,\cdots, n$ のすべてに対して色がwell-definedに定まる）．

$i=1,\cdots, n$ のそれぞれに対して，整数 $i$ が到達可能な整数のうち黒色に塗られているものの個数を求めよ．

制約

$1\leq n\leq 2\times 10^5$
$1\leq p_i\leq n$
$(p_1,\cdots, p_n)$ は $1,\cdots,n$ の順列
$|s|=n$
$s_i$ は0または1

考えたこと

各 $i=1,\cdots, n$ に対して $i$ から $p_i$ に有向辺をはったグラフを考えると， $(p_i)$ が順列であることから各連結成分はサイクルになる．よって頂点 $i$ からは， $i$ が属する連結成分のすべての頂点に到達可能である．したがって，UnionFindなどを用いて連結成分に含まれる黒色の頂点の個数を数えればよい．

提出：https://codeforces.com/contest/2008/submission/279116356

E - Alternating String

問題概要

問題文

英小文字のみからなる文字列 $t$ が交代的（alternating）であるとは，以下の条件がすべて成り立つことをいう．

$|t|$ は偶数である．
$t$ の偶数番目の文字がすべて等しい．
$t$ の奇数番目の文字がすべて等しい．

英小文字のみからなる長さ $n$ の文字列 $s$ が与えられる．以下の $2$ 種類の操作を行なって $s$ を交代的にするために必要な操作回数の最小値を求めよ．

操作A： $s$ の中から $1$ 文字を選んで削除する．この操作は高々 $1$ 回だけ行うことができる．
操作B： $s$ の中から $1$ 文字を選んで，ある英小文字に置き換える．この操作は何回でも行うことができる．

制約

$1\leq n\leq 2\times 10^5$
$|s|=n$
$s_i$ は英小文字

考えたこと

簡単のため0-indexedで考える．

区間 $[l, r)$ の偶数番目に文字 $c$ が ${\rm even}_c(l,r)$ 回，区間 $[l, r)$ の奇数番目に文字 $c$ が ${\rm odd}_c(l,r)$ 回登場するとする．

$n$ が偶数のとき，偶数番目と奇数番目でそれぞれ登場回数が最多であるような文字に揃えるのが最適である．よって

n-\max_c {\rm even}_c(0, n)-\max_c {\rm odd}_c(0, n)

が答え．

$n$ が奇数のときは，文字列の長さを偶数にするために，最初に操作Aを適用する必要がある．削除する文字の位置 $i$ を固定すると，操作後の文字列において偶数番目に位置するのは，もともとの文字列の区間 $[0, i)$ の偶数番目にいた文字と区間 $[i+1, n)$ の奇数番目にいた文字である．同様に，操作後の奇数番目はもとの $[0, i)$ の奇数番目と区間 $[i+1, n)$ の偶数番目に対応する．よって， $i=0,1,\cdots, n$ に対して

n-\max_c ({\rm even}_c(0, i)+{\rm odd}_c(i+1, n))-\max_c ({\rm odd}_c(0, i)+{\rm even}_c(i+1, n))

を求め，その最小値を答えればよい．

${\rm even}_c(l,r)$ と ${\rm odd}_c(l,r)$ の値は $O(n)$ かけて累積和を前計算することにより $O(1)$ で取得できるので，計算量は $O(n)$ になる．

提出：https://codeforces.com/contest/2008/submission/279137008

F - Sakurako’s Box

問題概要

問題文

長さ $n$ の数列 $(a_i)$ が与えられる．数列の要素の中から異なる2個の要素を無作為に選ぶとき，選んだ要素の積の期待値を $10^9+7$ で割った余りを求めよ．

制約

$2\leq n\leq 2\times 10^5$
$0\leq a_i\leq 10^9$

考えたこと

直球で典型が来たなあ，という感じの問題．

要するに

\frac{2}{n(n-1)}\sum_{i < j}a_ia_j

を求めよ，ということだ．やることは決まっていて，二重シグマの部分を

\sum_{i < j}a_ia_j=\sum_i a_i\sum_{j(>i)}a_j

と変形して内側のシグマの値を累積和から求めればよい．

Codeforcesでは（当然）ac-library-rsが使えないので，用意しておいた自作のmodintを貼った．

提出：https://codeforces.com/contest/2008/submission/279151308

G - Sakurako’s Task

問題概要

問題文

長さ $n$ の数列 $(a_i)$ が与えられる．この数列に対して以下の操作を何回でも行うことができる．

操作： $a_i\geq a_j$ なる $i,j\;(i\neq j)$ を選び， $a_i$ を $a_i-a_j$ または $a_i+a_j$ で置き換える．

整数 $k\;(\geq 1)$ が与えられるので，操作後の数列の要素全体からなる集合 $S$ に対して ${\rm mex}_k S$ の最大値を求めよ．

ここで，非負整数からなる集合 $S$ に対して， $x\notin S$ なる非負整数 $x\;(\geq 0)$ のうち $k$ 番目に小さいものを ${\rm mex}_k S$ と定義する．

制約

$1\leq n\leq 2\times 10^5$
$1\leq k\leq 10^9$
$1\leq a_i\leq 10^9$

考えたこと

難しかった！

${\rm mex}_k$ を最大化したいので，数列の値はできるだけ $0$ 付近に密集させ，できるだけ互いに異なっているようにしたい．いろいろサンプルを試して，何らかの方法で $1$ を作ることができたら，他の要素から $1$ を複数回引くことで数列の要素を $\{0,1,\cdots, n-1\}$ にすることができ，これが ${\rm mex}_k$ の最大値を与えることに気づいた．もちろん常に $1$ を作るのが可能というわけではないが，結果的にこの考察が解法に至るヒントになった．

$n=1$ のときはそもそも操作ができないので，以降は $n>1$ とする．

このとき $g={\rm GCD}(a_1,\cdots, a_n)$ とおくと，数列の要素はすべて $g$ の倍数である．これは操作後も変わらないから，この操作によって $g$ の倍数以外の数を得ることはできない．一方，ユークリッドの互除法の要領で数列の要素同士を引き算することにより必ず $g$ を作ることができるから，この $g$ を他の要素に対して足し引きすることにより任意の $g$ の倍数を得ることが可能である．よって， ${\rm mex}_k$ を最大化するには，数列の要素を

\{0, g, 2g,\cdots, (n-1)g\}

にするように操作を繰り返せばよい．このときの ${\rm mex}_k$ は $O(n)$ かけてシミュレーションをすることにより求まるが，提出コードでは横着して二分探索に頼っている．

提出：https://codeforces.com/contest/2008/submission/279213495