NOMURA プログラミングコンテスト2022（AtCoder Beginner Contest 253） F問題 Operations on a Matrix 状態が多くて脳が破壊された。 だいたいの情報は両端キューで管理して適宜pop_front()するとすこし楽になる。 まずタイプ1(l,r,x)のクエリによってj列目…

https://codeforces.com/contest/1674 E. Breaking the Wall 難しいのは隣り合う2つの壁を壊すパターンだと思うが、3分探索で提出したらACした。 正当性があるのかはすこし疑問があるが参考まで。 片方の2で割る回数を、整数の3分探索で調べて、合計手数のmi…

https://codeforces.com/contest/1668/problem/D 難しい。 公式解説のままです。 まず愚直なDPを考えるdp[i]=i番目まで決めた時のベストスコアとする。 このときAの累積和を求めておけば、j=0からi-1までためして、dp[i]= max(dp[j]+score(j,i)) となる。sco…

https://codeforces.com/contest/1673/problem/C 問題特有の考察はできたけどDPが解けなかった。 分割数って有名問題らしいけど難しい。 制約から40000以下の回文数はすくなそう（M種類）となって、dp[N][M] = 和がNのとき最後に使ったのがM番目の回文数のと…