Codeforces Round #598 (Div. 3), Codeforces Round #615 (Div. 3), Codeforces Round #617 (Div. 3) バチャ

Codeforces Round #598 (Div. 3)(2022/4/17)

A: Payment Without Change

出来るだけ価値 $n$ で支払って残りを価値1で支払う.
https://codeforces.com/contest/1256/submission/153854630

B: Minimize the Permutation

後ろから見ていって, 一個前より小さいかつその位置のswapをまだしていないならswapというのを100回位繰り返せばよい.
他にも1をできるだけ前にしてその後2をできるだけ前にして...としていっても良さそう.
https://codeforces.com/contest/1256/submission/153854966

C: Platforms Jumping

各プラットフォームで最も右に置いたらどの位置か, 最も左に置いたらどの位置かを求めて常にその間に入るように板を置いていく.
NOの時にreturn0をし忘れて不必要な条件を考えたりして時間を喰った.
https://codeforces.com/contest/1256/submission/153861408

D: Binary String Minimizing

文字列の代わりに, 各0に対してそれより左にある1はいくつかという配列をもつ.
例えば, 11011010 であれば, 2,4,5 という配列となる.
元の文字列の辞書順最小はこの配列の辞書順最小であり, swapの操作は, 配列の要素を1減少させることに当たる.
よって, まず先頭の項をできるだけ減らし, 次に2項目をできるだけ減らし,...をしていけばよい.
上の例で $k=5$ の場合, まず初項に操作をして, 0,4,5 となり, 残りの操作回数で2項目に操作をして, 0,1,5となる. これを文字列に復元すると, 01011110 であり確かに一致する.
復元は隣接項の差=間に挟まる1の数なので容易.
https://codeforces.com/contest/1256/submission/153857070

E: Yet Another Division Into Teams

まず数列を昇順に並べる.
明らかにチームの人数は3~5人のみを考えればよく, すると前から $i$ 人目までチーム割を確定させたときの多様性の最小値を状態に持たせたDPができる. 特に特筆すべきことのない復元パートが面倒くさい.
https://codeforces.com/contest/1256/submission/153859167

F: Equalizing Two Strings

全ての反転操作は, 長さ2の文字列の反転操作の繰り返しによって実現できる.
よって, 隣接項のswapの繰り返しで二つの文字列を一致させられるかを見ればよい.
まず2つの文字列を辞書順最小に並び替えた時に一致しなければ答えは明らかにNOである.
そうでないときは, 辞書順最小との転倒数の偶奇が一致することが必要十分.
自分の実装では同じ文字がある時の動作が不安であったので, 同じ文字がある場合はその文字を一か所だけ入れ替えて判定をもう一度行った.
(追記: 同じ文字がある場合, 転倒数の偶奇どっちにもできるため2回目の判定は不要だった) https://codeforces.com/contest/1256/submission/153859675

総括

1時間43分全完2ペナ142位. 後半をCDCEFCという順で考えたが, Cに時間を取られすぎた. D~Fにつまる問題があまりなかったので, Cを一旦綺麗に忘れ去って最後に回すべきだった. 順位表を上手く使っていきたい.

Codeforces Round #615 (Div. 3)(2022/4/22)

A: Collecting Coins

$\max\lbrace a,b,c\rbrace=M$ とすると, まず三人のコインの数を等しくするために少なくとも $(M-a)+(M-b)+(M-c)=3M-a-b-c$ 枚のコインが必要である.
これが $n$ より大きかったらその時点でNOである.
そうでない場合, 余ったコインを三人で均等に分けるには, $n-(3M-a-b-c)$ が3の倍数である事が必要十分となる.
https://codeforces.com/contest/1294/submission/154635286

B: Collecting Packages

