B - First Contest of the Year 解説 by seekworser

公式解説の実装例2の解説

公式解説の2つ目の実装例7行目に cout << 7 - ((d - f) % 7) << '\n'; という行がありますが、この行で何を行っているかの解説です。以下では合同式(剰余)についての知識を仮定します。

求める答えを \(x\) として、\(f \equiv x + d \pmod 7\) が成り立ちます。したがって、この問題は \(x \equiv f - d \pmod 7\) となるような \(x \quad (1 \le x \le 7)\) を求める問題と言い換えることができます。

\(7-x = y\) とすると、\(y \equiv d - f \pmod 7\) で、\(0 \le y \lt 7\)です。このような \(y\) は剰余演算を用いて (d - f) % 7 と計算することができます。(制約から、必ず \((d-f) \gt 0\) となることに注意してください。)\(7 - x = y\) を変形し、\(x = 7 - y\)であるため、結局 \(x\)7 - ((d - f) % 7) により求まることがわかります。

投稿日時:
最終更新: