人間だけど競プロやる

解けなかった問題を理解できたら記事を投稿します。日本語の解説が見つからなかったもの中心。

Codeforces Educational Codeforces Round 96 (Rated for Div. 2)

B. Barrels

最大量を増やせば良い。
一つでも移動すると、移動元は0になって、それが最小値になる。
よって大きい方からK+1個の和。

C. Numbers on Whiteboard

足して2で割ったものを小さくしたいということは、足す2数を小さくしたい。
よって大きい数から消費していけばよい。
実装はpriority queueを用いて、大きい方から2数を取り出し、2で割った結果を追加して、を繰り返す。

D. String Deletion

インデックスを指すポインタを2つ(ないし3つ)用意してうまく操作する。
まず与えられた入力を、同じ文字がいくつ連続するかの配列に加工する。
ex.) 111010 - > 3,1,1,1
操作1はまず2以上優先して探して、なければ1を探して-1をしていくのが最善なので、まとめると以下になる。

  • 操作1A:2以上を探して1を引く
  • 操作1B:1Aが出来ないとき、1を探して0にする
  • 操作2:1以上の最も左を0にする


操作1と操作2を実施するポインタをそれぞれ用意してうまく動かして回答する。
操作1Aができないとき、操作1Bは操作2を指し示すポインタから始まることに注意(調節しないとTLE)。

E. String Reversal

スワップ」「スワップ回数の最小値」というキーワードから転倒数かな?というあたりがつく。
入力とリバース後の結果を比較することで、どの文字がどの場所にくるのが近いかで、結果となる配列をつくる。
(近いというか、リーバス後に左に来る文字は、入力でなるべく左にあった文字を使ったほうがスワップ回数が少なくなる)

f:id:bqn2:20201014141055p:plain
fig.1

icpcsguru と urugscpci を比較すると、
012345678 にたいして 678541230 が求めたい結果となる。
連想配列などを用いて、文字種ごとにインデックスを管理して、近い場所から割り当てればOK)

あとは入力と結果の転倒数が求める答え。