ABC344

ardririy
·

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

A - Spoiler

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

https://atcoder.jp/contests/abc344/submissions/51024692

B - Delimiter

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

https://atcoder.jp/contests/abc344/submissions/51028699

C - A+B+C

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

https://atcoder.jp/contests/abc344/submissions/51035788

D - Strings Bags

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

https://atcoder.jp/contests/abc344/submissions/51054693

E - Insert or Erase

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

https://atcoder.jp/contests/abc344/submissions/51089028