DivineJK’s diary

Z cjikf c evf'

ABC193E - Oversleepingの解説を書いてみます

コンテスト中に通せたので、自分の解法を書いてみます。

問題

概要

電車が X秒で一方の街からもう一方の街に移動し、街に着いたときに Y秒停車する。高橋君は P秒寝て Q秒起きるを繰り返す。高橋君は街 Bで降車することができるか？もし可能ならば、最短何秒で降車できるか？ Tケースについて求めよ。

制約

  • 1\le T\le 10
  • 1\le X\le 10^{9}
  • 1\le Y\le 500
  • 1\le P\le 10^{9}
  • 1\le Q\le 500

厳密な問題の定義はもとの問題文を読んでください。

E - Oversleeping

解法

状況整理

電車が街 Aを出発してから、戻ってきて次に街 Aを出発するまで 2X+2Y秒かかります。つまり、電車の運動は周期 2X+2Y秒の周期的な運動です。同様に、高橋君の睡眠に関する行動の周期は P+Q秒です。ところで、高橋君が街 Bで電車を降りるためには、

  1. 電車が街 Bに停車している間に高橋君が目を覚ます。
  2. 高橋君が起きている間に電車が街 Bに到着する。

のいずれかが成立していれば良いです。そして、このいずれかが成り立つ最小の時刻が求める答えとなります。

周期的な運動であることから、電車の運動の状態は、時刻を 2X+2Yで割った余りによって決まります。つまり、時刻を tとすると、 t = (2X+2Y)n+k\quad(n, k\in \mathbb{Z}, n\le 0, 0\le k\lt 2X+2Y)で表したときの kによって電車の状態が決まります。一方、高橋君についても同じように t = (P+Q)m+l\quad(m, l\in \mathbb{Z}, m\le 0, 0\le l\lt P+Q)の lによってのみ決まります。 tを消去して、 (2X+2Y)n+k = (P+Q)m+lの形にすることで、 n, mについての二元一次方程式が出来上がります。このそれぞれの時刻の表示を用いて、高橋君が街 Bで電車を降りる条件を定式化してみると、

  1. l = Pかつ X\le k\lt X+Y、つまり、方程式 (2X+2Y)n - (P+Q)m = P - k
  2. k = Xかつ P\le l\lt P+Q、つまり、方程式 (2X+2Y)n - (P+Q)m = l - X

となります。それぞれの条件において、固定されていない方の kおよび lのとりうる範囲は高々 500なので、全ての場合について方程式を解いてみれば良いです。

商とあまりの定義

整数 a, b(b \neq 0)について、整数 q, rを用いて、 a = bq + rと表します。 aを bで割ったあまりとは、 aをこのような形で表したときの rであって、 0\le r\lt |b|となるような唯一の整数のことをいうものとします。また、 aを bで割ったときの商とは、 rに aを bで割ったあまりをとったときの qのことを指すものとします。

以下に例を示します。

a b あまり 商
24 5 4 4
-24 5 1 -5
24 -5 4 -4
-24 -5 1 5
40 -8 0 -5
-13 26 13 -1
-17 17 0 -1
-11 -5 4 3

拡張ユークリッドの互除法

いきなり一般的な問題を解くのは難しいと思うので、具体例を考えます。 8n - 27m = 1という方程式を解いてみましょう。後で示しますが、 n, mの係数(ここでは 8, -27)の最大公約数が右辺の約数であるとき、またその時に限り、この形の方程式は整数解を持ちます。よって、この具体例では整数解が存在します。

2つの変数に対して方程式が1つなので、整数解は無数に存在します。たとえば、 n = 17, m = 5は解のひとつです。他にも n = -10, m = -3も解のひとつです。このような解のひとつを機械的に求めるために、ユークリッドの互除法を使います。以下のように進んでいきます。

  1. 8 = -27\times 0 + 8
  2. -27 = 8\times (-4) + 5
  3. 8 = 5\times 1 + 3
  4. 5 = 3\times 1 + 2
  5. 3 = 2\times 1 + 1
  6. 2 = 1\times 2 + 0
  7. あまりが 0になったので終了。

