みんなのプロコン 2018

A - yahoo

問題文通りに判定する.

#include <bits/stdc++.h>

using namespace std;

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

  if(s[0] == 'y' && s[1] == 'a' && s[2] == 'h' && s[3] == s[4]) {
    cout << "YES" << endl;
  }
  else {
    cout << "NO" << endl;
  }
}

B - オークション

Xの桁数がK桁以下の場合, 答えは10^k円.
Xの桁数がK桁より大きい場合, K+1桁目を1増やし, 下K桁を0にする.
stoiやto_stringを使うとstringとintを往復出来て便利なことがわかった.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  string x;
  int k;
  cin >> x >> k;

  if(x.length() <= k) {
    string z;
    z += '1';
    for(int i = 0; i < k; i++) {
      z += '0';
    }
    cout << z << endl;
    return 0;
  }

  string ans;
  for(int i = 0; i < x.length() - k; i++) {
    ans += x[i];
  }
    
  int anstoi = stoi(ans);
  anstoi++;

  ans = to_string(anstoi);
  for(int i = 0; i < k; i++) {
    ans += '0';
  }

  cout << ans << endl;
}

DPをまともに解いたことがないのでCに挑むのはまた今度にしたい(やらないフラグ).

Codeforces Round #461 (Div. 2)

A - Cloning Toys

#include <iostream>

using namespace std;

int main(void) {
  int x, y;
  cin >> x >> y;

  int copy = y - 1;
  if(copy > x || (x - copy) % 2 != 0) {
    cout << "No" << endl;
  }
  else {
    cout << "Yes" << endl;
  }
}

上のコード提出したけど速攻Hackされた.
(生活こわれる時間帯で頭まわらなかったからね, しょうがないね)
editorialによると,
x = (奇数), y = 0の場合誤って"Yes"になるのでダメ.
x = (偶数), y = 1の場合も"Yes"になってしまうのでダメ.
y = 0, 1については別に場合分けする必要がある.

#include <iostream>

using namespace std;

int main(void) {
  int x, y;
  cin >> x >> y;

  if(y == 0) {
    cout << "NO" << endl;
    return 0;
  }
  if(y == 1) {
    if(x == 0) {
      cout << "Yes" << endl;
    }
    else {
      cout << "No" << endl;
    }
    return 0;
  }

  int copy = y - 1;
  if(copy > x || (x - copy) % 2 != 0) {
    cout << "No" << endl;
  }
  else {
    cout << "Yes" << endl;
  }
}

B - Magic Forest

n <= 2500で更に制約がかかるので3重for文で全探索しても大丈夫.
1 <= i <= j <= k <= nなのでjは i <= j <= n の範囲で探索.
3つの数が三角形の辺の長さにならないといけないので, (i + j) > kとなる.
よってkの最大値は(i + j - 1)とnの小さい方になるので, j <= k < min(i + j, n + 1).
i, j, kをbitsetにしてexorをとって0なら数える.
0 ⊕ 0 ⊕ 0 = 0なので上の方の桁は気にせず32bitとってよい.

#include <iostream>
#include <bitset>
#include <algorithm>
#include <utility>

using namespace std;

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

  int count = 0;
  for(int i = 1; i <= n; i++) {
    for(int j = i; j <= n; j++) {
      for(int k = j; k < min(i + j, n + 1); k++) {
	bitset<32> a, b, c;
	a = (bitset<32>) i;
	b = (bitset<32>) j;
	c = (bitset<32>) k;
	a ^= b;
	a ^= c;
	if(a == 0) {
	  count++;
	}
      }
    }
  }
  cout << count << endl;
}

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つの入力でテストケース複数あるのめんどくせー

Atcoder Petrozavodsk Contest 001

A - Two Integers

XがYの倍数でなければXが答えになる.

#include <iostream>

using namespace std;

int main(void) {
  int x, y;
  cin >> x >> y;

  if(x % y == 0) {
    cout << -1 << endl;
    return 0;
  }
  cout << x << endl;
}

B - Two Arrays

操作回数は(bの総和) - (aの総和)回.
ここまではコンテスト中にわかった.

1. a[i] > b[i]のとき少なくともb[i]をa[i] - b[i]回1増やす必要がある.
2. a[i] < b[i]のとき少なくともa[i]を(b[i] - a[i] + 1) / 2 (小数点以下切り捨て)回2増やす必要がある.

上の2つが(editorialによると)必要十分らしい.

02/07追記: (bの総和), (aの総和), 1増やす回数, 2増やす回数はlong long intでなければいけないのでコードを修正.

#include <iostream>

using namespace std;

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

  long long int sum_a = 0, sum_b = 0;
  for(int i = 0; i < n; i++) {
    sum_a += a[i];
    sum_b += b[i];
  }
  long long int t = sum_b - sum_a;
  long long int t_a = 0;
  long long int t_b = 0;
  for(int i = 0; i < n; i++) {
    if(a[i] < b[i]) {
      t_a += (b[i] - a[i] + 1) / 2;
    }
    else if(a[i] > b[i]) {
      t_b += a[i] - b[i];
    }
  }
  if(t >= t_a && t >= t_b) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

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;
}