エクサウィザーズ 2019 - AtCoder。AとBは解けたけどCでダメだった。
A: Regular Triangle
最初Pythonでand
を&&
と書いてしまって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程度にはなった。