Codeforces Round #559 (Div. 2)

バチャ

問題：ある個数の石ｘから初めて与えられた操作をする。最小値が0以上のとき、最後に残る石の数を最小化するｘを求めよ

考察：

Aにしてはちょっと厄介でした。

全体での最小値を0とすることが最適なので、x=0とか適当にして、最後の値-最小値とすればよいです。

問題：k|i-j|<=min(ai,aj)を任意のi,jで満たすような最大のkを求めよ

考察：

任意のaiでk|i-j|<=aiとしてよいです。

またこの式で一番厳しいものは、j=0,n-1のどちらかなのでどちらも試します。

これをすべてのaiで求めて最小のkを出せばよいです。

minを外していい理由ですが、もしai>ajならajを調べるときに抑えられています。

問題：ｎ人の男子とｍ人の女子がいて、男子が女子全員にお菓子を送る。

ｉ番目の男があげた菓子の数の最小値がai

ｊ番目の女が受け取った菓子の数の最大値がbjになった。

送られた菓子の和の最小値を求めよ

考察：

まずa,bをソートします。

そのとき、a[n-1]>b[0]のとき、実現不可能です。

a<=bのとき、ある女子に余分に菓子を送る男子がいることがわかります。

これはaiが大きい男子が余分に送ることが最適なので、a[n-1]から余分に見ます。

a[n-1]<b[0]のとき、m人に余分に上げると最小値a[n-1]が実現できません

なので、m-1人に余分に送り、もう1人にはa[n-2]さんが余分に送ります。

受け取りてのbさんはだれでも変わらないことは、式を書けば簡単にわかります。

以上のことを愚直に実装しますが、n=1やm=1のときに気を付けましょう

問題：長さｎの01の文字列を構築せよ。ある文字列tを部分文字列として登場する回数が1になる。を満たすｔの最小の長さがkになるようにせよ。ただしn%2==k%2

考察：

ｎが奇数のときは01010をk+2個分繰り返した後0をつければよいです。

n=kのときはすべて0にすればよいです

ｎが偶数のときが構築できませんでした。

問題：ある順列ｐを復元せよ。ai：i番目より右側にあって、piより小さい値が出現する最小のindex。が与えられる。

考察：

iより大きくai未満のindexはpiより小さいです。またpaiはpiより大きいです。

この区間がズレて重なる場合実現不可能です。

そうでない場合は適切に辺を張ることでトポロジカルソートで求めることができます。

バグりました。

※通したので追記

後ろから決めないとバグります。setなどを使いましょう

辺を張るときにすべてに張るとN^2本の辺になり間に合わないので、隣接するものに張りました。このとき、少し離れている頂点対に張られておらず、前からでも後ろからでも同じ優先度になります。

しかし、繰り返すようですが後ろから前に辺があるので、後ろから決めなければいけませんでした。