CODE FESTIVAL 2016 オープンコンテスト

2016.11.28

CODE FESTIVAL 2016を終えて。せっかくなので解説を読む前に、気になっていたけれど解き残していた問題を何問か解いてみました。

本戦

Final (Parallel)

当日WAだった問題を解き直しても結局考察不足でTLEになりそうだったので省略。

トーナメント

Elimination Tournament Round 1 (Parallel), Round 2 (Parallel), Round 3 (Parallel)

当日の結果はRound1落ちでした。不得意な競技プログラミングの中でも速解きは特に苦手なようです。

Round 2 A 迷子の高橋君

満点解答を目指すもWAが消えなかったので部分点200までで諦めました。

#include <iostream>
using namespace std;

int main() {
  int x, p;
  int a;
  float r;
  std::cin >> x >> p;
  if (x % 2 == 0) {
    a = 0;
  } else {
    a = -1;
  }

  if (p == 100) {
    r = (x - a) / 2;
    std::cout << r << std::endl; // 部分点
  } else {
    std::cout << "(´・ω・｀)" << std::endl;
  }
  return 0;
}

チームリレー

Relay (Parallel)

11人が1人1問ずつ解くリレー。当日は最も簡単なA問題を担当しました。初級者でも時間をかければ解ける問題が多かったものの、制限時間、資料参照不可のルールに会場の緊張感も加わって、当日では解けなかったと思います。

A 合成抵抗

抵抗R1、R2を並列接続した合成抵抗値を出力するだけの問題。たったそれだけでも手が震えて時間が掛かった上、出力の小数点以下桁数を間違えて1WAしました。（幸いにもCODE FESTIVALはペナルティなし。）

当時std::coutのフォーマット方法を忘れてprintfしていたのを書き直しました。

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
  int a, b;
  cin >> a >> b;
  cout << fixed << setprecision(7) << (1.0 / (1.0 / a + 1.0 / b)) << endl;
  return 0;
}

B 鏡文

担当の人があっと言う間にACしたので読む暇すら無かった問題。bdpqのみからなる文字列を受け取り、図形的に左右反転しても同じ文字列のままかを判定します。

#include <iostream>
#include <string>
using namespace std;

char m[128];

int main() {
  string s;
  cin >> s;
  int l = s.length();
  if (l % 2 == 1) {
    cout << "No" << endl;
    return 0;
  }

  m['b'] = 'd'; m['d'] = 'b'; m['p'] = 'q'; m['q'] = 'p';
  for (int i = 0; i < l / 2; i++) {
    if (m[s[i]] != s[l - 1 - i]) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}

C 硬度フェスティバル

とあるルールで行われるトーナメントの勝者を求める問題。全戦をシミュレートすることしか思いつきませんでしたが、それで間に合いました。

#include <iostream>
#include <cmath>
using namespace std;

int main() {
  int n;
  int a[1 << 18];
  cin >> n;
  for (int i = 0; i < 1 << n; i++) {
    cin >> a[i];
  }
  for (int m = 1; m < 1 << n; m *= 2) {
    for (int i = 0; i < 1 << n; i += m + m) {
      if (a[i] != a[i + m]) {
        a[i] = abs(a[i] - a[i + m]);
      }
    }
  }
  cout << a[0] << endl;
  return 0;
}

E 方眼紙と線分

線分が横切るマス（境界を含まない）の個数を求める問題。グリッドと線分の関係は、アクションゲームやグラフィックなどの分野で考えることが多い問題なので、楽しく解けました。

点(a, b)と(c, d)を得たらひとまず原点に移動。基本となるのはマンハッタン距離ですが、線分がグリッドの格子点を通るたびに使うマスの個数が1減ります。格子点を通る回数はabs(a - c)とabs(b - d)の最大公約数なので次のような解法になります。

#include <iostream>
#include <cmath>
using namespace std;

int gcd(int a, int b){
  for (int c; a != 0; ) { c = a; a = b % a; b = c; }
  return b;
}
int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  a = abs(a - c);
  b = abs(b - d);
  cout << a + b - gcd(a, b) << endl;
  return 0;
}

F 3分割ゲーム

問題文は短いけれど理解するのに手間取りました。解法は単純で、3分割した中央の長さが最大になるように分割操作をx回分巻き戻していくことになります。intだと溢れてしまったのでint64_tを使用しました。

#include <iostream>
using namespace std;

int main() {
  int x;
  int64_t n;
  int64_t a[3] = {2, 2, 2};
  cin >> x;
  for (int i = 0; i < x; i++) {
    n = a[0] + a[1] + a[2];
    a[0] = 1; a[1] = n; a[2] = n + 1;
  }
  cout << n << endl;
  return 0;
}

I 目があったら負け

正解となる出力が複数あり、そのうち一通りを出力すればよい形式。こういった出題形式の名を当日司会の方々が言っていたのですが、忘れてしまいました。基本的には隣の人から順に選んでいくだけでよく、nが偶数の場合は真反対の人同士が衝突しないようにうまくずらします。少々煩雑なコードになってしまいました。

#include <iostream>
using namespace std;

int main() {
  int n;
  cin >> n;
  if (n == 2) {
    cout << -1 << endl;
  } else if (n % 2 == 0) {
    for (int i = 0; i < n / 2; i++) {
      for (int j = 0; j < n - 1; j++) {
        if (j) cout << ' ';
        cout << (i + j + 1) % n + 1;
      }
      cout << endl;
    }
    for (int i = n / 2; i < n; i++) {
      cout << (i + n / 2) % n + 1;
      for (int j = 1; j < n - 1; j++) {
        cout << ' ' << (i + j) % n + 1 + (j < n / 2 ? 0 : 1);
      }
      cout << endl;
    }
  } else {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n - 1; j++) {
        if (j) cout << ' ';
        cout << (i + j + 1) % n + 1;
      }
      cout << endl;
    }
  }
  return 0;
}

感想

疲れたから競技プログラミングはしばらくいいかな……。