Educational Codeforces Round 96 (Rated for Div. 2) 参加記録

結果

A	B	C	D	E	F	G
00:04	00:07	00:21	00:30	00:54	-	-

5完。Div.2 rated内45位。あったまり。

1～Nまでの数字がある。2個選んで取り除き、その平均値（小数点以下切り上げ）を新たに追加する。数字が1つだけになったとき、その数字の最小値を求め、そのような数字の選び方を1つ答えよ。

切り上げ云々はさておき、平均を最小にする戦略を考える。

2つの数字aとbを選んで、その平均をxとする。次に、xと別の数字cを選んでその平均を新たなxとする。これを繰り返していくと、後に選んだ数字ほどxの値に影響するので、大きい数字から順に使っていけば良い。

切り上げに惑わされて時間を使った。完全二分木のような形で計算していく方法を考えてしまった。

0と1からなる文字列が与えられる。次の操作を行うことができる回数の最大値を求めよ。

操作:

ただし、1と2は必ず両方行う。また、必ずこの順に行う。

圧縮する。11101001 → [3, 1, 1, 2, 1]。圧縮後のリストを%%L%%とする。

すると、操作は「%%L%%の要素を1つ選んで1減らしたのち、先頭の要素を削除する」と読み替えることができる。

1減らす要素を選ぶときは「連続で同じ文字が並んでいるところ、かつ、なるべく先頭に近いところ」から選びたい。

毎回%%O(N)%%で線形探索するわけにはいかないので、少し工夫する。

現在減らそうとしている要素の位置を変数に保持しておいて、要素の値が1になるか、削除済みになった場合に次の位置を探しに行くという方針がシンプルか。

%%L%%の要素がすべて1になったら、あとは先頭から2個ずつ削除していく（最大%%\left\lceil \frac{|L|}{2} \right\rceil%%回操作できる）。

Hackしていて気づいたけど、もう少しオシャレなやり方があるみたい。

最大%%\left\lceil \frac{|L|}{2} \right\rceil%%回操作を行うことができる。

%%L%%の要素を先頭から順に見ていって、どれだけ無駄に削除する必要があるかを見ていくと、うまくいく。

文字列を反転させたい。隣同士の文字をswapする操作の回数が最低何回で達成できるか。

codeforces
->
secrofedoc

隣同士のswapという操作からいかにも転倒数を使って考えたくなる。問題をソートに帰着すれば解けそう。

上の例の場合、反転後の文字列を0123456789と置き換え、それがもとの文字列に対応させることで、転倒数を使って解くことができる。

すべての文字が1回しか出てこない場合はただ数列を反転するだけだが、同じ種類の文字が存在する場合はもっと効率の良い操作がある。

すなわち、同じ種類の文字について、反転前後で各文字の順序は変えずに対応させる。

2471583960
codeforces
->
0123456789
secrofedoc

これを実現するには、'a'から'z'までそれぞれの文字の位置を記録したリストを持っておく。

各文字種cに対して、左からi番目の出現位置idx[i]を反転した位置N-1-idx[i]を、右からi番目にあるcの反転後の位置に対応付ける。

あとは転倒数を求める。

自作のライブラリをしょっちゅう書き換えるので、正しい出力が得られないときにBITのバグを疑ってしまった。

解けず！　途中でお腹痛くなって離脱しちゃった。考えてみる！