2022-02-16

Codeforces Round #521 (Div. 3)F2. Pictures with Kittens (hard version)

問題概要

長さ $n$ の整数列 $a$ が与えられる. この中からちょうど $x$ 個の整数を選択するが, その時少なくとも連続する $k$ 個の中の一つが選ばれてなければならない. この時, 選んだ整数の合計の最大値はいくらか.

制約

$1 \le k, x \le n \le 5000$

解法

dp をしましょう. $dp[ i ] [ j ] :=$ ( $i$ 個の整数を, $j$ 番目までの整数で選び, かつ $a_j$ を選んだ時の合計の最大値 )と定義します. 通常の dp では添字が普通逆ですが, 逆だと後々困るのでこう定義しておきます.

遷移を考えます. $j$ 番目を選ぶ時, 一個前に選んだ整数は $k$ 個以内でなければなりませんから,

$dp[i+1][j+1] := \mathrm{max}(dp[i][j-k+1], dp[i][j-k+2], \cdots, dp[i][j]) + a_j$

のような遷移式ができます. 最後に選ぶ整数は $a_{n-k+1}, a_{n-k+2}, \cdots, a_n$ のいずれかですから, 答えは $\mathrm{max}_{n-k+1 \le j \le n}dp[x][j]$ となります.

これを愚直に実装すると計算量は $O(nkx)$ なので, これだと TLE します(F1 は通ります). なんとかして高速化しましょう.

dp の遷移式を見れば, $i$ についての添字は一つ前しか影響せず, $j$ についてはある範囲の最大値となっています. 典型的なテクニックですが, dp テーブルを SegmentTree として持つことにより区間最大値を高速に取得できるので, 一度の遷移が $O(\mathrm{log}k)$ で済みます. この時の全体の計算量は $O(nx\mathrm{log}k)$ です.

ただし, 添字 $i$ をあらわに持つと MLE します. in-place 化をすることで対処しましょう(一個先を作成して元の配列と swap することを繰り返すことでメモリを抑えるテクニックです).

さらに in-place 化してもなんか TLE します. 定数倍高速化のため, 更新する $j$ の範囲を限定すれば間に合わせることができます. 例えば, $dp[5][4]$ などは, 定義に合わせると $5$ 個の整数を $4$ 番目までで選ぶことに対応しているため, 明らかに値をとらず更新が不要です.

ACL のSegTree など高速な SegmentTree を用いないとどうやっても間に合わないかもしれません. 公式解説にはさらに $\mathrm{log}$ を落とした方法が載っているので確かめてみてください.

実装

Submission #146505254 - Codeforces

2022-02-15

Codeforces Round #547 (Div. 3)F2. Same Sum Blocks (Hard)

問題概要

長さ $n$ の数列 $a_i$ が与えられる. この中から総和が等しい区間を複数選ぶとき, 最大でいくつ選べるか？(構築せよ. ) ただし区間同士が重なってはならないものとする.

問題へのリンク

制約

$1 \le n \le 1500$
$-10^5 \le a_i \le 10^5$

解説

数列の長さが短いので, 区間の数が比較的少なく, 区間和としてとりうる値を全列挙することができます. ただし, これらすべての値についてどう選ぶかを実装しようとすると $O(n^4)$ や $O(n^2)$ 程度になってしまいうまくいきません.

そこで, std::map の key を区間和, value をその区間和をもつ区間 $\{l, r\}$ の vector として持ってみましょう. すると, 区間和を決めうったとき, 複数の区間からなる集合から重ならないようにたくさん選びましょうという問題になり, これは区間スケジューリング問題そのものです.

またこのように実装すると, ある区間についてたかだか $1$ 回しか見ることがないので, 全体としては $O(n^2)$ 回しか見ません. ということで, ソートの分を含めて $O(n^2\mathrm{log}n)$ で問題を解くことができました.

実装

Submission #146489204 - Codeforces

2022-02-15

Codeforces Round #529 (Div. 3)E. Almost Regular Bracket Sequence

問題概要

'(' と ')' で構成された長さ $n$ の文字列 $s$ が与えられる. この文字列のちょうど一文字を変更することで, $s$ が正しい括弧列になるような index は何個あるか？

