AGC017 B Moderate Differences

beta.atcoder.jp

所見

数学

問題概要

N個のマスがあり、左端にA、右端にBが書かれている。隣り合うマスの数の差がC以上D以下になるようにN個のマスを埋めることができるかを答えよ。

取った方針

2つの隣り合うマスの差の列をY_iと置くとY_iの総和がB-Aになればよい。よって、絶対値C以上D以下の数をN-1個使ってB-Aを作ろうとするができず死亡。

正しい方針

2つの隣り合うマスの差の列に着目するところまでは合っていて、-D<=Y_i<=-C もしくは C<=Y_i<=Dを満たすことに着目する。
Y_iはN-1個の数列なので、前者を満たす数がm個あったとすると、後者はN-1-m個あることになる。
よってY_iの総和がB-Aであることより、-Dm + C(N-1-m) <= B-A <= -Cm + D(N-1-m) を満たすmが存在すれば条件を満たすことができる。
m<=10⁵なのでmについて全探索すれば時間内に答えが出る。

得られた知見

• 一度条件を全部数式にすると見えることがある
• 全探索できそうな制約のものを変数にして式を立てる->全探索

解くのに必要な要素

• 不等式の和を取るアレ
• 差の和に注目する

周辺調査によって得られた知見

特になし