Bondo416さんのユニークビジョンプログラミングコンテスト2023 新春 (AtCoder Beginner Contest 287)での成績:990位
— ボンド@競プロ (@bond_cmprog) January 28, 2023
パフォーマンス:1473相当
レーティング:1421→1426 (+5) :)#AtCoder #ユニークビジョンプログラミングコンテスト2023新春(ABC287) https://t.co/9MVxbKxevv
A - Majority
For
の個数が $ \lceil \frac{N}{2} \rceil $ 以上であればよい
void solve() { int N; cin >> N; int f = 0; REP(i, N) { string s; cin >> s; if (s == "For") f++; } cout << (f >= ceil_div(N, 2) ? "Yes" : "No") << endl; }
B - Postal Card
全探索で条件を満たすものを数える
void solve() { int N, M; cin >> N >> M; vector<string> S(N), T(M); REP(i, N) cin >> S[i]; REP(i, M) cin >> T[i]; int ans = 0; REP(i, N) { int ok = 0; REP(j, M) { int sz = S[i].size(); if (S[i][sz - 3] == T[j][0] and S[i][sz - 2] == T[j][1] and S[i][sz - 1] == T[j][2]) ok = 1; } ans += ok; } cout << ans << endl; }
C - Path Graph?
パスグラフは木かつ木の直径が $ N - 1 $ であるので辺の数が $ M - 1 $ かつ直径が $ N - 1 $ であるかどうかを判定する
void solve() { int N, M; cin >> N >> M; treeDiameter g(N); REP(i, M) { int u, v; cin >> u >> v; --u, --v; g.add_edge(u, v); } if (M != N - 1) { cout << "No" << endl; return; } g.build(0); if (g.diameter == N - 1) cout << "Yes" << endl; else cout << "No" << endl; }
D - Match or Not
$ x $ を $ 1 $ 増やしたときに前の状態と異なる箇所は2箇所(消える箇所と増える箇所)なので差分更新ができる
よって予め今何文字マッチしているかを求めておき、それを差分更新して各 $ x $ について答えていく
void solve() { string S, T; cin >> S >> T; int correct = 0; int sz = T.size(); REP(i, sz) { if (S[(int)S.size() - 1 - i] == T[sz - 1 - i] or S[(int)S.size() - 1 - i] == '?' or T[sz - 1 - i] == '?') correct++; dump(S[(int)S.size() - 1 - i]); dump(T[i]); } int ans = 0; cout << (correct == sz ? "Yes" : "No") << endl; REP(i, sz) { if (S[(int)S.size() - sz + i] == T[i] or S[(int)S.size() - sz + i] == '?' or T[i] == '?') correct--; if (S[i] == T[i] or S[i] == '?' or T[i] == '?') correct++; // dumps(S[(int)S.size() - sz + i], T[i], S[i]); cout << (correct == sz ? "Yes" : "No") << endl; } }
E - Karuta
文字列を辞書順でソートをすると、各 $ i $ についてのLCPはその前後を見るだけでよくなる
各文字列についてその前後のLCPを愚直に求めても文字列の長さの総和程度で収まるのでソートがボトルネックとなり、実行時間以内に求めることができる
void solve() { int N; cin >> N; vector<string> S(N); vector<pair<string, int>> P(N); REP(i, N) { cin >> S[i]; P[i] = {S[i], i}; } sort(ALL(P)); vector<int> idx(N); REP(i, N) idx[i] = P[i].second; vector<int> ans(N); REP(i, N) { int x = P[i].second; int ma = 0; if (i > 0) { int y = P[i - 1].second; int cnt = 0; REP(i, min(S[x].size(), S[y].size())) { if (S[x][i] != S[y][i]) break; cnt++; } chmax(ma, cnt); } if (i + 1 < N) { int y = P[i + 1].second; int cnt = 0; REP(i, min(S[x].size(), S[y].size())) { if (S[x][i] != S[y][i]) break; cnt++; } chmax(ma, cnt); } ans[x] = ma; } REP(i, N) cout << ans[i] << endl; }