SRM 515 250pt: RotatedClock

TopCoder

問題概要

数字の書かれていない目盛12個の時計がある。どれかの目盛を起点にした長針の角度と短針の角度がそれぞれ与えられる。そのようになる時刻を求める問題。ただし複数ある場合は最も早い時刻を答え、無い場合はその旨出力する。

考えたこと

  • うん？これ時刻がぴったり整数分でなかったらどうするの？
  • 問題文を読み返してみたけど分からない。
  • 短針の角度が整数だからそれは起こり得ないのか。なるほど
  • 最も早いとかもあることだし、答えを12*60小さい方から全部試すのが考えられる。
  • これで判定問題に落ちた。
  • で、時刻と角度が合致するかの判定はどれが始点になっているのかの12通り調べれば良い。
  • 後は実装するだけだけど、角度で浮動小数点数とか出さないように角度を60倍して考えよう。
  • 合わない。何で？
  • 角度を60倍する処理を2回やっていた。こういうバグは出さないようにしたいなあ
  • 提出。
  • intermissionのときとか、角度を浮動小数点数でやってる人落ちないかなあとか思ってたけど、hour_angle = 30*hour + minute*0.5でやっても基数の関係上誤差が出ないことに気付いた。
  • (30,30)で12:00と答えそうなコードを見つけて撃墜できたので救われた。

本番中に通ったコード

計算量は12*60*12くらい。

#include <string>
#include <cstdio>
using namespace std;

struct RotatedClock {

	string getEarliest(int hourHand, int minuteHand) {
		char ans[10];
		for(int H=0; H<12; H++){
			for(int M=0; M<60; M++){
				if(check(H,M,hourHand, minuteHand)){
					sprintf(ans, "%02d:%02d", H, M);
					return string(ans);
				}
			}
		}

		return "";
	}

	bool check(int hour, int minute, int h_ang, int m_ang){
		static const int MIN = 60;
		h_ang *= MIN;
		m_ang *= MIN;
		int ch_ang = 360/12*(MIN*hour + minute);
		int cm_ang = 360/60*MIN*minute;
		for(int start = 0; start < 12; start++){
			if(ch_ang == h_ang && cm_ang == m_ang){
				return true;
			}
			h_ang = (h_ang + 30*MIN)%(360*MIN);
			m_ang = (m_ang + 30*MIN)%(360*MIN);
		}
		return false;
	}
};

計算量を落とす

  • さすがにこの手の問題は自然なO(1)解法がありそう。
  • 本番中もそう思っていたけど、間に合う限り一番分かりやすい方法でやるべしというポリシーがあるので考えないことにしていた。
  • よく考えたら短針の角度で何分かが一意に定まる。
  • 時刻が分かればあとは簡単に修正できる。
#include <string>
#include <cstdio>
using namespace std;

struct RotatedClock {

	string getEarliest(int hour_angle, int minute_angle) {

		//何分かは決定できる
		int minute = (hour_angle % 30) * 60 / 30;

		//実際は何度ずれてる?
		int offset = (minute * 360 / 60) - minute_angle;

		//起点が目盛上に無い場合は答えなし
		if(offset % 30 != 0){
			return "";
		}

		//12時を起点とした短針の角度を求めてやることができる
		int right_hour_angle = (hour_angle + offset + 360) % 360;
		int hour = right_hour_angle / 30;

		char ans[10];
		sprintf(ans, "%02d:%02d", hour, minute);
		return string(ans);
	}

};