ARC 069

2017.02.23

2月18日のAtCoder Regular Contest 069の感想です。C問題とD問題のみAC。800点38:56で276位でした。

C Scc Puzzle

S型のピースN個とc型のピースM個からSccを何個作ることができるか求める問題。ただしc型のピース2個をS型のピース1個に変えることができます。

まずcは常に2個単位で扱われるので「cc型のピースM/2個」と言い換えることができます。そしてSとccの個数の大小によって場合分けを行いました。

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

int main() {
  int64_t n, m;
  cin >> n >> m;
  m /= 2;
  cout << min(m, n + (m - n) / 2) << endl;
  return 0;
}

D Menagerie

円環状に並んだ合わせてN匹の羊（正直者）と狼（嘘つき）の割り当てを求める問題。1～N番目の各動物に対して「両隣の動物は同じ種類か」を尋ねた答えが入力で与えられています。長いので詳細は省略。

羊をtrueと表すことによって、i - 1, i, i + 1番目の動物の種類のXORとi番目の動物の回答が一致し、簡潔に記述できるようになりました。

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

int main() {
  int n;
  string s;
  cin >> n >> s;
  bool a[4][100000] = {{false, false}, {false, true}, {true, false}, {true, true}};
  for (int i = 2; i < n; i++) {
    for (int j = 0; j < 4; j++) {
      a[j][i] = a[j][i - 1] ^ a[j][i - 2] ^ (s[i - 1] == 'o');
    }
  }
  int k = -1;
  for (int i = 0; i < 4; i++) {
    if ((s[n - 1] == 'o') == (a[i][n - 2] ^ a[i][n - 1] ^ a[i][0]) && (s[0] == 'o') == (a[i][n - 1] ^ a[i][0] ^ a[i][1])) {
      k = i;
      break;
    }
  }
  if (k == -1) {
    cout << -1 << endl;
  } else {
    for (int i = 0; i < n; i++) {
      cout << "WS"[a[k][i]];
    }
    cout << endl;
  }
  return 0;
}

今回は度々つまずくD問題を難なく解けて嬉しいARCになりました。しかしE問題を解ける日はまだ遠そうです。