ABC287反省会
Q. https://atcoder.jp/contests/abc287/tasks/abc287_e
Eまででした。Gの実装が間に合わず辛酸舐めた。かなしい。
A - Majority
多数決って書いてあるのに、Forが過半数を超えたかで判定した。
int main() {
cincout();
ll N;
cin >> N;
ll f = 0;
rep(i, N){
string S;
cin >> S;
if (S[0] == 'F') ++f;
}
if (f > N / 2){
cout << "Yes" << endl;
}
else{
cout << "No" << endl;
}
}B - Postal Card
1WAして発狂した。
SがTと一致しているか、ではない。
TがSと一致しているか、である。
int main() {
cincout();
ll N, M;
cin >> N >> M;
map<string, bool> memo;
vector<string> V;
rep(i, N){
string S;
cin >> S;
S = S.substr(S.size() - 3);
V.emplace_back(S);
}
rep(i, M){
string T;
cin >> T;
memo[T] = true;
}
ll ans = 0;
rep(i, N){
ans += memo[V[i]];
}
cout << ans << endl;
}C - Path Graph?
「パスグラフ」の意味が難しかった。
・考察
いろいろ書きだして、条件をエスパーした。次の2パターンの合わせ技でAC。
1. "1本の木"であること。
=> 辺の数MがN - 1であり、連結であること。
2. 次数1が2つ、それ以外が次数2であること
を満たせばよかった。
Q. 次数の1,2,2,2,…2,1の組み合わせだけで判定すると？
A. 不完全ケースがある。連結じゃないグラフが考えられてしまう。
int main() {
cincout();
ll N, M;
cin >> N >> M;
if (M != N - 1){
cout << "No" << endl;
return 0;
}
UnionFind tree(N);
vector<ll> indeg(N, 0);
rep(i, M){
ll a, b;
cin >> a >> b;
--a, --b;
++indeg[a];
++indeg[b];
tree.unite(a, b);
if (indeg[a] > 2 || indeg[b] > 2){
cout << "No" << endl;
return 0;
}
}
if (tree.getSize(0) != N){
cout << "No" << endl;
return 0;
}
cout << "Yes" << endl;
}https://atcoder.jp/contests/abc287/submissions/38389244
D - Match or Not
・考察
1. 全部の文字を見直していると間に合わない
2. 変化を書き出してみる
Q.2
atcoder
?????
S'を書き出す
i=0: coder
i=1: a oder
i=2: at der
i=3: atc er
i=4: atco r
i=5: atcod
index[i]の一文字だけ状態変化している。
i=0のときだけ、T文字との誤りをカウントして、
iの変化時に、変化箇所だけ判定しなおしばよさそう。・実装
int main() {
cincout();
string S, T;
cin >> S >> T;
string U = S.substr(S.size() - T.size()); // S'を作る
ll wrong = 0;
auto isWrong=[&](char a, char b)->bool{
if (a == b) return false;
if (a == '?' || b == '?') return false;
return true;
};
rep(i, T.size()){
wrong += isWrong(U[i], T[i]);
}
rep(i, T.size() + 1){
// 判定
if (wrong > 0){
cout << "No" << endl;
}
else{
cout << "Yes" << endl;
}
// 変換
if (i == T.size()) break;
wrong -= isWrong(U[i], T[i]);
U[i] = S[i];
wrong += isWrong(U[i], T[i]);
}
}https://atcoder.jp/contests/abc287/submissions/38396612
E - Karuta
タイポで1REしてしまった。
・考察
辞書順にして、前後だけが最善マッチ候補。
・実装
int main() {
cincout();
ll N;
cin >> N;
vector<pair<string, ll>> V(N); // {文字列, id}
rep(i, N){
string S;
cin >> S;
V[i] = {S, i};
}
sort(all(V)); // 辞書順にする
ll ans[N]{};
// 辞書順の、前後だけが一致候補
rep(i, N){
auto[s, id] = V[i];
ll match = 0;
if (i - 1 >= 0){
auto [ps, pid] = V[i - 1];
ll cnt = 0;
while(cnt < min(ps.size(), s.size()) && ps[cnt] == s[cnt]){
++cnt;
}
chmax(match, cnt);
}
if (i + 1 < N){
auto [ps, pid] = V[i + 1];
ll cnt = 0;
while(cnt < min(ps.size(), s.size()) && ps[cnt] == s[cnt]){
++cnt;
}
chmax(match, cnt);
}
ans[id] = match;
}
rep(i, N){
cout << ans[i] << endl;
}
}https://atcoder.jp/contests/abc287/submissions/38401763
Fは「誘導部分グラフの連結成分数」の意味が分からなくて、ググって例を見てもなお、サンプルの意味がつながらなくて戦えない。
G - Balance Update Query
・考察
1. カードの値で座標圧縮して、
2. カードの枚数と総和のBITで管理すればいい。
3.
query3が来たら、枚数でにぶたんして上位何枚とるか決めればいい。
query1,2が来たら、BITの状態を更新すればいい。
というところまで見えて、あとは実装だけだったが、間に合わなかった。
・実装
int main() {
cincout();
ll N;
cin >> N;
vector<pll> A(N);
Bit<(ll)4e5 + 10> bits[2]; // [0] = 枚数, [1] = スコア
set<ll> vals;
ll totalcard = 0;
ll totalval = 0;
rep(i, N){
ll a, b;
cin >> a >> b;
A[i] = {a, b};
vals.insert(a);
totalcard += b;
totalval += a * b;
}
ll Q;
cin >> Q;
vector<tll> query;
rep(i, Q){
ll a[3];
cin >> a[0];
if (a[0] == 3){
cin >> a[1];
}
else{
cin >> a[1] >> a[2];
}
if (a[0] == 1){
vals.insert(a[2]);
}
query.emplace_back(a[0], a[1], a[2]);
}
map<ll, ll> comp; // comp[val] = id
map<ll, ll> inv; // comp[id] = val
{
ll id = 0;
for(auto s: vals){
comp[s] = id;
inv[id] = s;
++id;
}
}
rep(i, N){
auto[a, b] = A[i];
bits[0].add(comp[a], b);
bits[1].add(comp[a], a * b);
}
rep(i, Q){
auto [q, x, y] = query[i];
if (q == 1){
--x;
auto[a, b] = A[x];
bits[0].add(comp[a], -b);
bits[1].add(comp[a], -a * b);
totalval -= a * b;
A[x] = {y, b};
bits[0].add(comp[y], b);
bits[1].add(comp[y], y * b);
totalval += y * b;
}
else if (q == 2){
--x;
auto[a, b] = A[x];
bits[0].add(comp[a], -b);
bits[1].add(comp[a], -a * b);
totalcard -= b;
totalval -= a * b;
A[x] = {a, y};
bits[0].add(comp[a], y);
bits[1].add(comp[a], a * y);
totalcard += y;
totalval += a * y;
}
else{
if (totalcard < x){
cout << -1 << endl;
continue;
}
auto nibutan=[&](ll L, ll H)->ll{
while (H - 1 > L){
ll mid = (L + H) / 2;
if (bits[0].sum(mid) >= totalcard - x){
H = mid;
}
else{
L = mid;
}
}
return H;
};
ll cval = nibutan(-1, N + Q + 1); // valのcompで検索
ll b0 = bits[0].sum(cval);
ll ans = totalval - bits[1].sum(cval) + inv[cval] * (b0 - (totalcard - x));
cout << ans << endl;
auto debug=[&](){
cerr << "cval = " << cval << endl;
cerr << "b0 = " << b0 << endl;
};
// debug();
}
}
}https://atcoder.jp/contests/abc287/submissions/38426751