問題 問題概要 自然数N,M と 数列 {a_i} (0 <= i < N) が与えられる. 各 j = 1, ... ,M について, jと互いに素なa_iの要素の数を求めよ. 1 <= N,M,a_i <= 105 解法 各jについて, 互いに素でない <-> 共通因数を持つ a_i の数を考えることにしよう. j = 5 の…

問題 問題概要 サイズNの数列からサイズKのsubarrayを選び,subarrayのminを取り除く試行をQ回行う. 取り除いたminのうちの max - min をminimizeするように試行を行った時のminを求めよ. 1 <= N <= 2000, 1 <= a_i <= 109 解法 思考箇条書き 単純に小さい順…

問題 問題概要 NM のハンコをハンコがマスに収まるような範囲の全ての場所でHW のマスに押す. ハンコで黒く塗られるのは何箇所か求めよ. 1 <= N,M <= 103 ,1 <= H,W <= 109 解法 まず for(ハンコを押した回数) for(ハンコの全てのマス)のループの順序を入れ…

問題 問題概要 昇順に並んでいる数列{x_i} (1<=i<=N) が与えられる. (i, j, k) , (i < j < k) の組で, x_j - x_i <= D x_k - x_j <= D x_k - x_i > D を満たす組の総数を求めよ. 3 <= N <= 105 解法 補集合を考える. x_j - x_i <= D, x_k - x_j <= D を満た…

問題 問題概要 ブロックに0,A,B,A+Bのいずれかの得点をつけることができる 合計Kの得点をつける塗り方をmod 998244353で求めよ. 1 <= N,A,B <= 3105, 0 <= K <= 181010 解法 単純にDPを立てると,状態がO(NK)とかになってしまうので間に合わない. ここで問題…