雑記

競技プログラミングについての話題(?)

PCK予選 2015 (virtual)

眠すぎて杉になりそう


PCK2015の予選のvirtualを1時間だけやりました

5完
ooooox----

f:id:Luzhiled:20170727090947p:plain

A - The Number of Participants

問題概要

数字が3つ与えられます。総和を求めてください。

解法

難解な問題だった、危うく迷宮入りするところだった。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int a, b, c;
  cin >> a >> b >> c;

  cout << a + b + c << endl;
}

B - Fishing Competition

解法

書かれている通りに実装すると、入力の順番にPCK側の優しさを見ることができる。

#include <bits/stdc++.h>
using namespace std;

int a, b, c, d;

int solve(int h1, int h2) {
  return h1 * a + h2 * b + (h1 / 10) * c + (h2 / 20) * d;
}

int main() {
  int h[2][2];
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 2; ++j) {
      cin >> h[i][j];
    }
  }

  cin >> a >> b >> c >> d;

  int s = solve(h[0][0], h[0][1]);
  int t = solve(h[1][0], h[1][1]);
  if (s == t) {
    puts("even");
  }
  else {
    puts(s < t ? "kenjiro" : "hiroshi");
  }
}

C - Frog Going Straight

解法

カエルの気持ちになると、最初に大ジャンプをできるだけ繰り返して余ったぶんは小ジャンプして帰るのが最適だとわかる(カエルなので)

#include <bits/stdc++.h>
using namespace std;

int main() {
  int d, l;

  cin >> d >> l;

  int ans = d / l;
  ans += d - (l * ans);

  cout << ans << endl;
}

冷静に杉になると、D mod L でいいことがわかります。


D - Secret Investigation

解法

まあ書かれている通りにやると解けます

配列3つ用意して条件を判定してもいい気がしたけど、条件が2つもあってめんどくさそうだったのでやめた

#include <bits/stdc++.h>
using namespace std;

int n, m;
bool f[1010];

int main() {
  int ans = 0;

  cin >> n;

  memset(f, true, sizeof(f));

  cin >> m;
  for (int i = 0; i < m; ++i) {
    int a;
    cin >> a;
    f[a] = false;
  }

  cin >> m;
  for (int i = 0; i < m; ++i) {
    int a;
    cin >> a;
    f[a] = true;
  }

  cin >> m;
  for (int i = 0; i < m; ++i) {
    int a;
    cin >> a;
    if (f[a]) ans++;
  }

  cout << ans << endl;
}

E - Programming Contest

解法

上の方から見ると楽だなあみたいな気持ちになると楽(杉なので)

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  vector<int> p;

  cin >> n;
  for (int i = 0; i < n; ++i) {
    int a;
    cin >> a;
    p.push_back(a);
  }

  for (int i = n; i >= 0; --i) {
    int cnt = 0;
    for (int j = 0; j < n; ++j) {
      if (p[j] >= i) cnt++;
    }

    if (cnt >= i) {
      cout << i << endl;
      break;
    }
  }
}

F - Quality Management

解法

問題をぐっと睨む。めんどくさそうに感じる。(40分とかした)

愚直にやると O(C \times N ^ 2) になってしまうなあみたいな気持ちになる。

前計算してdiffのぶんだけ計算し直しでいいかなあみたいな気持ちになったので、

ダメな部分を全部もってクエリを処理するコードを一番最初に書いたけど、よく考えたら O(C \times N^2 logN) (悪化)(最悪)(logNで差を付けられろ)

ここで1時間たったのでvirtual終了



なんで一日に二回朝ごはん食べてるんだろうなあみたいな気持ちになりながらもう一度ちゃんと考察する。

前処理の O(N^2)は仕方がないのでここは放置するとして、他はもう少し改善できるよなあみたいな気持ちになったところ、改善どころか普通にやるだけでO(N^2 + C D)になって笑った

#include <bits/stdc++.h>
using namespace std;

int c, n, m;
bool p[1010][1010];

bool is_same(int y, int x) {
  if (y >= m) y = n - y - 1;
  if (x >= m) x = n - x - 1;
  int xx = n - x - 1;
  int yy = n - y - 1;
  return p[y][x] == p[yy][x] &&
         p[y][x] == p[y][xx] &&
         p[y][x] == p[yy][xx];
}

int main() {
  int ans = 0;

  cin >> c >> n;
  m = n / 2;

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      scanf("%1d", &p[i][j]);
    }
  }

  int cnt = 0;
  for (int i = 0; i < m; ++i) {
    for (int j = 0; j < m; ++j) {
      if (!is_same(i, j)) cnt++;
    }
  }

  if (cnt == 0) ans++;

  while (--c) {
    int d;
    cin >> d;

    for (int i = 0; i < d; ++i) {
      int y, x;

      cin >> y >> x;
      y--; x--;

      bool pre = is_same(y, x);
      p[y][x] ^= 1;
      if (pre != is_same(y, x)) {
        if (pre) {
          cnt++;
        } else {
          cnt--;
        }
      }
    }

    if (cnt == 0) ans++;
  }

  cout << ans << endl;
}