AtCoder Begineer Contest 141 に参加。

3完、3ペナ

A - Weather Prediction

3分ぐらいで解けた。

先頭の文字だけで区別すればOK

B - Tap Dance

7分ぐらい。

RとLの違いだけを気にすれば良い。

10分ぐらい。

Nが10の5乗なので、単純にループでまわしても解ける。

一応Pypyで実行してAC。

この問題で残り時間をほとんど溶かした。

方針と実装はそれぞれできたが、NとMがそれぞれ10の5乗なので、O(NM)の計算量になると制限時間オーバーになる。

回避方法が分からなかったが、優先度付きQueueを使えばO（M log N) となり解けた。

Pythonだとheapq

最小を最大に入れ替えるために-をつけるのはよくやる方法。

解き方が分からず、力任せにやったら案の定TLE

Z-Algorithm なるものを使うらしい。

知ってないと解けない問題ぽかったなぁ。

到達できず

D問題で計算量を減らす方法を探しているうちにタイムオーバー E問題もアルゴリズムを知っていれば解けた問題やはり基本問題もっと沢山解く必要があることがわかった回だった。