まずは条件を整理する。 インデックス があって（ ） 、 から までで条件が「2」のとき、長さ1に 両方を含むことはできないので明らかに0通り。 から までの条件が「1」で までの条件が「2」のとき までに2種類を含むので0通り。 以上から答えが「0」のとき…

。をの素因数の集合とする。 が答え。 とは互いに素なので両方が、の素因数の倍数であることはない。 またがの倍数なのでがの倍数の場合、もの倍数。 よってとは共にの倍数ではない。 以上からとにある数を足すことで両方をの倍数にできる。 のすべての素因…

にたいしてを最大値として採用できるように、かつをできるだけ小さくするを求めて、これらの最小値が答え。 どうやって計算するか。 2進数で考える。 より30桁考えれば良い。上の桁から決めていきたいので、以下では左から0,1,2..桁目と数えることとする。 …

グラフを作ってからメモ化再帰で答えをもとめる。 数字が大きいところにしか辺を貼れないので、グラフはDAGになる。 あるマスから行または列の、自分の次に数が大きいマス（複数ありうる）に辺を貼る。 「自分の次に数が大きいマス」にだけ辺を貼れば良い。…

kyopro_friendsさんの公式の解説の通り。 解説動画がくれば詳しく解説してくれそうだけど、実装に時間がかかったので残しておく。 dp[i][j] = i番目の試合でj番目の選手が勝ったときの、得られるポイントの最大値とする。 遷移はdp[i+1][j] = (i+1)番目の試…

スコアの計算式とxorの性質から幅は1か2だけ考えれば良い。 任意の範囲（幅=x）を0にするとき、一個ずつ消してx秒か、2個ずつ操作して残った一個を消して、x秒で出来る。 2個ずつ操作していって、最後の2つが同じ値のとき「幅-1」秒で0にできる。 2個ずつ操…

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番目の回文数のと…

言われてみればなるほど。 本番中は1を追加する場所を全部試すとMを追加する場所が高速に求まったりするのかな？という方向で考えてたけどちょっと外してた感。 まず、同じ値が並べばコストは0。 差が1ならコスト1なので、隣り合う値がaとbのときコストをb-a…

Codeforces Codeforces Round #779 (Div. 2) D1. 388535 (Easy Version) 2進数の桁毎（i桁目毎）に0,1の分布をみて、からまでとaに含まれる要素を比較する。 i桁目含まれる0,1の個数が異なるならxのi桁目を1にして、i桁目の0,1を逆にすればよい(A)。 問題は…

まず、の場所が最大値=Nなのは明らか。 また順列の並び替えなので最大値は常に1つで2つ以上存在しないので、の個数が1でないときは不適（条件1）。 PをローテートしたときはCもローテートされるので、を先頭にしておく。 いまでが確定している（以後決定した…

codeforces CodeTON Round 1 (Div. 1 + Div. 2) D. K-good codeforces.com 式変形した結果、偶数 × 奇数 になっていて、この条件を満たすようにするという問題はよくある気がする。 ポイントは、 0を使えないので1からKの和を使う。 余りの重複があってはい…

4時間くらい格闘してやっとACしたので 実行時間もメモリもカツカツ とくにメモリはMLEエラーを連発して、可能な箇所は64bit変数を32bit変数に変更して節約するなどした。 気づき xが変化する時、最小全域木の形が変わるポイントは少ない 最小全域木の形（使…