ganmo::cout

競技プログラミング始めました

AtCoder Grand Contest 040

念願の初橙パフォ!
atcoder.jp

A - ><

atcoder.jp
ランレングス圧縮をして「Λ」(「/」「\」)の形を作っていく。

f:id:aprilganmo:20191104224342p:plain
S = ">>>><<<>><<>>"の場合の例
左端の「\」と「/」の形に気を付けつつ「Λ」の形の和を計算して足していけば求められて、O(N)で間に合う。
拙解 (C++14): Submission #8273736 - AtCoder Grand Contest 040

B - Two Contests

atcoder.jp
L_iでソートしたときに上から1, 2, \cdots, N-1個を1回目のコンテストにした場合の楽しさと、問題iだけを1回目のコンテストにした場合の楽しさをセグ木を使って計算して一番大きかったやつを出力すると、O(N\log N)ACなんで?
嘘解法2つで無理やり通したと思ったけどEditorial見たら結果的に想定解法でした
拙解 (C++14): Submission #8275594 - AtCoder Grand Contest 040