Codeforces Round #587 (Div. 3), Codeforces Round #590 (Div. 3), Codeforces Round #595 (Div. 3) バチャ

Codeforces Round #587 (Div. 3)(2022/4/14)

A: Prefixes

偶数番目の文字と奇数番目の文字が同じ時どちらかを変えればよい.
https://codeforces.com/contest/1216/submission/153634293

B: Shooting

ほぼ明らかに $a$ の大きい順に処理するのが良い.
https://codeforces.com/contest/1216/submission/153634945

C: White Sheet

頑張って何とか判定をする.
自分は, 白いところが見えているなら, 必ず白い長方形の境界上の点で黒い長方形に覆われていないものがあることを利用した.
さらに, そのうち座標が半整数の物だけ見ればよいので, 初めに全ての座標を2倍することで処理をしやすくした.
おそらく頑張れば $O(1)$ でできるが, 自分は $O(l)$ ( $l$ は周長) でやった.
https://codeforces.com/contest/1216/submission/153635769

D: Swords

最も多く残っている剣は一本もとられなかったとしてよい.
すると, とられた剣の本数が求まるので, それらの最大公約数を取れば, $z$ の値が求まり, $y$ が求まる.
https://codeforces.com/contest/1216/submission/153636384

E1: Numerical Sequence (easy version)

E2と同じ方法でやった.
$i$ ブロックまで数列を並べた時の全体の長さは $\Omega(i^2)$ となるのでeasyの制約ならブロックごとに数列を見ていって間に合うと思う.

E2: Numerical Sequence (hard version)

必要な情報は, 何ブロック目の数列か, そのブロックの何項目か, その項の何桁目かという事である.
これを順に求めていく.
まず, 何ブロック目の数列かを二分探索で求める.
そのために, $i$ ブロック目の末項が全体の何番目かを高速で求められるようにしておく.
各数の出現回数を考えると, 1が $i$ 回, 2が $i-1$ 回, ... ,10が $i-9$ 回, ... , $i-1$ が2回, $i$ が 1回という事が分かる.
これらをさらに桁数ごとにまとめることで, $j$ 桁の数が何回出現するかが求められるので, それらを足し合わせれば, $i$ ブロックの末項が全体の何番目かが求まる.
これを用いて全体の $k$ 番目が何ブロック目かが分かる.

また, ここから目当ての数がブロック内の何番目かが分かる.
これが何項目の数にあたるのかは再び二分探索で求める.
先ほどと同様に, $j$ 桁の数が何回現れるかを考えるとこれも高速に行える.

最後のその項の何桁目かは高々十数桁なので愚直に見ていけばよい.
全体に境界とかの細かい処理が間違えそうだったのでデバッグモードや途中結果の出力で関数の中を確認しながら実装した. おかげで一発.
https://codeforces.com/contest/1216/submission/153638928

F: Wi-Fi

できるだけ小さいところにルーターを置ければ嬉しい.
よって, 番号の大きい方から見ていって, できるだけ番号の小さい方にルーターを置いていくのが良い.
具体的には, 以下のようなDPをする.
$DP\lbrack i\rbrack$ : $i,i+1,\dots,n-1$ 番の部屋に回線がつながっているときのコストの最小値という配列を用意.
更新は,

$DP\lbrack i\rbrack$ に本体を置くとき, $DP\lbrack i+1\rbrack$ から $DP\lbrack i\rbrack$ へ遷移.
$DP\lbrack i\rbrack$ にルーターから回線を引くとき, $i$ を範囲に含むルーターのうち, 最も番号の若い位置にルーターを置く. そのルーターの番号の小さい方の端を $l$ として, $DP\lbrack i+1\rbrack$ から $DP\lbrack l\rbrack$ へ遷移.

の2つを行えばよい.
https://codeforces.com/contest/1216/submission/153642875

総括

1時間26分全完0ペナ24位. 神経を使う問題で0ペナなのは良い.

Codeforces Round #590 (Div. 3)(2022/4/15)

A: Equalize Prices Again

数列の要素の総和を $S$ として, $\left\lceil\frac{S}{n}\right\rceil$ を出力すればよい.
https://codeforces.com/contest/1234/submission/153724220

B1: Social Network (easy version)

B2と同じ

B2: Social Network (hard version)

細かいところを詰めるのに少し時間がかかった.
{何番目に追加されたか, id} を持たせたsetと, M[id]="set内に存在するか否か" を持たせたmapを用意すると, 存在判定・削除・追加を全て実現でき, 常に画面の状態をsetが表しているようにできる.
https://codeforces.com/contest/1234/submission/153725052

C: Pipes

$i$ 列目の上の段, 下の段に水を流せるかをそれぞれbool値で管理する.
$i$ 列目の $j$ 段目のパイプが直線の場合, その段の前の行に水を流せる場合水を流せる.
また, この時以外に, 両段共に曲がったパイプの場合, $i-1$ 列の下の行に水を流せるなら $i$ 列の上の行に, $i-1$ 列の上の行に水を流せるなら $i$ 列の下の行に水を流せる.
最終的に, $n+1$ 行目の下の段に水を流せるかを判定すればよい.
https://codeforces.com/contest/1234/submission/153725617