いずれの移動をする場合でも一回の操作で, $x+y$ の値は1ずつ増加する.
よって, $x+y$ が等しい荷物があればその時点で回収は不可であり, そうでない場合(回収できる場合の)回収順は一意に定まる.
また, $x,y$ の座標も移動によってそれぞれ広義単調増加をするので $x+y$ の値で荷物をソートした時 $x$ 座標と $y$ 座標がそれぞれ広義単調増加をする必要がある.
逆にそうなっているとき, 全回収が可能である.
https://codeforces.com/contest/1294/submission/154636082

C: Product of Three Numbers

重複を取り除いた全探索で間に合う.
$a$ を, $2\le a, a*a*a\le n$ の範囲で全探索. $b$ を $a\lt b, a*b*b\le n$ の範囲で全探索をし, $c=n/(a*b)$ として適するか確かめる.
この全探索で間に合うか微妙なラインだったが, 試したら思いのほか高速だったのでそのまま出した.
$a$ の全探索の時点で $n$ の約数でない $a$ を飛ばすようにするとかなり速くなるはずので間に合わなければそれをするつもりだった. (追記: 実際にこっちも出したら60倍以上速かった.)
https://codeforces.com/contest/1294/submission/154636359 (これは遅い方)

D: MEX maximizing

MEXの値は単調増加かつ高々クエリ数以下となるので何とかこの性質を利用できそう.
$+x,-x$ を自由にしてよいというのは, $x$ で割った余りが等しい数は同一視して良いという事である.
よって, クエリで受け取る値を $x$ で割った余り毎にカウントしていく.
1つ前のクエリまでのMEXの値が $m$ であり, 現在のクエリまでに受け取った値のうち, $\pmod x$ が $i$ であるものの数を $X_i$ とすると, MEXが $m+1$ 以上となるためには, $m$ を $x$ で割った余りを $r$ として, $X_{r}>\frac{m}{M}$ である事が必要十分である. MEXの更新を行った後さらに更新できる場合は再び更新を行っていく.
最初の考察より, このMEXの更新は高々クエリ数回しか行われないので間に合う.
https://codeforces.com/contest/1294/submission/154636857

E: Obtain a Permutation

列ごと独立に考えて最後に値を足し合わせればよい.
また, 要素を書き換えるという操作は最後に纏めて行ってよく, 書き換える必要のある個数は, 完成後の行列との不一致数である. よって, 回転を全部試して, 完成後の行列との不一致数と回転数の和が最小になるところを探せばよい.
しかし不一致数を追うと計算量がよろしくないので, 回転毎に完成行列との一致数を追って, 全体から引くようにする.
完成行列の各成分の値は全て異なるので, 元の行列の各要素がある回転によって完成行列のどこかと一致する場合でも, そのような回転の方法は1通りだけである.
さらにその回転の方法は計算で求まるので, 各要素に注目することで, 各回転で何個の要素が一致するかを高速に求めることができ, この問題に答えることができる.
https://codeforces.com/contest/1294/submission/154637866

F: Three Paths on a Tree

解説を読むと3頂点のうち2つは木の直径をなす2点となるらしい.
確かに木の直径となる頂点を用いていない場合, 3点のうち1点を上手く選ぶとスコアを大きくできることが示せる. 残りの1頂点は多始点BFSで求まるので実装は重くない.
バチャ中の自分はそんなことには気づかなかったので気合で木DPをした.
根を適当に決めて, 各頂点の部分木から頂点を0,1,2,3 個選んだ時のスコアの最大値と選ぶ頂点をもたせることを考えると, 葉から順に頑張って更新をして行ける.
詳細はただ大変で地道な作業となってしまったので略.
https://codeforces.com/contest/1294/submission/154642350

総括

1時間16分全完1ペナ43位. Fの考察をおろそかにして筋肉実装をしてしまったのが反省点ではあるが, 結果的には上々. DとかEとかの一見高度なアルゴリズムが必要そうな問題を工夫によって簡単なものの組み合わせで実装できる系統の問題が好き.

Codeforces Round #617 (Div. 3)(2022/4/26)

A: Array with Odd Sum

