問題

B – 超大型連休

プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

atcoder.jp

解法

1. 振替休日の蓄積日を保持してカレンダーを実装する。

コード例

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
// const ll INF = 1LL << 60;
// const int INF = 1001001001;


vector<string> stringSplit(const string& str, char sep) {
  vector<string> v;
  stringstream ss(str);
  string buffer;
  while(getline(ss, buffer, sep)) {
    v.push_back(buffer);
  }
  return v;
}

int main() {
  int N;
  cin >> N;

  vector<vector<int>> calendar(12);
  int k = 0;
  rep(i, 12) {
    if(i == 1) {
      rep(j, 29) {
        if(k == 0 || k == 6) {
          calendar[i].push_back(1);
        } else {
          calendar[i].push_back(0);
        }
        k++;
        if(k == 7) {
          k = 0;
        }
      }
    } else if(i == 3 || i == 5 || i == 8 || i == 10) {
      rep(j, 30) {
        if(k == 0 || k == 6) {
          calendar[i].push_back(1);
        } else {
          calendar[i].push_back(0);
        }
        k++;
        if(k == 7) {
          k = 0;
        }
      }
    } else {
      rep(j, 31) {
        if(k == 0 || k == 6) {
          calendar[i].push_back(1);
        } else {
          calendar[i].push_back(0);
        }
        k++;
        if(k == 7) {
          k = 0;
        }
      }
    }
  }

  rep(i, N) {
    string s;
    cin >> s;
    vector<string> v = stringSplit(s, '/');
    int month = stoi(v[0]) - 1;
    int day = stoi(v[1]) - 1;
    calendar[month][day]++;
  }

  vector<int> sum(366);
  int cnt = 0;
  int duplicate = 0;
  rep(i, 12) {
    int n = calendar[i].size();
    rep(j, n) {
      if(1 < calendar[i][j]) {
        duplicate += calendar[i][j] - 1;
        sum[cnt] = 1;
      } else if(1 == calendar[i][j]) {
        sum[cnt] = calendar[i][j];
      } else {
        if(0 < duplicate) {
          sum[cnt] = 1;
          duplicate--;
        } else {
          sum[cnt] = calendar[i][j];
        }
      }
      cnt++;
    }
  }

  /*
  rep(i, 366) { cout << sum[i] << " "; }
  cout << endl;
  */

  int ans = 0;
  int current = 0;
  rep(i, 366) {
    if(sum[i] == 1) {
      current++;
      ans = max(ans, current);
    } else {
      current = 0;
    }
  }

  cout << ans << endl;
  return 0;
}