Educational Codeforces Round 37 (Div.2)

A - Water The Garden

最も左にある蛇口から庭の左端までの区間, 最も右にある蛇口から庭の右端までの区間では,
(蛇口のあるマス含む)蛇口から端までの距離 = その範囲を満たすのに必要な時間となる.
左からi番目の蛇口とi + 1番目の蛇口の間の区間では,
(蛇口のあるマス含む)2つの蛇口の間の距離 / 2 (小数点以下切り上げ) = その範囲を満たすのに必要な時間となる.
これらのうち最大値を求めればよい.

#include <iostream>
#include <utility>

using namespace std;

int main(void) {
  int t;
  cin >> t;
  int n[t], k[t], x[t][200];
  for(int i = 0; i < t; i++) {
    cin >> n[i] >> k[i];
    for(int j = 0; j < k[i]; j++) {
      cin >> x[i][j];
    }
  }


  for(int i = 0; i < t; i++) {
    int mx = x[i][0];
    for(int j = 1; j < k[i]; j++) {
      int diff = x[i][j] - x[i][j - 1] + 1;
      if(diff % 2 == 1) {
	diff++;
      }
      diff /= 2;
      mx = max(mx, diff);
    }
    mx = max(mx, n[i] - x[i][k[i] - 1] + 1);
    cout << mx << endl;
  }
}

B - Tea Queue

生徒の並び始める時間, 諦める時間をペアにして並び始める時間順にキューに入れる.
現在時間timeの初期値は先頭の生徒が並び始めた時間にする.

1. timeが諦める時間より遅ければ0を出力してpop.
2. timeが生徒が並んでいる時間内であれば現在時を出力, popしてtimeを1秒(?)進める.
3. timeが生徒が並び始める時間より早ければその時間までtimeを進める.

1~3をキューの中身がなくなるまで繰り返したら終了.

#include <iostream>
#include <vector>
#include <utility>
#include <string>
#include <queue>

using namespace std;

int main(void) {
  int t;
  cin >> t;
  int n[t];
  vector< vector<int> > l, r;
  l.resize(t);
  r.resize(t);
  for(int i = 0; i < t; i++) {
    cin >> n[i];
    for(int j = 0; j < n[i]; j++) {
      int lj, rj;
      cin >> lj >> rj;
      l[i].push_back(lj);
      r[i].push_back(rj);
    }
  }

  queue< pair<int, int> > q;
  for(int i = 0; i < t; i++) {
    for(int j = 0; j < n[i]; j++) {
      q.push(pair<int, int>(l[i][j], r[i][j]));
    }
    int time = l[i][0];
    string ans;
    while(!q.empty()) {
      if(time > q.front().second) {
	ans += "0 ";
	q.pop();
      }
      else if(q.front().first <= time && time <= q.front().second) {
	ans += to_string(time) + " ";
	time++;
	q.pop();
      }
      else {
	time = q.front().first;
      }
    }
    ans.pop_back();
    cout << ans << endl;
  }
}

C - Swap Adjament Elements

交換可能な連続する範囲(3列目の入力で1が連続する範囲)(i, j)(i <= j)について, 各要素がi以上j以下であればOK.
そうでない場合はNOを出力して終了.
交換出来ない要素はi番目がiであるかどうかを調べる.
1~nの各要素は入力時に1を引いておくと配列の添字を各要素のチェックにそのまま用いることができる.

以下のリンクの提出を参考にして解いた.
http://codeforces.com/contest/920/submission/34922144

#include <iostream>

using namespace std;

int main(void) {
  int n;
  cin >> n;
  int a[n];
  for(int i = 0; i < n; i++) {
    cin >> a[i];
    a[i]--;
  }
  string s;
  cin >> s;

  int cur = 0;
  for(int i = 0; i < n; i++) {
    if(s[i] == '0' || i == n - 1) {
      for(int j = cur; j <= i; j++) {
	if(a[j] < cur || a[j] > i) {
	  cout << "NO" << endl;
	  return 0;
	}
      }
      cur = i + 1;
    }
  }
  cout << "YES" << endl;
  
}

1つの入力でテストケース複数あるのめんどくせー