エクサウィザーズ 2019反省会

エクサウィザーズ 2019 - AtCoder。AとBは解けたけどCでダメだった。

A: Regular Triangle

最初Pythonand&&と書いてしまってRE出してしまった…。少なくとも1回はテストしないとダメ。

Python

A, B, C = map(int, input().split())
 
if A == B and B == C:
  print('Yes')
else:
  print('No')

C++

#include <bits/stdc++.h>
using namespace std;

int main(){
    int A, B, C;
    cin >> A >> B >> C;
    
    if (A == B && B == C) {
      cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }
}

B: Red or Blue

C++

最初の提出。

#include <bits/stdc++.h>
using namespace std;
int main(void){
  int N;
  string s;
  cin >> N >> s;
  
  int r_cnt = 0;
  int b_cnt = 0;
  for (int i = 0; i < s.size(); i++) {
    if (s.at(i) == 'R') {
      r_cnt++;
    } else {
      b_cnt++;
    }
  }
  if (r_cnt > b_cnt) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

これはstd::countを使えば短く書けるらしい。

#include <bits/stdc++.h>
using namespace std;

int main(void){
  int N;
  string s;
  cin >> N >> s;
  int B = count(s.begin(), s.end(), 'B');
  cout << ((N - B) > B ? "Yes" : "No") << endl;
}

Python

N = int(input())
s = input()
B = s.count("B")

if N - B > B:
  print("Yes")
else:
  print("No")

C: Snuke the Wizard

O(NQ)の方法しか思いつかずダメだった。

Python

import sys
import numpy as np
input = sys.stdin.readline

N, Q = map(int, input().split())
S = input().strip()

tile = {}
now = np.array([1] * (N+2))

for s in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
  tile.setdefault(s, [])

for i in range(len(S)):
  tile[S[i]].append(i+1)

for i in range(Q):
  t, d = input().split()
  old = now[tile[t]]
  if d == "L":
    now[(np.array(tile[t])-1).tolist()] += old
    now[tile[t]] -= old
  else:
    now[(np.array(tile[t])+1).tolist()] += old
    now[tile[t]] -= old

print(sum(now) - now[0] - now[-1])

解説によると、「最終的に左(右)に出たゴーレムより左(右)に居たゴーレムはすべて左(右)に出る」ことから、左(右)に出るゴーレムと出ないゴーレムの境界を探せば良いらしい。ゴーレム1対の最終的な結果はO(Q)で求められるので、境界は二分探索で探せばO(QlogN)で見つかる。左右探してもO(2QlogN)なので間に合う。

import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
S = input().strip()
td_list = [input().split() for _ in range(Q)]
dest = [-2] * (N+1)

def sim(i): # i番目のゴーレムの最終結果を得る
  idx = i
  if dest[i] != -2:
    return dest[i]
  for td in td_list:
    if idx == -1:
      dest[i] = -1
      return -1
    elif idx == N:
      dest[i] = N
      return N
    elif td[0] == S[idx]:
      if td[1] == "L":
        idx -= 1
      else:
        idx += 1
  dest[i] = idx
  return idx


# 左側の境界を探索
left, right = -1, N

while right - left != 1:
  mid = (left + right) // 2
  if sim(mid) == -1:
    left = mid
  else:
    right = mid

lb = right

# 右側の境界を探索
left, right = -1, N

while right - left != 1:
  mid = (left + right) // 2
  if sim(mid) == N:
    right = mid
  else:
    left = mid

rb = left

print(rb - lb + 1)

C++

Pythonだと1500msくらいかかって結構ギリギリなのでC++でも書いてみた。

#include <bits/stdc++.h>
using namespace std;

int sim(int i, int N, string& S, vector<int>& dest, vector<vector<char>>& td_list) {
  int idx = i;
  if (dest.at(i) != -2) return dest.at(i);
  for (vector<char> td : td_list) {
    if (idx == -1) {
      dest.at(i) = -1;
      return -1;
    }
    if (idx == N) {
      dest.at(i) = N;
      return N;
    }
    if (td.at(0) == S.at(idx)) {
      if (td.at(1) == 'L') {
        idx--;
      } else {
        idx++;
      }
    }
  }
  dest.at(i) = idx;
  return idx;
}

int main(void){
  int N, Q;
  cin >> N >> Q;
  string S;
  cin >> S;
  vector<int> dest(N, -2);
  vector<vector<char>> td_list(Q, vector<char>(2));
  for (int i = 0; i < Q; i++) {
    cin >> td_list.at(i).at(0) >> td_list.at(i).at(1);
  }
  
  // 左側の境界を探索
  int left = -1;
  int right = N;
  while (right - left != 1) {
    int mid = (left + right) / 2;
    if (sim(mid, N, S, dest, td_list) == -1){
      left = mid;
    } else {
      right = mid;
    }
  }
  int lb = right;

  // 右側の境界を探索
  left = -1;
  right = N;
  while (right - left != 1) {
    int mid = (left + right) / 2;
    if (sim(mid, N, S, dest, td_list) == N){
      right = mid;
    } else {
      left = mid;
    }
  }
  int rb = left;

  cout << rb - lb + 1 << endl;
}

300ms程度にはなった。

f:id:Rion778:20190331025405p:plain