Educational Codeforces Round 46 - プロコン参加記

Codeforces初参加です。B問題の実装に手間取り結局バグを取り除けず1完。

Rate:0→1484

A問題

前年度のTシャツのサイズと今年度のTシャツのサイズで異なるものの数を調べれば良い。英語を読むのに時間がかかって10分程度でAC。

B問題

ライトのオンオフが切り替わる1秒前か1秒後に新たなコマンドを入力することになるので、全ての切り替わるポイントについて調べる。切り替わるポイントが10^5程度あるので、コマンドを挿入した結果ライトがついている時間の長さを累積和を使ってO(1)で計算できるようにしておく。

（コンテスト終了後にデバッグしようと思ったけど面倒で放置している)

C問題

座圧、というものを使うらしい。大きな数を扱うとき小さいものから順に番号をつけいくことで小さい数に変換してから考える方法。ABC036のC問題から来てるっぽい。

この問題は座圧してl,rの値を小さな値に変換した後、範囲内の個数をカウントしていけばよい、と思う。範囲内の個数を更新する際、n行の入力に対しl[i]-r[i]+1個の値を更新していく方法しか思いつかず、これは最悪がO(n^2)で10^10になってしまうのでTLEして終わった。