AOJ 1338 Clock Hands - すいバカ日誌

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1338

解法

まず，それぞれの針がなす角を求めましょう．短針が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;
    }
}

問題文

解法

ソースコード

感想