「AtCoder Grand Contest 034」に参加しました

コンテストページはこちら

結果

2完 [A(400), B(600)] 49:18 ペナルティ: 3 (-> 64:18)
・順位: 736位 (Rated)
・パフォーマンス: 1552
・Rating変化: 1326 -> 1351 (+25) [Rating最高値]

各問題の解法

A問題 (400点)

提出詳細
A～Cの間と、B～Dの間に ‘##’ があると飛び越えることができないため、No。
D < C の場合は、すぬけ君がふぬけ君を飛び越える必要があるため、B-1～D+1の間に '...' が存在する必要がある。 計算量 O((C-A) + (D-B))

int N, A, B, C, D;
cin >> N >> A >> B >> C >> D;
string s;
cin >> s;
A–; B–; C–; D–;
bool ans = true;

for (int i = A; i < C; i++) {
  if (s[i] == ‘#’ && s[i + 1] == ‘#’)
    ans = false;
}

for(int i = B; i < D; i++) {
  if (s[i] == ‘#’ && s[i + 1] == ‘#’)
    ans = false;
}

bool ret = D > C;
for (int i = B; i <= D; i++) {
  if (s[i – 1] == ‘.’ && s[i] == ‘.’ && s[i + 1] == ‘.’)ret = true;
}

cout << (ans && ret ? “Yes” : “No”) << endl;

各問題の解法

B問題 (600点)

提出詳細
まず、BCは移動してもその形を壊さないため、これをXとおく。
前から線形探索をして、Aならカウントを1増やす、Xならカウントを答えに足す、それ以外ならカウントをリセットする。

計算量 O(N)

string sr;
cin >> sr;
int N = sr.size();
if(N < 3) {
  cout << 0 << endl;
  return 0;
}
string s;
for(int i = 0; i < N; i++) {
  if (i < N - 1 && sr[i] == 'B' && sr[i + 1] == 'C') {
    s += "X";
    i++;
  }
  else
    s += sr[i];
}

int cnt = 0;
long long ans = 0;
N = s.size();
for (int i = 0; i < N; i++)
{
  if (s[i] == 'A') cnt++;
  else if (s[i] == 'X') ans += cnt;
  else cnt = 0;
}
cout << ans << endl;

感想

600まで解いたけど+25で、なかなか厳しい世界になったなって感じがします。