Codeforces Round #621 + 622 参加記録
1日に２つあると大変ですね。疲れました。
# 621 (div2)はA, B, C1の３つ解けたつもりがC1がシステムテストで落ちました。 一行間違えて消していて直すと通りました（泣） ちゃんと確認しましょう！
#622 (div2)はA, B, C, Dまで解けたつもりですが現在システムテストの途中なのでわかりません。 DなどはTLEが怖いですね。
621-A Fast Food Restaurant
いきなり難しくてNo Subを考えましたが15分かけてACです。 a, b, cそれぞれ４以上なら同じなのでsortしてから手で全探索しました。もっと効率的な解き方がありそうです。。
621-B Different Rules
難しかったです。順位をよくする方は順位の和がa+b+1となる人をたくさん作る感じにしました。 悪くする方は順位の和がa+bちょうどになる人を増やします。下みたいな感じになりましたが自信ありません。（通ったけど）
print(max(a+b-n+1, 1), min(a-1, n-b)+min(b-1, n-a)+1+(a-1-(n-b) if n-b < a-1 else 0))
621-C1 Skyscrapers (easy version)
A, Bよりも簡単でした。（でも落ちた...）最も高くなる点を全探索します。１つ点を最も高い点として固定してそこから貪欲に左右に低くしていけばいいです。
621-C2 Skyscrapers (hard version)
ずっと考えてたけど解けませんでした。 最長増加列の話などと似ているのでsegtreeを使うのかなあとか、全てのビルをX以下にするとしてXを2分探索かなあとか考えていました。
終了後、以下のtweetをもとにACしました。
左右から累積和でみていって、例えば左から見るときは、1個前よりちいさければそれ以前を更新していく形で解けます。(愚直にやるとO(N^2)かかるのですが、stackを使うことでO(N)でできます)https://t.co/jnHNcXTL9d
— じゅぴろ (@jupijupi111) 2020年2月23日
すごいですね。O(N)だし。
beatとかいうデータ構造を使ってもACできるし、セグ木+2分探索でも解けるようです。（方法はわからない）
622-A Dead Pixel
簡単ですね。ただ英単語力的に苦戦しました。
622-B Home Coming
これも簡単でした。後ろからシミュレーションするだけです。621のABとはえらい違いです。
623-C Restoring Permutation
一応、証明っぽいものができたと思っていますが自信ないです。 １〜２Nの大きい方から見ていって、biに含まれる数 <= 含まれない数と常になっていれば構成可能で、ないなら-1です。 あとは貪欲に詰めていけばいいです。
624-D Recommendations
解法はすぐ思いついたのですがセグ木使うだけでも苦手なので時間がかかりました。 セグ木の用途はmaxを常にpopできるような集合を使いたいからです。 今回は重複ありだったので時間がかかりました。少し前のABCでも同じ苦戦をしているので早めに纏めておきたいです。 確かC++だとライブラリがあるのでこんなところで30分以上かけているのはとても不利になってしまいます。 その上、セグ木でこれを代用するのは遅いのでTLEが怖いですね。
具体的な解法は後で追記します。（眠いので）
624-E Double Elimination
泥臭くやればできる可能性もありそうだと思いながら、途中で心折れました。 見るからに実装が大変です。セグ木の実装とかで2分木の扱いになれればできるかな...
