# AtCoder 練習その５

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

## 2021-12-24
### ABC217E - Sorting Queries (diff: 986 緑）

解けなかった。
[これ](https://atcoder.jp/contests/abc217/submissions/28096460) が TLE で、
[解説見て書いたやつ](https://atcoder.jp/contests/abc217/submissions/28096624)
が AC なの、ちょっと不思議だ。消却計算量（ならし計算量）というらしい。

## 2021-12-22
### ABC217D - Cutting Woods（diff: 802 緑）

平衡二分木…ああ、set かというので
[一応解いた](https://atcoder.jp/contests/abc217/submissions/28067025)
んだけど、set を二つ使うという、いかにも無駄な実装になってしまっていた。

そうか、一個前の要素を参照すればいいのか：
[28067089](https://atcoder.jp/contests/abc217/submissions/28067089)

## 2021-12-18
### ABC216D - Pair of Balls (diff: 1039 緑)

とけた：
[27965212](https://atcoder.jp/contests/abc216/submissions/27965212)

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

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

### ABC215E  - Chain Contestant (diff: 1413 水色）

とけた：
[27970363](https://atcoder.jp/contests/abc215/submissions/27970363)

## 2021-12-17
### ABC213E - Stronger Takahashi (diff: 1423 水色）

わかんなかった。

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

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

投稿したコード：
[27954157](https://atcoder.jp/contests/abc213/submissions/27954157)

## 2021-12-16
### ABC212E - Safety Journey (diff: 1410 水色)

dp だよねーと普通に書いてしまって [TLE](https://atcoder.jp/contests/abc212/submissions/27940412)。そんな簡単なわけないか。

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

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

投稿したコード： [27941606](https://atcoder.jp/contests/abc212/submissions/27941606)