AtCoder 練習その5

年末・年始を使って、ABC が8問構成になって以降の D, E, F で緑以上青以下のものをやって行こう!おー!

2021-12-24 (Fri)

ABC217E - Sorting Queries (diff: 986 緑)

解けなかった。 これ が TLE で、 解説見て書いたやつ が AC なの、ちょっと不思議だ。消却計算量(ならし計算量)というらしい。

2021-12-22 (Wed)

ABC217D - Cutting Woods(diff: 802 緑)

平衡二分木…ああ、set かというので 一応解いた んだけど、set を二つ使うという、いかにも無駄な実装になってしまっていた。

そうか、一個前の要素を参照すればいいのか: 28067089

2021-12-18 (Sat)

ABC216D - Pair of Balls (diff: 1039 緑)

とけた: 27965212

ペアを検出するための工夫と、 M 本の筒を全部毎回走査するのは無駄なので、まだ先頭の色を確認してない筒番号の que を用意するなどして確認回数を ボールの個数 2N 回に抑える。

思いついた通りでよかったんだけど、 ペアを検出するための vector サイズを N にしたのに、\(a_i\) から 1 引くの忘れててバグって手こずってしまった。

ABC215E - Chain Contestant (diff: 1413 水色)

とけた: 27970363

2021-12-17 (Fri)

ABC213E - Stronger Takahashi (diff: 1423 水色)

わかんなかった。

解説をみると一行目に「この問題は*****で解くことができます。」とあって、 それを見たらとけた、という類の問題。(なので伏せ字にしました)

*****を二回ほど使ったことがあったけど、まだモノにできてなかったという感じかな。

投稿したコード: 27954157

2021-12-16 (Thu)

ABC212E - Safety Journey (diff: 1410 水色)

dp だよねーと普通に書いてしまって TLE。そんな簡単なわけないか。

普通にやると繰り返しの回数が K * N * N なわけだけど、N*N の全結合経路のうち、 通れないパスの個数は 2M + N しかないので、これに気づけば K * (2M + N) になる。

ちゃんとした説明は「解説」を参照。

投稿したコード: 27941606