年末・年始を使って、ABC が8問構成になって以降の D, E, F で緑以上青以下のものをやって行こう!おー!
平衡二分木…ああ、set かというので 一応解いた んだけど、set を二つ使うという、いかにも無駄な実装になってしまっていた。
そうか、一個前の要素を参照すればいいのか: 28067089
とけた: 27965212
ペアを検出するための工夫と、 M 本の筒を全部毎回走査するのは無駄なので、まだ先頭の色を確認してない筒番号の que を用意するなどして確認回数を ボールの個数 2N 回に抑える。
思いついた通りでよかったんだけど、 ペアを検出するための vector サイズを N にしたのに、\(a_i\) から 1 引くの忘れててバグって手こずってしまった。
とけた: 27970363
わかんなかった。
解説をみると一行目に「この問題は*****で解くことができます。」とあって、 それを見たらとけた、という類の問題。(なので伏せ字にしました)
*****を二回ほど使ったことがあったけど、まだモノにできてなかったという感じかな。
投稿したコード: 27954157
dp だよねーと普通に書いてしまって TLE。そんな簡単なわけないか。
普通にやると繰り返しの回数が K * N * N なわけだけど、N*N の全結合経路のうち、 通れないパスの個数は 2M + N しかないので、これに気づけば K * (2M + N) になる。
ちゃんとした説明は「解説」を参照。
投稿したコード: 27941606