Educational Codeforces Round 150 (Rated for Div. 2)

　Dまで四完。

コンテストへのリンク

コンテスト後のツイート

Educational Codeforces Round 150 (Rated for Div. 2) Dまで
A 5以上なら「1 1 ?」にすれば勝てる
B シミュレーション。Aより簡単。
C ある文字の最左・最右を変えてみる
D 貪欲。(l,r)をrでソートし、そこまででペアを作れるか。作れたら、rより左に左端があるものは捨てる。

— titia (@titia_til) June 12, 2023

E. Fill the Matrix

　横に何マス繋がっているか？　が何個ずつあるかを分かれば良い。

　それは最大長方形のアルゴリズムを使えば解ける……という情報を得てAC。

　スタックを利用して最大長方形の面積を求めるアルゴリズムが頭に入っていなかったのが一番の問題だった。実際、「最大長方形」という文字を見てもピンと来ず、検索してどういうアルゴリズムだったかを思い出したら解法が分かった。

　典型アルゴリズムを頭に入れておくのが大事。