Codeforces Round #562 (Div. 2)

バチャ

ボロボロすぎた

やるだけ。

特別気を付けることもないかなって印象です。

サンプルみて問題もよくわかりました

問題：pairがm個ある。ある整数2つを選び、すべてのpairのどちらかにどちらかが含まれるx、yはあるか。

考察：

かなり苦戦しました。

ひらめきがないと厳しいんですかね。あんまり理論的に詰めることができませんでした。

着目する点としては、x、yの片方がカバーするpairの数は、どちらかがm/2個以上になります。

なので、m/2回以上出現する整数をxとします。これは最大でも4種類しかないです。

xを含まないpairのすべてに含まれる整数を求めればO(m)で解が求まります。

2つ要素があったら片方固定は典型でしたが、試すまでに時間がかかったりとよくなかったです。このくらいの問題は長くとも15分程度で通せたらうれしいなー。精進します。

問題：ｎ個の整数列がある。任意の個数選んで( ai+1)%mする操作が行える。最小回数で非減少にせよ

解説：

これわからなかったです。解説で通しました

ある操作回数に対して、非減少列になるかがO(n)でわかります。

また操作回数は最大でm回なので二分探索で解くことができます。

二分探索の各ステップの説明です。

操作回数分足したとき、1周するかしないかで、以前の最大値と一致するならそうします。

しないとき、もし以前の最大値より小さければダメです。

大きければ以前の最大値を更新してそのあとを見ます。

操作回数に対して一意に決まることに気づけなかったところが敗因ですね。

要素を1つずつ見てもわからなそうだったら、最大でどのくらいかとか、また別の視点で見るべきですね

Div1同時開催なので本番なら0完でした…

怖すぎます。というか実力なさすぎる。

DEも練習して通せるようにします。ただ解説読んだ感じかなり厳しそうでした。うーんつらいですね。