Codeforces Round #568 (Div. 2)

codeforces.com

上の回をやりました。

A~C2までの3完でした。終了後にDとEを解きました。

A. Ropewalkers

ソートしてmax(0,d-a[1]+a[0])+max(0,d-a[2]+a[1])

B. Email from Polycarp

それぞれをランレングス圧縮をして、圧縮後の長さが同じかつ、全てのindexについて（同じ圧縮後のsとtが同じ文字∧sの長さ<tの長さ）を満たしていればYES、そうでなければNOを出力。

C1, 2. Exam in BerSU

C2の解法を書きます。

$i$ 人目まで見た時、 $i-1$ 番目以下の全員が問題を解くのにかかった時間の総和を $sum$ とします。また、 $1\sim 100$ のそれぞれについて $t[i]$ として何度登場したかを $memo$ に記録しておきます。

$t[i]+sum\leq m$ のとき

$0$ を出力。

$t[i]+sum\gt m$ のとき

$100$ から降順に

$sum+t[i]-memo[num]\leq m$ となるかを調べます。

$false$ のとき

$sum-=memo[num],\ res+=memo[num]$ として $num$ を1つ小さくします。

$true$ のとき

二分探索をして何人消せばいいのかを求めます。

計算量は $O(N\times 100\times \log(N))$ です。

D. Extra Element

バチャ中は無限場合分け編をしてずっと詰まってACできませんでした。

解説の方針がスッキリしていてわかりやすかったです。

ソート後の配列をbとすると、b[2]-b[0]が他全部と一致するか調べたあとは全部の差分がb[1]-b[0]と一致するかを調べて
全部一致->最後のを消す
ひとつだけ一致しないかつ、次のと合わせると一致する->間のindexを出力
それ以外->cout<<-1<<endl;
— やまけー (@yamake_cpp) 2020年12月3日

上のツイートに、b[2]-b[1]が他全部と一致する->b[0]を消して終わり。を加えて終わりです。

E. Polycarp and Snakes

問題を読んだ瞬間に「これ情報オリンピック過去問でやったやつだ！！」となりましたが、よく読むと結構違いました。似てる奴

似てる奴のコードをコピペしてちまちま直してたけど、結構違ったので結局新しく書きました。

パット見トポソして構築なんですが、よく見るとaから順番に書いていくとあるので、素直にaから順番に書いていくだけで良いです。

具体的にはそれぞれの文字について、登場した座標の上下左右について端っこのものを記録します。

2 2

のaのように登場していない文字については適当な登場した文字と全く同じ上下左右端を持たせて大丈夫です。

新しい紙を用意して

それぞれの文字について $up\neq down \cap left \neq right$ となる文字があればNOを出して終了、そうでなければ $(up,\ left)$ を左上に $(down,\ right)$ を右下に持つ長方形領域にその文字を記入していきます(最初の条件の否定よりこの長方形は幅もしくは高さが1になる。)。