ABC 432 C 問題の解き方と説明

導入

AtCoder ABC 432 の C 問題と公式解説の難易度が高めだったので、私なりの解法とその説明を書き残したいと思います。

問題

全文：ABC 432 C - Candy Tribulation

問題文を読み解くと、$N$ 個の等差数列の共通部分とその最大値を求める問題に帰着できます。

方針

まず子供 $i$ に小さな飴を配り、そこから1個ずつ大きな飴に交換することを考えます。
飴を交換するごとに重量が $d = Y - X$ 個ずつ増加することに着目すると、
子供 $i$ が持つ飴の総重量は次の等差数列 $S_i$ で表せることがわかります。

$$S_i = \left\{ X A_i + k d \;\middle\vert\; 0 \le k \le A_i \right\}$$

ここで $d$ を共通の公差、$S_i$ の初項を $L_i = X A_i$ 、末項を $R_i = Y A_i$ と定義します。
すべての $S_i$ に共通部分 $G$ が存在すれば、これが条件を満たせる飴の総重量の集合です。
考察を進めると、以下の2つの条件が満たされれば共通部分が存在することがわかります。

図 1: 各子供の飴の重量 $S_1, S_2$ とその共通部分 $G$

• 区間条件：すべての $S_i$ の区間 $[L_i, R_i]$ が重なっていること
• 剰余条件：すべての $S_i$ の初項 $L_i$ が $\mod d$ において同値であること

実装

def solve1(n, x, y, a):
    g_l = max(a) * x
    g_r = min(a) * y

    # 区間条件を満たすか
    if g_r < g_l:
        return -1

    d = y - x
    # 共通部分が存在すれば、その最大値 g_r を選べば大きな飴の個数を最大化できる
    g = g_r

    ans = 0
    for a_i in a:
        # 剰余条件を満たすか
        if (g - x * a_i) % d != 0:
            return -1
        ans += (g - x * a_i) // d

    return ans

詳しい証明

共通部分の形

共通部分が存在する場合、その数列は「$d$ ごとに並ぶ点の集合の共通部分」なのでこれ自身もまた等差数列となります。
これを以下のように $G$ と定義します。

$$G = \left\{ g = G_l + k d \;\middle\vert\; G_l \le g \le G_r,\ 0 \le k \right\}$$

ただし $G$ の初項を $G_l$、末項を $G_r$ で表しています。

区間条件

すべての区間が重なっている部分が集合 $G$ の区間になります。
全区間のうち最大の左端 $\max(L_i)$ と最小の右端 $\min(R_i)$ を求めれば、それぞれが区間の端だとわかります。

$$\max(L_i) \le \min(R_i) \iff G_l \le G_r$$

剰余条件

共通部分 $G$ が存在するためには、等差数列 $S_i$ の初項 $L_i$ が $\mod d$ において同値であることが必要です。
例えば「歩幅が同じ人々が、スタート地点に歩幅未満のズレがある状態で歩き始める」という状況を考えます。
この人々はどれだけ歩いても互いの足跡を踏むことがありません。互いの足跡を踏めるのはスタート地点の差がちょうど歩幅の倍数であるときのみです。

図 2: 剰余条件が満たされない（スタート地点の差が $d$ の倍数でない）場合、共通部分が存在しない

この条件（剰余条件）は以下の式で表せます。

$$L_i \equiv g \pmod d \iff (g - L_i) \bmod d = 0$$

大きな飴の数の最大化

問題では大きな飴を渡せる個数の最大値が求められています。
各子供に渡す大きな飴の数を $t_i$ とすると、これは $g = G_r$ として次の式で計算できます。

$$G_r = L_i + t_i d \iff t_i = (G_r - L_i) / d$$

上述したコードにおいては、剰余条件の確認と $t_i$ の総和の計算を同時に行っています。

まとめ

導入でも述べたように「等差数列の共通部分を求める」という問いに帰着できれば単純な問題なのですが、
問題文からこれを読み解くのが難しく、理屈が単純ゆえに数式による証明も難しくなりがちな問題でした。
公式解説やけんちょんさんによる解説もありますので、本記事も問題を読み解く一助になれば幸いです。