第4回 ドワンゴからの挑戦状 本選 A - アナログ時計

A - アナログ時計

問題概要

$ h $時$ m $分$ s $秒からスタートして，分針と秒針，時針と分針が重なった回数がそれぞれ$ C_1 $回，$ C_2 $回であるときの最小・最大の経過秒数を求める．

解法概要

$ C_1 \leq 10000 $なので，愚直に針の動きをシミュレートしても間に合う． (私は) 小数は扱いたくないので針の角度は時計の12の位置を0として度数法での角度に120をかけたものを使って針同士の角度の差を計算するようにした． テストケースcorner_01にずっと引っかかっていたのだが，原因はソースコードのコメント参照．

ソースコード

#include <iostream>

using namespace std;

typedef long long ll;

const ll cycle = 43200;

int main() {
    std::ios::sync_with_stdio(0); cin.tie(0);
    ll h,m,s,c[2];
    cin >> h >> m >> s;
    h %= 12;
    cin >> c[0] >> c[1];
    if(c[0] < c[1]){
        cout << -1 << endl;
        return 0;
    }

    ll tt = 0;
    ll h_hand, h_hand_prev = 3600 * h + 60 * m + s;
    ll m_hand, m_hand_prev = 720 * m + 12 * s;
    ll s_hand, s_hand_prev = 720 * s;
    ll ans[2] = {0, 0};
    while(c[0] >= 0 && c[1] >= 0){
        tt++;
        /* 
            針の角度が0になったときに，
            実際に追い抜きが起こっていないのに
            角度の大小関係が変わってしまうことを防ぐため，
            ここではまだcycle (= 43200)でmodは取らない
        */
        h_hand = (h_hand_prev + 1);
        m_hand = (m_hand_prev + 12);
        s_hand = (s_hand_prev + 720);

        if(m_hand != s_hand && (m_hand_prev - s_hand_prev) * (m_hand - s_hand) <= 0){
            if(ans[0] != 0){
                // tt-1で針が重なっている場合に注意 (corner_01)
                if(m_hand_prev != s_hand_prev) ans[1] = tt-1;
                else ans[1] = tt-2;
                break;
            }
            c[0]--;
        }
        if(h_hand != m_hand && (h_hand_prev - m_hand_prev) * (h_hand - m_hand) <= 0){
            if(ans[0] != 0){
                // tt-1で針が重なっている場合に注意 (corner_01)
                if(h_hand_prev != s_hand_prev) ans[1] = tt-1;
                else ans[1] = tt-2;
                break;
            }
            c[1]--;
        }

        if(c[1] == 0 && c[0] == 0 && ans[0] == 0){
            ans[0] = tt;
        }

        h_hand_prev = h_hand % cycle;
        m_hand_prev = m_hand % cycle;
        s_hand_prev = s_hand % cycle;
    }

    if(ans[1] == 0){
        cout << -1 << endl;
    }else{
        cout << ans[0] << " " << ans[1] << endl;
    }
}

感想

オープンコンテストの時から何度も挑戦してはWA食らってきたけど， やっと，やっとACできた……．

corner_01がかなり強敵のように感じていたけど，気づいてしまえばかなりあっけない．