Codeforces Round #459 (Div2)

A - Eleven

iがフィボナッチ数なら"O", そうでないなら"o".
メモ化再帰で解く.関数fib(int n)とメモ配列fib_memo.
i = 1 to nについてi == fib(counter)なら"O"とする.
counterの初期値を2にすると1がダブらなくて済む.

#include <iostream>

using namespace std;

long long int fib_memo[1000] = {0};

long long int fib(int n) {
  if(n == 0) return 0;
  if(n == 1 || n == 2) return 1;
  if(fib_memo[n] != 0) {
    return fib_memo[n];
  }
  return fib_memo[n] = fib(n - 1) + fib(n - 2);
}

int main(void) {
  int n;
  cin >> n;
  int counter = 2;
  for(int i = 1; i <= n; i++) {
    if(i == fib(counter)) {
      cout << "O";
      counter++;
    }
    else {
      cout << "o";
    }
  }
  cout << endl;
}

B - Radio Station

名前: name
名前と対応するip: ip
コマンド: command
コマンドと対応するip: ipcom
にstringで保存する.
配列ipの各要素の末尾に';'を加えてipcomの各要素と比較できるようにする.
ipcomの各要素と一致するipの要素を見つけて対応する名前を出力する.

#include <iostream>

using namespace std;

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

  string name[n], command[m], ip[n], ipcom[m];
  for(int i = 0; i < n; i++) {
    cin >> name[i] >> ip[i];
    ip[i].push_back(';');
  }

  for(int i = 0; i < m; i++) {
    cin >> command[i] >> ipcom[i];
  }

  for(int i = 0; i < m; i++) {
    cout << command[i] << " " << ipcom[i];
    for(int j = 0; j < n; j++) {
      if(ipcom[i] == ip[j]) {
	cout << " #" << name[j];
	break;
      }
    }
    cout << endl;
  }
}

C - The Monster

Editorialの擬似コードを実装してみたけど問題ページに載ってる例でうまく行かない。
"?("の場合が間違ってカウントされてるっぽいけどEditorialが間違ってる?

#include <iostream>

using namespace std;

int main(void) {
  string s;
  cin >> s;

  int n = s.length();
  bool f[n + 1][n + 1];
  bool g[n + 1][n + 1];

  for(int l = 0; l < n; l++) {
    int cur = 0;
    bool ok;
    for(int r = l; r < n; r++) {
      ok = true;
      if(s[r] == ')') {
	cur--;
      }
      else {
	cur++;
      }
      if(cur < 0) {
	ok = false;
      }
      f[l + 1][r + 1] = ok;
    }
  }

  for(int r = 0; r < n; r++) {
    int cur = 0;
    bool ok;
    for(int l = r; l >= 0; l--) {
      ok = true;
      if(s[l] == '(') {
	cur--;
      }
      else {
	cur++;
      }
      if(cur < 0) {
	ok = false;
      }
      g[l + 1][r + 1] = ok;
    }
  }

  int ans = 0;
  for(int l = 1; l <= n; l++) {
    for(int r = l; r <= n; r++) {
      if(f[l][r] && g[l][r] && (r - l + 1) % 2 == 0) {
	cout << l << r << r - l + 1 << endl;
	ans++;
      }
    }
  }

  cout << ans << endl;
}