よって、最大公約数が 1であることが求まりますが、これらの各式を a = bq + rの形でみたときに、 a, bがどのように変化するかを行列表示で見てみたいと思います。

行列表示を知らない方もいると思うので必要なことだけ簡単に説明すると、行列とは要素を矩形に並べたもので、行列同士の積として

 \begin{pmatrix}a & b \\\ c & d\end{pmatrix} \begin{pmatrix}u \\\ v\end{pmatrix} = \begin{pmatrix}au + bv \\\ cu + dv\end{pmatrix}
 \begin{pmatrix}a & b \\\ c & d\end{pmatrix} \begin{pmatrix}p & q \\\ r & s\end{pmatrix} = \begin{pmatrix}ap + br & aq + bs \\\ cp + dr & cq + ds\end{pmatrix}

がなりたちます。また、2つの行列が等しいとは、両方の行列のサイズが等しく、かつ同じ場所にある要素が等しいことを意味します。

a _ 0 = 8, b _ 0 = -27として、 n + 1番目の式を a _ {n} = b _ {n}q _ {n} + r _ {n}と表します。ユークリッドの互除法のアルゴリズムのもっとも重要な事実として、 a _ {n}と b _ {n}の最大公約数は b _ {n}と r _ {n}と等しい、というものがあります。よって、 a _ {n+1} = b _ {n}, b _ {n+1} = r _ {n} = a _ {n} - b _ {n}q _ {n}です。このことを行列表示すると

 \begin{pmatrix}a _ {n+1} \\\ b _ {n+1}\end{pmatrix} = \begin{pmatrix}0 & 1 \\\ 1 & -q _ {n}\end{pmatrix} \begin{pmatrix}a _ {n} \\\ b _ {n}\end{pmatrix}

となります。これは

 \begin{pmatrix}a _ {n} \\\ b _ {n}\end{pmatrix} = \begin{pmatrix}0 & 1 \\\ 1 & -q _ {n-1}\end{pmatrix}\begin{pmatrix}0 & 1 \\\ 1 & -q _ {n-2}\end{pmatrix} \cdots \begin{pmatrix}0 & 1 \\\ 1 & -q _ {0}\end{pmatrix}\begin{pmatrix}8 \\\ -27\end{pmatrix}

のように書けるので、

 \begin{pmatrix} x _ {n} & y _ {n} \\\ u _ {n} & v _ {n}\end{pmatrix} = \begin{pmatrix}0 & 1 \\\ 1 & -q _ {n-1}\end{pmatrix}\begin{pmatrix}0 & 1 \\\ 1 & -q _ {n-2}\end{pmatrix} \cdots \begin{pmatrix}0 & 1 \\\ 1 & -q _ {0}\end{pmatrix}

とおきます。すると、

 \begin{pmatrix} x _ {n+1} & y _ {n+1} \\\ u _ {n+1} & v _ {n+1}\end{pmatrix} = \begin{pmatrix}0 & 1 \\\ 1 & -q _ {n}\end{pmatrix}\begin{pmatrix} x _ {n} & y _ {n} \\\ u _ {n} & v _ {n}\end{pmatrix} = \begin{pmatrix} u _ {n} & v _ {n} \\\ x _ {n} - q _ {n}u _ {n} & y _ {n} - q _ {n}v _ {n}\end{pmatrix}

となります。この行列を求めることや計算していくことは、漸化式にしたがってその都度一つずつ順番に行えます。そして、初期値によらず最終的には b _ {n}が 0、 a _ {n}が a _ 0, b _ 0の最大公約数になって終了するので、

 \begin{pmatrix}1 \\\ 0\end{pmatrix} = \begin{pmatrix}x _ {f} & y _ {f} \\\ u _ {f} & v _ {f}\end{pmatrix}\begin{pmatrix}8 \\\ -27\end{pmatrix}

