Codeforces Round 860 (Div. 2)

　Dまで四完だったが、Cがシステムテストで落ちた。二分探索の上限をミスっていた。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round 860 (Div. 2) Dまで
A A[i]<=B[i]に並べて判定。
B Counterを使う。
C 貪欲に進む。進める条件は、(a*bたちのgcd)%(bたちのlcm)==0。二分探索したが、必要なかった気がする。
D 正負に分け、絶対値が大きい順にsortし、正のときは負の数を負のときは正の数を並べたら通った（未証明）

— titia (@titia_til) March 26, 2023

E. Multitest Generator

　解法ツイートを参考にAC。

・答えは高々２である

・0にできるかは、後ろからDPをすれば求められる

・1にできるかは、以下の二つで場合分け

  - A[i]自身を変更する：DP配列の後ろからmaxを取っておけば分かる。

  - 他の数字を変更する：DP2として、後ろからindex i までで一回だけ数字を変更したとき、最大で何個のtestに分けられるか？　を求めれば、それを使って答えが求められる。

　整理して考えればそんなに難しくないが、整理するのが難しい。