Educational Codeforces Round 41 (Div.2)

今回は1完です. Bのケアレスミスに気づきたかったね.

各列に積み上がっていくブロックの数のうち最小のものを出力する.
つまり一番低い列の高さが答え.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  int n, m;
  cin >> n >> m;

  int r[n];
  for(int i = 0; i < n; i++) {
    r[i] = 0;
  }
  for(int i = 0; i < m; i++) {
    int x;
    cin >> x;
    r[x - 1]++;
  }

  int mn = 2000000000;
  for(int i = 0; i < n; i++) {
    mn = min(mn, r[i]);
  }

  cout << mn << endl;
}

B - Lecture Sleep

t[i](1 <= i <= n)が1であるときのa[i]の値の総和を求めこれをbaseとする.
配列aから連続するk個の要素を取り出し, その中でインデックスが同じかつ配列tの要素が0である
配列aの要素の総和addを求める.
例えばk = 3で, 指定したインデックスの範囲がi = 2, 3, 4となるとき配列aと配列tは,
i 2 3 4
t 1 0 0
a 4 8 7
となる. このときadd = a[3] + a[4] = 15となる.
addの値を可能な連続するk個の範囲すべてで計算してその最大値とbaseを足したものが答え.
これを愚直に書くとO(n * k)になるが連続する大きさkの範囲から外れた要素をaddから引いて
大きさkの範囲に新たに加わった要素をaddに足すとO(n)でできる.
この記事の最初にケアレスミスしたって書いたけどどこをケアレスミスしたか忘れた. 時間空けすぎた.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  int n, k;
  cin >> n >> k;
  int a[n + 1];
  for(int i = 1; i <= n; i++) {
    cin >> a[i];
    // cout << "a[" << i << "]: " << a[i] << endl;
  }
  int t[n + 1];
  for(int i = 1; i <= n; i++) {
    cin >> t[i];
  }

  long long mx = 0;
  for(int i = 1; i <= n; i++) {
    if(t[i] == 1) {
      mx += a[i];
    }
  }

  long long base = mx;
  for(int i = 1; i <= k; i++) {
    if(t[i] == 0) {
      base += a[i];
    }
  }
  mx = max(mx, base);
  // cout << "base: " << base << endl;
  for(int i = 2; i <= n - k + 1; i++) {
    if(t[i - 1] == 0) {
      base -= a[i - 1];
    }
    if(t[i + k - 1] == 0) {
      base += a[i + k - 1];
    }
    mx = max(mx, base);
    // cout << base << endl;
  }

  cout << mx << endl;
}

C - Chessboard

自力で出来なかったのでEditorial見ながら解いた.
チェス盤は左下の角が必ず黒ということを知らなかったので倍のパターン調べる必要があると思ってしまった.
色塗り後のピースは角が黒のパターンのピース2つと角が白のパターンのピース2つになるはずなので,
まず各ピースが角が黒のパターンのピースにどれくらい合致しているか
(角が黒のパターンのピースとして使うとしたら塗りなおさなくてよいのは何箇所か)を調べる.
次にピースを4!通りに並べ替え, 各並び順に対応する塗り直しの回数を求め, その最小値を出力する.

以下, Editorialのほぼコピペ.

#include <bits/stdc++.h>

using namespace std;

const int N = 109;

int n;
string a[4][N];

int main(void) {
  cin >> n;
  for(int k = 0; k < 4; k++) {
    for(int i = 0; i < n; i++) {
      cin >> a[k][i];
      for(int j = 0; j < n; j++) {
	a[k][i][j] -= '0';
      }
    }
  }

  // 角が黒のパターンに何枚合致しているか
  vector <int> v;
  for(int k = 0; k < 4; k++) {
    int sum = 0;
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
	if((i + j) % 2 != a[k][i][j]) {
	  sum++;
	}
      }
    }
    v.push_back(sum);
    // cout << "a[" << k << "]: " << sum << endl;
  }

  // 4!通り並び替えて一番修正が少ないものを選ぶ
  int res = int(1e9);
  vector <int> perm;
  for(int k = 0; k < 4; k++) {
    perm.push_back(k);
  }
  while(next_permutation(perm.begin(), perm.end())) {
    int sum = 0;
    for(int k = 0; k < 4; k++) {
      int id = perm[k];
      if(k & 1) {
	sum += v[id];
      }
      else {
	sum += n * n - v[id];
      }
    }
    res = min(res, sum);
  }
  cout << res << endl;
}