AOJ 1338 Clock Hands

解法

まず,それぞれの針がなす角を求めましょう.短針が1周するのに$H$時間かかるとします.
今時刻が $h:m:s$ である時,針が上を向いている状態を 0 度とすると,長針,短針,秒針はそれぞれ
$\displaystyle ang_h = \frac{360}{H} \times h + \frac{6}{H} \times m + \frac{s}{10H}$
$\displaystyle ang_m = 6m + \frac{s}{10}$
$ang_s = 6s$
の角度にあります.
簡単にするために,$ang_h = 0$ となるように時計を回転させます.
$ang_h = 0$
$\displaystyle ang_m = 6m + \frac{s}{10} - \left(\frac{360}{H} \times h + \frac{6}{H} \times m + \frac{s}{10H}\right)$
$\displaystyle ang_s = 6s- \left(\frac{360}{H} \times h + \frac{6}{H} \times m + \frac{s}{10H}\right)$
これらの値が負になっていれば,360 を加えて辻褄を合わせます.

秒針と長針の位置関係は二通りありますが,とりあえず $ang_s < ang_m $の場合を考えましょう.
このとき,秒針との短針および長針の間の角はそれぞれ
$\displaystyle ang_s - ang_h = 6s- \left(\frac{360}{H} \times h + \frac{6}{H} \times m + \frac{s}{10H}\right)$
$\displaystyle ang_m - ang_s = 6m - \frac{59s}{10}$
これらが仮に等しいとして等式を立て,式を整理すると,
$\displaystyle s = \frac{n}{d} = \frac{60m(H + 1) + 3600h}{119H - 1}$
が成り立ちます.秒針と長針の位置関係が異なる場合も,似た式になります.

つまり,目的の時刻において,$d$ は $119H - 1$ の約数であるということが分かります.
ここから,$d = 119H - 1$ とおいてしまって,その上で n を少しずつ増やしていく全探索が考えられます.実際,秒針は高々2周程度する間に,目的の時刻は必ず存在します.(最後に $n$ と $d$ を gcd で割れば良い)

浮動小数点を扱ったり,分数をきちんと持つのは面倒なので,すべての式に $10 \times H \times d$ をかけてしまって,一周が $360 \times 10 \times H \times d$ 度であるということにすれば実装が楽です.

計算量も,$H <= 100$ という制約から,十分間に合います.

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    int H, h0, m0, s0;
    while(cin >> H >> h0 >> m0 >> s0, H) {
        const ll d = 119 * H - 1;
        ll n = s0 * d;
        ll ho = h0, mo = m0;
        while(true) {
            ll ang_h = 3600 * ho * d + 60 * mo * d + n;
            ll ang_m = 60 * H * mo * d + n * H;
            ll ang_s = 60 * H * n;
            ang_m = (ang_m - ang_h) % (360 * 10 * H * d);
            ang_s = (ang_s - ang_h) % (360 * 10 * H * d);
            if(ang_m < 0) {
                ang_m += 360 * 10 * H * d;
            }
            if(ang_s < 0) {
                ang_s += 360 * 10 * H * d;
            }
            ang_h = 0;

            if(ang_h != ang_m) {
                ll ang1, ang2;
                if(ang_m < ang_s) {
                    ang1 = 360 * 10 * H * d - ang_s;
                    ang2 = ang_s - ang_m;
                } else {
                    ang1 = ang_s;
                    ang2 = ang_m - ang_s;
                }
                if(ang1 == ang2) {
                    break;
                }
            }

            n++;
            if(n == 60 * d) {
                n = 0;
                mo++;
            }
            if(mo == 60) {
                mo = 0;
                ho++;
            }
            if(ho == H) {
                ho = 0;
            }
        }
        ll g = __gcd(n, d);
        cout << ho << ' ' << mo << ' ' << n / g << ' ' << d / g << endl;
    }
}

感想

THE ICPC って感じの問題だった.