https://codeforces.com/contest/1095/problem/E

制約

$1 \le n \le 10^6$

解法

正しい括弧列の判定方法は stack を用いた方法がありますが, 次のような条件を満たすときも文字列が正しい括弧列だということができます.

'(' を $1$ に, ')' を $-1$ に置き換えた数列 $a_i$ を考える.
$a_i$ について, その累積和を取ると, すべての要素が $0$ 以上であり, かつ $a_i$ の総和が $0$

総和が $0$ の条件は '(' と ')' の数が等しいことに対応し, 累積和が正だと対応するあまってしまう ')' が存在しないことになります.

これを用いて問題を考えます. まず '(' の数と ')' の数の差が $2$ でないとどうやってもちょうど一つ変更して正しい括弧列にはなりません. その場合は除外して考えます.

'(' が ')' より $2$ つ多い場合を考えましょう. 前述の累積和の配列を $p$ とすれば, $i$ 番目の '(' を ')' に変更することは, $p_i$ 以降すべてに $-2$ を足すことに対応します( $+1$ されていたものが $-1$ されるので). この操作によって総和が $0$ になることは保証されているので, $p_0 \sim p_{i-1}$ までと $p_i \sim p_{n-1}$ までが操作後すべて正であればよいです. これは区間最小値を求めることに対応します. SegmentTree を用いると簡単ですが, 端からの最小値を求められればいいので累積最小値でも求めることができます.

'(' が ')' より $2$ つ少ない場合は, 変更により加えられる数字が $2$ になること以外前述の例と同様です.

以上より, 区間最小値を Segmentree で求めるなら $O(n\mathrm{log}n)$ , 累積最小値で求めるなら $O(n)$ で答えを求めることができました.

実装

Submission #146347460 - Codeforces

2022-02-14

Codeforces Round #506 (Div. 3)D. Concatenated Multiples

問題概要

数字 $x$ と $y$ の連結を, 文字列として $x$ と $y$ を連結したときにできる数とする. たとえば $12$ と $3456$ の連結は $123456$ である.

長さ $n$ の数列 $a_n$ と $k$ が与えられる. このうち, $a_i$ と $a_j$ ( $i \neq j$ ) の連結が $k$ で割り切れるような順序付きペア $(i, j)$ の個数を求めよ.

問題へのリンク

制約

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

解法

$a_i$ と $a_j$ の連結が $k$ で割り切れるには, $a_j$ の桁数を $p_j$ として $(a_i\times 10^{p_j} + a_j) \equiv 0~\mathrm{mod}~k$ が満たされている必要があります. これを数え上げることにしましょう.

$a_i$ を固定したとき, $a_i \times 10^{p_j} \equiv -a_j$ を満たすものを数えます. 左辺に $j$ に依存する値が入っていて厄介ですが, $p_j$ は高々 $10$ 通りの値しかとらないので, (桁数が $t$ で, $k$ で割った余りが $s$ ) の個数をあらかじめ計算しておけば数え上げることができます( $-a_j$ を数え上げるのに注意してください).

(桁数が $t$ で, $k$ で割った余りが $s$ ) の個数はどう管理しましょうか？僕は普通に std::map で管理していましたが, std::map は定数倍が重く TLE するようです. 配列を用意し, 二分探索で個数を計算することにしましょう. これは, 座圧などでも言える話です.

なお, $i \neq j$ である必要があるので, この部分は考慮してコードを書く必要はあります.

実装

Submission #146323421 - Codeforces

2022-02-14

Codeforces Round #501 (Div. 3)E2. Stars Drawing (Hard Edition)

問題概要

書くのだるいので, サイトの文章を読んでください....

問題へのリンク

制約

$3 \le n, m \le 1000$

解法

こういうのと全く一緒です.

まず, 星の数は最小化する必要がなく, また重なってもいいということから, 作れる星は全部作ってしまうのがよいです(作れるのに作らないことは '*' を埋められるのに埋めないことになり, 明らかに無駄です).

そこで, あるマスについて, 自分の上下左右に何個 '*' があるかを数えたい気分になります. 普通に実装すると $O(n^2m^2)$ で TLE します.