D: Distinct Characters Queries

各文字の出現位置をsetで管理しておく.
文字の変更クエリはこのsetの削除, 追加及び文字列の変更を行えばよい.
文字種カウントクエリは, 各文字 $c$ に対し, $l$ 文字目以降の $c$ の初めての出現位置と, $r+1$ 文字目以降の $c$ の初めての出現位置をlowerboundで行い, これらの結果が異なれば, 区間内に $c$ が現れることが分かるのでこれを数える.
(cf: E - Simple String Queries 全く同じ問題) https://codeforces.com/contest/1234/submission/153726029

E: Special Permutations

順列 $p_{i}$ を $p_{i+1}$ に変更するには, $i,\ i+1$ を入れかえるだけで良い.
よって, この変更によって, 値が変わるのは, $x_j,\ x_{j+1}$ の少なくとも一方が $i,\ i+1$ の場合のみである.
よって, 各数 $1,2,\dots,n$ に対し, 数列 $x$ において隣合う数を配列で持っておいて, 値が変わりうるタイミングのみで参照するようにすれば, 全体で $O(m+n)$ で計算できる.
https://codeforces.com/contest/1234/submission/153727181

F: Yet Another Substring Reverse

文字種をわざわざ20に絞っているところからbit系のことをするのだろうと想像がつく.
実際, bitで考えるのが筋が良く, a,b,c...の出現を0,1,2...番目のbitが立っている事と対応させるとうまくいく.
区間を一か所反転させるとき, 任意の2つの区間を取った時, その2つをくっつけることができる.
よって, この問題は同じ文字を2つ以上含まないように2つの区間を選ぶときの区間長の和の最大値を答える問題となる.
そこで, $DP\lbrack bitmask\rbrack$ で, 文字の出現が $bitmask$ の部分集合で表される場合の区間の長さの最大値としておく.
この計算は, まず文字列の区間の左端を固定して, 同じ文字が区間内に入らない限り右端を伸ばしていくという事をして, そののち, bitの表す値の小さい方から順に大きい方へ包含させていく計算を行えばよい.
その後, $DP\lbrack bitmask\rbrack+DP\lbrack !bitmask\rbrack$ の最大値を求めればよい. 但し, $!bitmask$ はbitmaskの全てのbitを反転させた値である.
https://codeforces.com/contest/1234/submission/153729641

総括

1時間2分0ペナ全完20位. Fをスムーズに解けたのに成長を感じた.

Codeforces Round #595(2022/4/16)

A: Yet Another Dividing into Teams

差が1のペアがあれば答えは2. そうでなければ1.
https://codeforces.com/contest/1249/submission/153776852

B: Books Exchange

順列をサイクルに分解して, サイクルの個数を出力すればよい.
easy だけ解くなら本の移動を全てシミュレートすればよい.
https://codeforces.com/contest/1249/submission/153777097

C: Good Numbers

良い数であることと3進法で表記した際に全ての桁の数が0または1であることが同値である.
よって, 3進法表記で下の桁から見ていって, 良い数であるかつ最小のものを管理していけばよい.
各位の数が0,1,2のそれぞれの場合に良い数かつ最小という条件を満たすために必要な操作を考えればよい.
https://codeforces.com/contest/1249/submission/153777621

D: Too Many Segments

区間スケジューリングののりで, 右端でソートして $k$ 個以上と被っているなら除去, そうでなければ採用という事をしたら落ちた.
方針を少し変えて, 累積和を用意して小さい方の点から順に見ていく.
累積和の値が $k$ より大きければその点を覆っている区間で右端が最も大きいものを除去し, 累積和の値をいじるというのを全ての点に対して覆っている区間が $k$ 以下になるまで行ったら通った.
どういったケースで前者が落ちるのか結局最後まで分からなかった.
https://codeforces.com/contest/1249/submission/153779990

E: By Elevator or Stairs?

明らかに階を降りる移動は不要である.
階数及びエレベータに乗っているかのペアを頂点に持ち最短経路問題を解けばよい. 辺は, 階を1つ登るのとエレベータの乗降に対応させて貼ればよい.
自分はこれを最短経路問題として解いたが, 実際には下の階に下りないのでDPで良かったりする.
https://codeforces.com/contest/1249/submission/153780941

F: Maximum Weight Subset

複雑めな木DP.
各頂点に, その部分木で, 選んだ頂点の深さがその頂点から見て $i$ 以上である時のスコアの最大値を持たせる. すると, 更新は

その頂点を採用するとき : 全ての子の部分木で, 採用される頂点の深さが $k$ 以上となるようにする.
その頂点を採用しないとき: 各 $i$ に対して計算する. 深さ $i$ とする子を一つ選び, 残りの子に関しては, 間隔が $k$ 以下とならない範囲を計算で求めて足し合わせ, それらの最大値をとる.

によってできる. これで, 丁度深さ $i$ の場合を計算できたので累積maxをして深さ $i$ 以上の場合を計算できる. 計算量は多分 $n^2k$ .
https://codeforces.com/contest/1249/submission/153784286

総括

1時間36分全完5ペナ81位. 添え字合わせに苦労する回だった.

仮のブログ

仮です