Codeforces Round #674 (Div. 3), Codeforces Round #677 (Div. 3), Codeforces Round #690 (Div. 3) バチャ

Codeforces Round #674 (Div. 3)(2022/5/3)

A: Floor Number

$n\ge 2$ の時だけ場合分けをして残りは割り算によって求まる.
https://codeforces.com/contest/1426/submission/155732980

B: Symmetric Matrix

まず $m$ が奇数の時は明らかに敷き詰められない.
$m$ が偶数の時は, 対角成分を敷き詰めるために, 1,0成分と0,1成分が等しい行列が存在する必要がある.
逆に, 全ての要素をこの行列で敷き詰めたものは対角行列になる.
https://codeforces.com/contest/1426/submission/155733423

C: Increase and Copy

1加算を繰り返したのちにコピーを繰り返す場合のみを考えればよい.
この時, $i(i-1)\lt n\le i(i+1)$ の時に数字を $i$ までしてからコピーをするのが最適.
https://codeforces.com/contest/1426/submission/155733894

D: Non-zero Segments

前から累積和を記録していき, 過去に登場した累積和と現在見ている累積和が等しくなった場合, その部分の区間和が0になるので, その直前に適当な数を入れる必要がある.
この時, とんでもなく大きい値を入れればその値を含む区間和が0となる事はないため, それ以前の結果をリセットできる. これを繰り返せばよい.
https://codeforces.com/contest/1426/submission/155734194

E: Rock, Paper, Scissors

勝利数の最大値は, Aliceの各手に対して, Aliceが勝てるようなBobの手をできるだけ出すようにすればよい.
最小値は, Aliceの各手に対して, まずAliceが負けるようなBobの手をできるだけ出し尽くし, 次にあいことなるようにBobの手を出していけばよい.
https://codeforces.com/contest/1426/submission/155734483

F: Number of Subsequences

DP $\lbrack i\rbrack\lbrack j\rbrack$ に, 文字列の前から $i$ 文字までの部分文字列で, "abc" の $j$ 文字目まで完成させる場合の数という動的計画法を行う.
更新は, $i+1$ 文字目を用いるか用いないかで場合分けをし, さらに $i+1$ 文字目が'?' の場合は全ての文字にした場合の遷移をそれぞれ行えばよい.
https://codeforces.com/contest/1426/submission/155734905

総括

27分全完0ペナ11位. スピードラン系の回はスムーズに行くとかなり楽しいね.

Codeforces Round #677 (Div. 3)(2022/5/6)

A: Boring Apartments

4電話毎に10桁というのを利用すると楽. 愚直にやっても可.
https://codeforces.com/contest/1433/submission/156071356

B: Yet Another Bookshelf

答えは最も左の本と右の本の間にある空白の数である.
一回の移動でこの空白を最大1つ減らすことができ, 最終的の形では空白が0であることから考えるとよい.
https://codeforces.com/contest/1433/submission/156071819

C: Dominant Piranha

支配的な魚がいる時, 初期の大きさが最大で支配的な魚が必ずいる.
また, 大きさが最大の魚はその両隣の少なくとも一方が自分より小さければその魚を食べて, 単独トップの大きさになれるので支配的となれる.
https://codeforces.com/contest/1433/submission/156072090

D: Districts Connection

全ての街のペアに対して, それらの街が別のギャングに支配されているかつまだ道で繋がっていない場合に繋いでいく.
接続判定はdsuを使うとよい.
https://codeforces.com/contest/1433/submission/156072395

E: Two Round Dances

まずグループへ分ける.
これは $n-1$ 人のうち, 人1と同じ組になる $\frac{n}{2}-1$ 人を選ぶ組み合わせである.
次に各グループ内での順番を決めるが, これは $\frac{n}{2}$ 人からなる数珠順列である.
掛け順を適当にするとオーバーフローするかも.
https://codeforces.com/contest/1433/submission/156072947

F: Zero Remainder Sum

