ABC344｜ardririy

Dまで早かっただけにEで詰まって勿体ない...が、しっかり5完できていい感じ。

A - Spoiler

'|'を取り除いて出力だと勝手に思っていた。||の間かどうかをフラグで管理する。

Nが与えられないってどうやって入力読めば..？となったが、普通に一つずつ入力して0が来たらやめたらいい。

A+B+Cの計算結果としてあり得るのは高々100^3通りなので、事前計算しておく。クエリはsetなり二分探索なりでO(log(NML))で処理可能で十分高速です。

DはDPのD！dp[i] = Tのi文字目までを作成するまでの最小コストとすれば良いです。i = 1..=Nについて、それぞれの結果をすぐに反映すると一つの袋で複数個文字を使ってしまう場合があるので、一度違う配列に避けておく必要があります。

ある値に対して、その前の値が何であるかとその直後の値が何であるかを持っておけば、順列の情報を保持したまま削除/挿入のクエリに対してO(1)で処理が可能になる。これを実現するためにはmapを持ち出す必要があり、全体でO(Qlog(N))。