Codeforces Round #644 (Div. 3), Codeforces Round #650 (Div. 3), Codeforces Round #653 (Div. 3) バチャ

Codeforces Round #644 (Div. 3)(2022/5/2)

A: Minimal Square

長い方の一辺が正方形の一辺となるか短い方の一辺を2つ並べたものが正方形の一辺となるか.
https://codeforces.com/contest/1360/submission/155566856

B: Honest Coach

昇順にソートして隣り合う要素の差の最小値.
https://codeforces.com/contest/1360/submission/155566946

C: Similar Pairs

隣あう2つの要素でペアになっているものを2つ以上作る必要はない.
なぜなら, $(a,a+1),\ (b,b+1)$ というペアがあったらこれは偶奇, 偶奇のペアなのでこれを偶偶, 奇奇のペアにすることができるからである.
よって, まず隣あう2つの要素でのペアを作らずにペア分けできるかを判定し, できない場合は隣り合う要素が存在するかを判定すればよい.
https://codeforces.com/contest/1360/submission/155567093

D: Buying Shovels

$n$ の約数を全探索すればよい. 全てで試し割りをしては間に合わないが, $\sqrt{n}$ 以下の数での試し割りなら間に合う.
https://codeforces.com/contest/1360/submission/155567230

E: Polygon

全ての1マスが右又は下の少なくとも一方が1マスまたは壁であるかが必要十分条件.
必要性は明らか. 十分性も右下の方から順に置いていくことを考えると明らか.
https://codeforces.com/contest/1360/submission/155567524

F: Spy-string

1つ目の文字列と1文字以下だけ違う文字列というのは, $25*m+1$ 個のみである.
これ以外は答えになりえないのでこれらを全探索すれば十分である.
判定部分も全ての文字列で1文字ずつやっても $O(nm^2\sigma)$ で十分間に合う. ( $\sigma$ は文字種数でここでは26.)
https://codeforces.com/contest/1360/submission/155567819

G: A/B Matrix

まず $a*n=b*m$ が必要である.
逆にこれを満たす時行列を構築できる. 以下に一例を示す.

$i$ 行目には, $(i-1)a+1, (i-1)a+2,\dots, (i-1)a+a-1\pmod{m}$ 列目に1を置く.

$a*n=b*m$ より全ての列に同じ数の1が置かれ, その数が $b$ 個となる.
https://codeforces.com/contest/1360/submission/155568044

H: Binary Median

気持ちとしては全体をソートして中央値を取り出したいが, $2^{60}\simeq 10^{18}$ であるのでそれは叶わない.
ここで視点を変えて, 取り除かれている側に注目すると, これは探索できる程度に少ない.
また, 文字列の並びはごく普通のソート順であるので, ある文字列 $mid$ より小さいかつ取り除かれていない文字列の個数というのは mid より小さい文字列の個数- $mid$ より小さく取り除かれる文字列の個数によって高速に求められる.
よって, mid の位置を二分探索で求めればよい.
https://codeforces.com/contest/1360/submission/155568944

総括

36分全完0ペナ10位. とても良い. 全問題で考察も実装もスムーズに行った.

Codeforces Round #650 (Div. 3)(2022/5/2)

A: Short Substrings

1文字目と奇数文字目を拾っていけばよい.
https://codeforces.com/contest/1367/submission/155584099

B: Even Array

奇数番目にある偶数の数と偶数番目にある奇数の数が異なれば-1, 等しければその値.
https://codeforces.com/contest/1367/submission/155584220

C: Social Distance

1と1の間隔から間に何人座れるかが求まる. 両端だけ勝手が違うことに注意.
https://codeforces.com/contest/1367/submission/155584589

D: Task On The Board

最も大きい文字が入っていた場所の $b$ の値は0である.
逆に, $b$ の値が0の場所は全て最も大きい文字が入る.
最も大きい文字が入る場所が決まれば, そこから各項への距離から, 最も大きい文字を無視した場合の $b$ の各値が求まる.
以下これを全ての文字が決定っするまで繰り返せばよい.
https://codeforces.com/contest/1367/submission/155586303

E: Necklace Assembly

使う長さ $L$ を決め打ちした時, $\gcd{(L,k)}$ 周期で同じ模様を繰り返す必要がある.
これさえわかってしまえば, 各飾りがいくつあるかの情報から長さ $L$ で条件を満たす飾りが作れるかが判定できるので, $L$ を全探索すればよい.
https://codeforces.com/contest/1367/submission/155586901

F1: Flying Sort (Easy Version)

動かさなくて良い部分列の最大長を求めると, これはソート後の数列で連続しているかつ, 昇順に並んでいることが条件である.
ソート後の順番と元の順番から, この最大長を求めることができる.
https://codeforces.com/contest/1367/submission/155588257

F2: Flying Sort (Hard Version)

EasyVerの手法に加えて, 部分列の前後には追加で項を追加できるのでとやろうとしたが合わなかった. 解説を見ても方針自体はあってるっぽい...

総括

A~F1の6完1ペナ152位. F2が通せたと思いきや通せなかったのが悔しい. Cにてこずったのもかなりスコアに響いてしまった.

Codeforces Round #653 (Div. 3)(2022/5/4)

A: Required Remainder

$\lfloor\frac{n-y}{x}\rfloor*x+y$
https://codeforces.com/contest/1374/submission/155759373

B: Multiply by 2, divide by 6

$n=2^a3^b\ (a\le b)$ と表せない時-1, そうでない時 $(b-a)+b$ .
https://codeforces.com/contest/1374/submission/155759568

C: Move Brackets

)を-1, (を+1とみて前から累積和を取っていく. 累積和が負になったら答えを1加算して累積和を0に戻す.
https://codeforces.com/contest/1374/submission/155759764

D: Zero Remainder Array

1番目の操作を1度しかできないので, $a_{i}$ には $k$ で割って $-a_{i}$ だけ余る数を加算しないといけない.
よって, $a_{i}$ を $k$ で割った余りで分類することで $x\to x+1$ を何回しないといけないかが分かる.
https://codeforces.com/contest/1374/submission/155760274

E1: Reading Books (easy version)

Bobにのみ興味がある本とAliceにのみ興味がある本をそれぞれ時間の昇順に並べ, 1冊ずつセットにすることで, 全ての本が, どちらにも興味があるものとしてよい.
すると, 単に本を時間で昇順ソートして小さい方から $k$ 冊の和を求める問題となる.
https://codeforces.com/contest/1374/submission/155760812

E2: Reading Books (hard version)

どちらにも興味のある本の冊数を決め打ちという方針でやったがなぜか合わない. 後からテストケースを見たが, 見える範囲では原因が分からなかった.

F: Cyclic Shifts Sorting

貪欲に小さい数を前に送っていく.
この時点で最後までうまく行ければそれで良い.
上手く行かない場合でも, 同じ値が複数回現れる場合は達成可能で, 同じ値2つを先ほどと逆順になるようにして再び貪欲にソートしていくとちゃんとソートできる.
操作回数は, 1つの要素を1つ前に進めるのに最大2回の操作なので, $n(n-1)$ 回で上から抑えられるのでOK. https://codeforces.com/contest/1374/submission/155763232

総括

E2以外の6完0ペナ41位. 順位表を見て早めにFに移れたので良かった. E2の原因が分からなかったのはもやる.

仮のブログ

仮です