エクサウィザーズ 2019 - AtCoder。AとBは解けたけどCでダメだった。
A: Regular Triangle
最初Pythonでand
を&&
と書いてしまってRE出してしまった…。少なくとも1回はテストしないとダメ。
A, B, C = map(int, input().split())
if A == B and B == C:
print('Yes')
else:
print('No')
#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
最初の提出。
#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;
}
N = int(input())
s = input()
B = s.count("B")
if N - B > B:
print("Yes")
else:
print("No")
C: Snuke the Wizard
O(NQ)の方法しか思いつかずダメだった。
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):
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)
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程度にはなった。