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

考えたこと

重なるタイミングがどんなときかとりあえず列挙する
分針と秒針はxx:00:00、xx:01:01とxx:01:02の間、xx:02:02とxx:02:03の間…
時針と分針は00:00:00、01:05:00あたり…
時針と分針は明らかに面倒なのでコードを書いて列挙することにする
重なるタイミングが列挙できればc_1,c_2回時刻を遷移させるシミュレーションを行えばよさそう
二つ時刻が与えられた時にその時刻間の時間を求める関数を書いて遷移させるのにかかる時間を求められるようにする
条件を満たすのは[c_1回遷移させる分の時間,c_1+1回遷移させる分の時間)になる
秒針と分針、時針と分針でそれぞれ区間を求めてその共通部分が答えなければ-1
-----他の人のコードを見た----
冷静になって考えるとHH:MM:SSの形でもつと処理が地獄なので全て秒単位でもつべき
O(c_1 + c_2)のコードを書いたがもっと愚直にシミュレーションできる
分針と秒針は1分に1回重なるので答えは大きくてもせいぜい60*10^4くらいになるはずなので1秒ごとにシミュレーションを書いても余裕
時刻now-1からnowで分針と秒針、時針と分針が重なるかどうかの判定はO(1)でできる
重なった回数が与えられた条件を満たす区間を出力する

2時間バグらせた
バグらせやすそうな問題は考察してから実装

学び

時刻は秒でもつ

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

signed main(void)
{
  int h, m, s, c1, c2;
  cin >> h >> m >> s >> c1 >> c2;

  int start = h*3600 + m*60 + s;
  int now = start;
  int cnt1 = 0, cnt2 = 0;
  int l = INF, r = -1;
  for(; cnt1<=c1 && cnt2<=c2; ++now) {
    // 秒針と分針
    if((now-1)%60*60 < (now-1)%3600 && now%60*60 >= now%3600) cnt1++;
    // 分針と時針
    if((now-1)%3600*12 < (now-1)%43200 && now%3600*12 >= now%43200) cnt2++;

    // ちょうど重なっているときは含まない
    if(now%60*60 == now%3600 || now%3600*12 == now%43200) continue;

    // 重なった回数が条件を満たす
    if(cnt1 == c1 && cnt2 == c2) {
      chmin(l, now-start);
      chmax(r, now-start);
    }
  }

  if(l == INF) cout << -1 << endl;
  else cout << l << " " << r << endl;

  return 0;
}

ferinの競プロ帳

競プロについてのメモ

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

考えたこと

学び