となります。これの上側の要素を比較すると 8x _ {f} - 27 y _ {f} = 1という式を得ます。この x _ {f}, y _ {f}は元の方程式 8n - 27m = 1の解になっています。具体的には、

 \begin{pmatrix} x _ {f} & y _ {f} \\\ u _ {f} & v _ {f}\end{pmatrix} = \begin{pmatrix}0 & 1 \\\ 1 & -2\end{pmatrix}\begin{pmatrix}0 & 1 \\\ 1 & -1\end{pmatrix}\begin{pmatrix}0 & 1 \\\ 1 & -1\end{pmatrix}\begin{pmatrix}0 & 1 \\\ 1 & -1\end{pmatrix}\begin{pmatrix}0 & 1 \\\ 1 & 4\end{pmatrix}\begin{pmatrix}0 & 1 \\\ 1 & 0\end{pmatrix} = \begin{pmatrix} -10 & -3 \\\ 27 & 8 \end{pmatrix}

であるので、解 n = -10, m = -3が見つかりました。この解を利用することで、 8n - 27m = 2の解はこれを2倍した n = -20, m = -6がみつかることもわかります。

また、 a _ 0, b _ 0を a _ {f}, 0に変えるまでの最悪計算量は、 a _ 0, b _ 0がフィボナッチ数列の隣り合う項のときなので \mathrm{O}(\log \max(a _ 0, b _ 0))です。

さらに、 n = -10 + 27u, m = -3 + 8u(u \in \mathbb{Z})も方程式 8n - 27m = 1を満たすことがわかると思います。このことは一般に、 an + bm = cに整数解が存在するなら、 nが 0以上 |b|未満になるように解を決めることが可能であることが言えます。そのように実装しておくと、解が存在しないときに -1, -1を返すことで判定できるので便利です。

改めて、方程式 ax + by = cの整数解を求める手順をまとめてみます。ここで、 k/lを kを lで割った商、 k \% lを kを lで割ったあまりとします。

  1. x = 1, y = 0, u = 0, v = 1, k = a, l = bとする。
  2. lが 0ならば手順4. へ。そうでなければ手順3. へ。
  3. x = u, y = v, u = x - u \times (k / l), v = y - v \times (k / l), k = l, l = k\% lとする。手順2. にもどる。
  4. この時点で kは aと bの最大公約数になっている。もし cが kで割り切れなければ、 (x, y) = (-1, -1)を返し終了。
  5. a = a / k, b = b / k, c = c / kとする。
  6. x, yを c倍する。
  7. (x + ub, y - ua)も方程式の解としてとれる。 u = \lfloor \dfrac{b - x - 1}{b}\rfloorとすると、 0\le x + ub\lt |b|となる。
  8. (x + ub, y - ua)を返して終了。

本題

拡張ユークリッドの互除法で条件1. と条件2. を満たす n, mを求めます。ただし、解が存在するならばどちらも 0以上でなくてはならないので、その条件も確かめる必要があります。 nは自動的にこの条件を満たします。 mが負になってしまう可能性があるように思えますが、それは起こらないことが示せます。

0\le n \lt P+Qであったとすると、式変形により、条件1. では \lfloor \dfrac{Q-1 + k}{P+Q}\rfloor \le m \le a + \lfloor \dfrac{Q-1 + k}{P+Q}\rfloor、条件2. では \lfloor \dfrac{P + Q + X - l -1}{P+Q}\rfloor \le m \le a + \lfloor \dfrac{P + Q + X - l -1}{P+Q}\rfloorですが、 1\le Q + X - 1\le Q - 1 + k \lt Q + X + Y - 1、 0 \le X - 1\lt P + Q + X - l - 1\le Q + X - 1であるので、自動的に mが 0以上になることがわかります。

さらに、以上の方法で求めた nは最小の非負整数解であるので、これで欲しいものは求まりました。あとは、解が存在するような (2X+2Y)n + kのもとでの最小値を求めれば良いです。

全体的な計算量は \mathrm{O}((P+Q)\log (\max(P+Q, 2(X+Y))))です。

コンテスト中のACコード

atcoder.jp

余談

解が存在しないときの出力が'infinity'になっていることに気をつけましょう。僕はそれで2ペナ食らいました。