初めから総和が奇数なら問題なし.
総和が偶数なら奇数を偶数へか偶数を奇数へ変更する必要がある. 偶数と奇数がそれぞれ1つずつ以上あればこれは可能.
https://codeforces.com/contest/1296/submission/155013039

B: Food Buying

10以上持っているとき, 10支払って1ポイント還元を得ることは, 所持金を9減らして10の報酬を得るのと等価である.
よって基本的には $s$ に対して $10*\lbrack\frac{s}{9}\rbrack$ 得ることができる.
最後に残った9から10報酬得ることはできないので注意.
https://codeforces.com/contest/1296/submission/155013323

C: Yet Another Walking Robot

2回以上同じ座標に行くかを見る.
各座標に対し, そこに着いた最後の時刻を記録しておくと同時に消す文字列の最短を求められる.
https://codeforces.com/contest/1296/submission/155013994

D: Fight with Monsters

各モンスターに対して, 1ポイントを得るためにスキルを何回必要かを求める.
まずギリギリまでスキルを使わずモンスターの体力を減らしていく. この操作は $h$ を $h\%(a+b)$ に置き換えることで一気に行える.
この後は $b$ を減らす攻撃を行うと体力が0以下になるため全て $a$ 減らす攻撃を行う必要があるので必要なスキル使用回数が計算で求まる.
https://codeforces.com/contest/1296/submission/155015300

E1: String Coloring (easy version)

E2と同じ

E2: String Coloring (hard version)

文字列を前から見ていって, できるだけ小さい番号を振っていく.
元の文字列の $i$ 文字目がソート後に $a_{i}$ 文字目になっているという関係を $(i,a_{i})$ と表すと, $j\lt i$ に対して, $j,i$ に同じ色を割り振れる条件は $a_{j}\lt a_{i}$ である.
よって, 各色に対する $a_{hoge}$ の最大値を管理しながら $i$ の小さい順に更新していけばよい. 具体的には, 各色に対する $a_{hoge}$ の最大値をsetで管理しておくと, 新たに $i$ 番目の色を決めるのは $a_{i}$ の値をsetに対してlowerbound-1し, setを更新すればよい. 既にある色で使えるものが無ければ新たな色を増やして $a_{i}$ をsetに突っ込む.
https://codeforces.com/contest/1296/submission/155017223

F: Berland Beauty

各乗客の証言から, $a,b$ のパス上の景観度が $g$ 以上である必要があることが分かる.
よって, まず全ての辺の美しさを1で置いておき, 証言を得るごとにパス上の景観度をもとの値と証言で得た景観度の大きい方で置き換えていく.
一通りの更新を終えた後に, 全ての乗客の証言と不一致がないかを確かめ, 不一致が無ければそれを出力をすればよい. 不一致があれば解は存在しない.
この判定方法は以下のように正当化される.

乗客の景観度を下回らないようにパス上の景観度を更新しているため, もし乗客の証言と不一致があるとしたら, 現在の景観度が証言より大きい場合に限る.
一方, 各更新ではそれ以上は小さくできないというラインで更新をしている. よって, 現在の景観度を小さくしようとすると, どこかの証言と不合致を起こす.
よって, この方法で不一致があるならどう頑張っても証言と不一致する.

実装の際は $O(n^2)$ が通る制約なので毎回BFSでパスを探して愚直に更新や判定をすればよい. 毎回全てリセットする方針でも 2995ms でかろうじて通った. LCAとかを管理してパスの探索を毎回しなくて良いようにしたら少なくとも定数倍はかなり改善すると思う.
木をパスとしてうまく持つことで木上の区間更新とかができるのがあった気がするのでそれを使えばオーダー自体も改善できそう.
https://codeforces.com/contest/1296/submission/155019077

総括

1時間14分全完2ペナ83位. どこかの問題で大幅に詰まるという事は無かったが, 全体的にもっと早く解けたのではの気持ち.

仮のブログ

仮です