Codeforces Round #764 (Div. 3)

はじめに

バチャの記録

結果は $5$ ペナ全完 $175$ 位？ さすがにペナひどい

本文

A. Plus One on the Subset

概要

数列 $a$ が与えたられる

好きな数の要素を選んでインクリメントする という操作を繰り返してすべての要素を一致させるとき, 操作の最小回数を求めよ

解法

最大値と等しくないものを全て選ぶ ということを貪欲に繰り返せばよい

$\max a - \min a$ 回

提出コード

蛇足

std::minmax_element は実装がとても賢くて, 比較回数が $\max(\lfloor\frac{3(n - 1)}{2}\rfloor, 0)$ で済みます

その代わり, 同じ値の要素が複数ある場合, 最小値は最も左のものが, 最大値は最も右のものが選ばれます これで困ることはほとんどないと思いますが

B. Make AP

概要

長さ $3$ の数列が与えられる

好きな要素を選んで好きな自然数をかける という操作を一度だけ行って,数列を等差数列にできるかを判定しなさい

解法

並べ替えありかと思って next_permutation しようと思ったら違った

どの要素を変更するのかを決めると, 何に変更しなければいけないかも自動的にわかる それが可能かを判定すればいい

提出コード

C. Division by Two and Permutation

概要

長さ $n$ の数列 $a$ が与えたられる

好きな要素を選んで $2$ で割る (切り捨て) を好きな回数行うことで, $a$ を $[1 \ldots n]$ の並び替えにすることができるかを判定しなさい

解法

明らかに大きい要素を作るほうが大変なので, 上から愚直に埋めていくことにする
$a$ の要素を全て最大ヒープにいれる

各 $i = n \ldots 1$ について, ヒープの最大値が $i$ より大きい限り $2$ で割る を繰り返す

ヒープの最大値が $i$ と一致したらそれを採用 しなければ不可能

どの要素も高々 $\log a _ i$ 回しか割られないので, 計算量は $O(n\log a\log n)$ とかのはず

提出コード

D. Palindromes Coloring

概要

文字列 $s$ が与えられる

$s$ の各文字を $k$ 色に塗り分ける このとき, 塗られていない文字があってもいいがどの色も使われていなければならない

同じ色で塗られた文字は適切に並び替えることで回文にすることができる という条件を満たすように塗り分けたとき, 同じ色で塗られた文字の数の最小値 の最大値を求めよ

解法

同じ長さの回文を $k$ 個つくる としてよい

よって, 偶数個ある文字をそれぞれに分配したあと, 残ったものを高々一つずつ配ればよい

提出コード

バチャではわざわざシュミレートして $1$ ペナ生やしたが, 冷静に考えるとそんな必要なかった

出し直し

E. Masha-forgetful

概要

長さ $m$ の数字列 $s$ と, 同じく長さ $m$ の数字列 が $n$ 個与えられる

どの部分文字列も $n$ 個の数字列のどこかに含まれるように, $s$ を長さ $2$ 以上の(連続する)部分文字列 に分解することができるが判定し, 可能ならどれがどこに含まれているのかを答えなさい

解法

分割の個数は最小化する必要ないので, それぞれの部分列の長さは高々 $3$ としてよい

$s$ の prefix を条件を満たすようにできるか をdpで求めて, 復元する

$n$ 個の数字列の長さ $2$ or $3$ の部分文字列にわけた結果を全て列挙しておけば遷移が高速にできるので, 後は頑張る

提出コード

不可能な場合の打ち切りを忘れていて $1$ ペナ

F. Interacdive Problem

概要

整数 $n$ が与えられる 以下の操作を高々 $10$ 回行って, 整数 $x \in [1, n)$ を当ててください

• 整数 $c \in [1, n)$ を選び, $x$ に $c$ を足す その後, $\lfloor\frac{x}{n}\rfloor$ の値を知ることができる

解法

制約が二分探索と言っている

$c % n$ の値の範囲を二分探索する

途中で区間がやばいことにならないのか は未証明で出しました... (冷静に考えると大丈夫)

提出コード

これ最後に解いたので, 時間がなくて焦って未証明で出しまくったら $3$ ペナ生えた

G. MinOr Tree

概要

重み付き無向グラフが与えられるので, 最小全域木の重みを求めなさい

ただし, 重みの和 は足し算ではなく bitwise OR

解法

貪欲に上の桁から削れるだけ削る

その bit が立っていないような重みの辺だけを使って全域木を構築できるなら, そのような辺だけを残す

ということを上 ($2^{30}$ の bit くらい) から見ていく 判定は UnionFind を使うと楽

提出コード

なんかめっちゃ解かれてたので先に見たら簡単だった F と交換してほしい

おわりに

感想

• F みたいな変則にぶたん苦手なのでとても困った
• ↑ にしても $3$ ペナはひどい

そのせいで結果的に制限時間 $10$ 分くらいしか残りませんでした...