第4回 ドワンゴからの挑戦状 本選-A アナログ時計
概要
太郎君は、H時M分S秒に寝ました。起きた時には、C1回秒針と分針が重なり、C2回分針と時針が重なった。この時、寝てる時間としてあり得るのは最低何分、最長何分でしょう？ありえない入力ならば-1と出力すること。
ただし、寝始めや寝起きの時間はすべて整数秒であり、それらの時間はいずれの針も重なってるということは起きないと保証されてる。
制約：
ACするまで
1. なんだこれは。。。とドン引きする。
2. ひとまずキリのいい時間まで進めるように書くが、実装がすさまじく大変して発狂。
3. 面倒になったので、一秒一秒数え上げることに。しかしここでも誤差などの関係で実装に苦しむ。
4. 書き方を少し変更した結果、AC
考察
この問題は、公式解説では何も考えずに愚直に数え上げたほうがいいとされている。(つまり、上のACするまでのと同じ)
しかし、精進友hotman78からO(1)の方がはるかに実装が楽というのを聞いて試したところすごく楽であったため、2通りの解法を明記する。どちらでも、非常に実装面で学べるテクニックの多い問題である思う。
線形で数え上げる方法
公式解説曰く実装が楽な方法。しかし、実装上の誤差を丁寧に扱わないといけない。
ひとまず、針が重なり合うのは基本的には整数秒ではないというのがわかる。(整数秒なのはx時00分だけ) 。はっきりと整数秒で重なるわけではないので、1週60分、12時間と考えるとどうしても小数点が出てくる。
ならば、一層のこと毎秒ごとの3本の針の角度の増分を出して、それを秒ごとに更新すればよい。針の重なりは、今の角度と1秒前の角度から判断できる。重なりが一度あるたびにC1, C2を1ずつ減らせばよい。
ここで、C1とC2の範囲が合うパターンを考える。どこかで、C1==0 && C2 == 0ならば、その時はC1とC2が共同の区間を持ってることとなる。答えはこの区間の長さを求めればよい。
上記のものを実装すればよい。実装する際に、時針は12時間一周、分針は60分に一周、秒針は60秒に一周することから、余りを取った。
また、小数点の値の度重なる加算は値の判断に影響を及ぼす程度の誤差になるので、今回の場合は増分を毎回足すのではなく、掛け算から算出した。(実際に加算で実装したら簡単に誤差でWAとなったため)
O(1)の算数解法
この問題を数え上げずに算数で解こうとすると、まずは綺麗な日にちに揃えないといけない。この際に、一定時間を進めようとすると多大なる場合分けが発生して実装コストが非常に重くなり、気が滅入る。
進められる量は入力に依るので綺麗な時間に進められるかが入力依存だが、ここで、入力に依存しない綺麗な時間へのそろえ方を考えてみる。
答えを言うと、きれいな時間に進めるのではなく、一旦始まりの0時0分0秒に戻して考えることとする。どれだけ進められようが、始まりの時間に戻ることには制約はない上に、この場合は簡単に算出できる。すべての針が重なる0時0分0秒から、一定周期(汚い小数であるが)でC1,C2が増えることから、今の時刻割るその一定の周期の値を切り捨てた回数をC1, C2に足せば、0時0分0秒から新しいC1, C2回、針が重なった後が答えであると簡単にわかる。
この際、C1, C2からそれぞれの周期を乗じて、整数に切り捨てればそれぞれの条件を満たす区間が求まる。(具体的な実装はソースコードへ)その2つの区間の積集合が答えとなり、存在しない場合は-1と出力すればよい。
この問題の算数解法の実装の要点は、計算しやすい点にいかにそろえるかである。その手段として、後ろそろえではなく、前そろえを用いた。
