Codeforces Round #501 (Div. 3)D. Walking Between Houses

問題概要

$1$ から $n$ の数直線上の整数の点どうしを移動し, ちょうど $k$ 回の移動で総移動距離を $s$ にしたい. これは可能か？可能なら構成例を示せ. ただし, 一回の移動では必ず $1$ 以上移動しなければならない.

問題へのリンク

制約

$2 \le n \le 10^9$
$1 \le k \le 2\times 10^5$
$1 \le s \le 10^{18}$

解説

こういう問題が好きな人, この世にいるんですか？僕は普通に嫌いです.

構築系では, まずできない場合はどんな場合かを考えましょう. 移動距離の上限は $n-1$ ですから, $k$ 回の移動では $(n-1)k$ の距離までしか移動できません. $s$ がこれを上回っていた場合は構築できません.

また同様に一回の移動距離の下限は $1$ ですから, $k$ 回の移動では少なくとも $k$ だけ移動します. $s$ がこれを下回る場合には構築できません.

逆に, 上記を満たしている場合には必ず構築できます. 基本的には, $n-1$ 移動したとしても残り移動距離が残り移動回数よりも多い間は $1$ と $n$ を往復し, いい感じに残り移動回数が残り移動距離と等しくなるように調整した後 $1$ の移動を繰り返せばよいです. 詳しくは実装を見てください.

実装

Submission #145953182 - Codeforces