そこで, $L[ i ][ j ]$ を自分の左にある '*' の数として定義します. これは, 動的に更新すれば $O(nm)$ で構築できます(累積和みたいな感じです). あとは右上下も同様に前計算すれば, あるマスの上下左右の '*' の数は $O(1)$ で求められることになります.

あとはつくれるだけ星を作り, それがもとの分布と一致しているかを確かめれば良いです. ある区間を '*' に変更するクエリは愚直にやると $O(n^2m^2)$ になるので, うまいことやってください. imos 法が楽だとは思いますが, 遅延セグ木, dsu なんかでもできると思います.

実装

長いですが, やってることは非常にシンプルです.

Submission #146311286 - Codeforces

2022-02-13

Codeforces Round #486 (Div. 3) D. Points and Powers of Two

問題概要

数直線上の $n$ 個の点 $x_1, \cdots, x_n$ が与えられる. この中から適当な個数の点を選び, 選んだ点を $x_{i_1}, \cdots, x_{i_k}$ としたとき任意のペアについて $|x_{i_a} - x_{i_b}|$ が $2$ の累乗になるようにしたい. このとき, 最大何個の点を選ぶことができるか？構成とともに示せ.

制約

$1 \le n \le 2\times 10^5$
$-10^9 \le x_i \le 10^9$

解法

明らかに $1$ 点のみを選ぶことは可能です. また, $2$ 点選ぶのも, ある点 $x_i$ に対して選びうる点は $x_i \pm 2^d$ だけですから適当な $d$ の範囲について対応する点が存在するかどうかを判定すれば良いです.

$3$ 点選ぶ時の条件は何でしょうか？ $x_a \lt x_b \lt x_c$ なる三点を選ぶとき, $x_b - x_a = x_c - x_b = 2^d$ を満たすことが必要です. もし $x_b - x_a \neq x_c - x_b$ となるなら, $x_c - x_a$ は少なくとも二つの bit が立ってしまいます(二進数で考えるとわかりやすいです). この判定も候補が定数個なので適切に実装すれば実行時間制限以内に解が存在することを確かめることができます.

$4$ 点以上選ぶのは明らかに不可能です. $x_a \lt x_b \lt x_c \lt x_d$ を選ぶならば, $3$ 点の時の議論から $x_b - x_a = x_c - x_b = x_d - x_c = 2^d$ がなりたたければなりませんが, このとき $x_d - x_a$ は明らかに $3$ の倍数になってしまいます.

以上より, 確かめる解の大きさの最大値は $3$ なので, その部分を全探索すれば良いです.

実装

解の上限が大きさ $3$ だとあらかじめわかっているので, $3$ の解があればそれをすぐに出力しています.

Submission #146217002 - Codeforces

2022-02-11

Codeforces Round #501 (Div. 3)D. Walking Between Houses

問題概要

$1$ から $n$ の数直線上の整数の点どうしを移動し, ちょうど $k$ 回の移動で総移動距離を $s$ にしたい. これは可能か？可能なら構成例を示せ. ただし, 一回の移動では必ず $1$ 以上移動しなければならない.

問題へのリンク

制約

$2 \le n \le 10^9$
$1 \le k \le 2\times 10^5$
$1 \le s \le 10^{18}$

解説

こういう問題が好きな人, この世にいるんですか？僕は普通に嫌いです.

構築系では, まずできない場合はどんな場合かを考えましょう. 移動距離の上限は $n-1$ ですから, $k$ 回の移動では $(n-1)k$ の距離までしか移動できません. $s$ がこれを上回っていた場合は構築できません.

また同様に一回の移動距離の下限は $1$ ですから, $k$ 回の移動では少なくとも $k$ だけ移動します. $s$ がこれを下回る場合には構築できません.

逆に, 上記を満たしている場合には必ず構築できます. 基本的には, $n-1$ 移動したとしても残り移動距離が残り移動回数よりも多い間は $1$ と $n$ を往復し, いい感じに残り移動回数が残り移動距離と等しくなるように調整した後 $1$ の移動を繰り返せばよいです. 詳しくは実装を見てください.

実装

Submission #145953182 - Codeforces