Kotlin Heroes: Episode 11

Kotlin Heroes はコンテストには参加せず,C++ や Python で書いたコードを chatgpt に変換してもらうことで AC しています.コンテスト中にこれをやるのはルール違反です.

スポンサーリンク

A. Problem Solving

ソートして max と 2nd max を比べます.

B. Shuffle

1, 9, 8, 7, 6, 5, 4, 3, 2

C. Split the Expression

“+” で区切ってそれぞれの部分を独立に最適化すればよいです.

D. Among Wolves

全部倒す,左方向を $2$ 枚の壁で塞いで右側を倒す,右方向を $2$ 枚の壁で塞いで左側を倒す,両方を $3$ 枚の壁で塞ぐ.

E. Rock-Paper-Scissors Bot

$S$ は自分じゃなくて相手の手の列であることに注意.

先頭は特殊処理が必要として,相手の手の列を自分の手の列に置き換えます.さらに prefix や suffix に自分の手をいくつか追加する可能性がありますが,suffix は追加手数分そのまま得点を増やせるので,prefix は相手の手を合わせる目的のみの追加です.すると相手の手が同じところは複数経由しないので,prefix への追加は $2$ 個までです.

あとは目的の自分の手の列を消化した後も,最後の相手の手を見届ける必要があることなどにも注意.

F. Good Subarray

判定は,悪い要素があるかです.悪い要素とは,要素 $x$ であってその位置よりも左側に $x-1,x,x+1$ のどれも存在しないものです.

すると,最大長は悪い要素の位置の最小値として計算できます.

subarray の始点をインクリメントしながら悪い要素のインデックス集合を管理すればよいです.

G. Removal of a Permutation

愚直なシミュレーションを考えます.列の長さから $1$ を引いたものを大きさと呼ぶことにすると,$2$ 通りの遷移先での大きさの和は不変です.よって深さ $k$ のシミュレーションでは大きさの和が $n$,列の長さの和は $n+2^k$ でおさえられます.

$2^k>n$ となる深さまでシミュレーションすると,大きさ $0$ の遷移先が存在するためこの時点ですべての答が確定しているため,.それ以上大きな $k$ での探索は不要になります.大きな $k$ での探索を打ち切るだけの愚直な再帰的計算で $O(n\log n)$ 時間が達成されます.

H. Strange Matrix

bit ごとに独立に解けばよいです.考えるべき操作は各行に $0$ または $1$ を xor するというものです.この値を $x_i$ とします.

制約は,$x_i \oplus x_j=0$, $x_i\oplus x_j=1$ となることがそれぞれ許されるかというものです.

どちらも許されなければ答はNO,どちらも許される制約は無視して,他の制約がある $i,j$ 間に辺を張ったグラフを考えると,連結成分ごとに高々 $2$ 通りの定め方から選ぶということになります.

I. Stack and Queue

人を固定して,その人に対する矛盾が起こっている期間を考えます.

ひとつめの列での診察時刻区間が単調に減少し,ふたつめの列での診察時刻区間が単調に増加することから,矛盾が起こっている期間は空でないならば区間になります.これをすべての人について求めれば解けます.

並列二分探索を考えると,特定のタイミングと人についての $2$ つの区間を比べればよいということになります.これは Fenwick Tree でできます.

CodeForces
スポンサーリンク
シェアする
maspyをフォローする
maspyのHP
タイトルとURLをコピーしました