問題 "ABC?" の4文字のみからなる文字列sが与えられる この文字列が '?' をq個含むとき、それらの '?' を "ABC" のいずれかに置き換えることで3^q個の文字列が作られる それぞれの文字列に含まれるABC数の和を求める (ABC数: 文字列から3文字抜き取って左か…

問題 n個の都市とm本の列車があり、i本目の電車は区間[li, ri]を走っている 各クエリで[l,r]に「走る区間が完全に含まれる」ような列車の本数を出力するn 解法 区間[l,r]を走る列車について考える これを二次元平面上の (y座標,x座標) = (l,r) の点とみなす…

問題 一直線にN個の島がN-1本の橋で繋がっている 島a[i]とb[i]を行き来できなくしてほしい、という形の要望M個を全て叶えるために取り除く必要のある橋の本数の最小値を求める 解法 クエリをa[i]の降順に見ていき、取り除いた橋の中で一番左の橋の番号rを保…

ABC100まで 体感難易度(★)、問題概要、一言コメント 自分で辞書的に使うために作ったもの まだ解いてない問題の大まかな解法(累積和とかDPとか)を知りたくない人は見ないように