各行に対して, DP $\lbrack i\rbrack \lbrack j\rbrack \lbrack k\rbrack$ を, $i$ 列目までの要素を考えて, $j$ 個の要素を足し合わせた和を, $K$ で割った余りが $k$ となる時の和の最大値とする動的計画法を行う.
MLEが怖かったので, 各行の計算が終わったらその行の最終結果を次の行に持ち越してそれ以外の結果を破棄するという工夫をしてみたが効果は不明.
https://codeforces.com/contest/1433/submission/156073987

G: Reducing Delivery Cost

サンプル2のように元の最短路とコスト変更後の最短路が異なる場合があるので難しい.
ある道のコストを0にしたときの経路長の和が高速に求まれば嬉しい.
そのためには各頂点から各頂点への最短経路が求まれば良さそう.
これが分かれば, コスト変更後の最短経路は, その辺を使わないかその道を使う(2方向)の3パターンでそれぞれ $O(1)$ で求まるので, 全体のスコアも $O(k)$ で求まり, 全ての辺のコストを0にするのを試せる.
各頂点から各頂点への最短経路は初め脳死でワーシャルフロイドをしたが当然間に合わない.
辺の数がかなり少なく設定されているので, 各頂点を始点にダイクストラ法をすればよい.
https://codeforces.com/contest/1433/submission/156075142

総括

51分全完2ペナ59位. ペナがどっちも頭が使えていないペナなので無念. それ以外はまあまあ.

Codeforces Round #690 (Div. 3)(2022/5/8)

A: Favorite Sequence

両端のindexを持っておいて, 出力して, indexを1内側に動かすというのを2つのindexが重なるまですればよい. 前半後半を別の配列で持って後半を反転して交互に前から出していくとかの方が早く実装できた気もする.
https://codeforces.com/contest/1462/submission/156262540

B: Last Year's Substring

操作後に残る文字列は元の文字列の接頭辞と接尾辞をくっつけたものであるので, 接頭辞, 接尾辞でそれぞれ2020の何文字目までを作れるかを計算し, その和が2020の文字列長4以上であれば良い.
https://codeforces.com/contest/1462/submission/156262742

C: Unique Number

桁和の最大は $1+2+\dots+8+9=45$ であるのでそれより大きいなら-1.
そうでない時, 下の桁に大きい数を詰めれるだけ詰めていけばよい.
https://codeforces.com/contest/1462/submission/156262929

D: Add to Neighbour and Remove

操作のバリエーションが多いように感じるが, 本質的には, 数列をいくつかに区切って各区間の総和を等しくするときに区切る数の最大はいくつですかという問題になる.
これは, 1つ目の区切りの位置を全探索で決め打ちすれば, 残りの区切りに関しては累積和を利用して貪欲に区切っていける, または区切るのが不可能であるか判定が $O(n)$ でできるので, 全体で $O(n^2)$ で求まる.
https://codeforces.com/contest/1462/submission/156263592

E1: Close Tuples (easy version)

E2の入力の1部が固定値なだけなので省略.
https://codeforces.com/contest/1462/submission/156263880

E2: Close Tuples (hard version)

数列を昇順にソートしておく. 同じ値に関しても適当に順番を付けておく.
$a_i$ が最小値であるような条件を満たすtupleの数を求め, $i$ に関して足し合わせればよい.
$a_i$ が最小値である時, 使える数は $a_i$ より大きく, $a_i+k$ 以下の数である. この個数はlower_bound等で求まる.
このうち, tupleに使う数 $m-1$ 個を選べばよく, これは二項係数で行える.
https://codeforces.com/contest/1462/submission/156264036

F: The Treasure of The Segments

全体との共通点を持たせるセグメントを固定した時, この問題はそのセグメントと交わらないセグメントの数を高速に求める問題となる.
2つのセグメントA,Bが交わらないのは, 「Aの右端よりBの左端が真に大きい」か「Aの左端よりBの右端が真に小さい」の2パターンあり, これらは同時には起こりえない.
よってこのそれぞれのパターンになるセグメントの数を数えればよく, それぞれの端の座標を昇順にソートしておくとlower_bound等で高速に求めることができる.
https://codeforces.com/contest/1462/submission/156265251

総括

35分全完1ペナ26位. ペナの10分で順位を10落とした. もったいなし. 全体的に見ればかなりスムーズに解けた.

仮のブログ

仮です