👻
ABC273の個人的な振り返り(A~E問題)
これが私のはじめてのzennでの記事になります。
コンテストの振り返り
個人成績
成績：5完5ペナ（91分53秒）
順位：708位
パフォーマンス：1594
レート変化：1599→1598(-1)
パフォーマンスのボーダー
| 2400(理論値) | 2000 | 1600 | 1200 |
|---|---|---|---|
| 6完79:09 | 5完56:38 | 5完112:44 | 4完87:27 |
A~F問題の最速攻略時間
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0:20 | 1:18 | 2:17 | 4:09 | 6:46 | 14:33 |
各問題の振り返り
A問題
最速との差：1分38秒（+1ペナ）
自分の解法
愚直に実装しました
LL f(LL num){
if(num == 0)return 1;
return num * f(num - 1);
}
LL n;
int main(){
cin >> n;
cout << f(n) << endl;
}
上位・運営陣に見られた解法・実装
ほとんどの方が、愚直ではなく逆順に掛ける実装をしていました。
int n;
int main(){
cin >> n;
LL ans = 1;
for(LL i = 1;i <= n;i++)ans *= i;
cout << i << endl;
}
反省点
- 「
N 0 - わざわざ問題文通りに実装してしまった。
前半の問題が早く片付けば片付くほど、後半の問題を解ける時間が増えるので、手間の減る実装を心掛けていきたいですね。
B問題
最速との差：9分27秒
自分の解法
愚直に実装しました。
LL ro(LL x, int d){
LL y = 0;
LL step = 1;
REP(i, d + 1)step *= 10;
for(LL cand_y = (x / step - 10) * step; cand_y < (x / step + 10) * step; cand_y += step){
if(abs(cand_y - x) <= abs(y - x)){
y = cand_y;
}
}
return y;
}
LL x, k;
int main(){
cin >> x >> k;
REP(i, k){
x = ro(x, i);
}
cout << x << endl;
}
上位・運営陣に見られた解法・実装
- 文字列で管理すると愚直な実装でも楽にできる[1]
- あとで掛ける方式（後述）
あとで掛ける方式
最終結果は、
int main(){
cin >> x >> k;
REP(i, k) x += 5, x /= 10;
REP(i, k) x *= 10;
cout << x << endl;
}
反省点
- 考察を捨ててしまった
最近のABCは、たとえ前半の問題であっても、問題文のまま実装するより、多少考えてから実装した方がいいように感じることが増えてきましたね。
C問題
最速との差：5分31秒
自分の解法
std::setの仕様を確認しながら実装していきました
int main(){
cin >> n;
REP(i, n)cin >> a[i];
vector<pair<int, int>> v;
REP(i, n){
v.push_back({a[i], i});
}
sort(ALL(v));
reverse(ALL(v));
set<int> st;
REP(i, n){
int sz = st.size() - distance(st.begin(), st.upper_bound(v[i].first));
ans[sz]++;
st.insert(v[i].first);
}
REP(i, n){
cout << ans[i] << endl;
}
}
上位・運営陣に見られた解法・実装
std::map で数と個数を一緒に管理することによって、二分探索を実装する手間を減らしていた。[3]
反省点
- STLの使い方を結構忘れてしまっている
自力で解けた問題でも、改めて解説を見てみると、改善すべき点が多く見つかりました。
D問題
最速との差：52分34秒（+4ペナ）
自分の解法
上位・運営陣に見られた解法・実装
- 疑似的な壁を置かずに、二分探索をして結果がbegin(), end() なのかで分類していた
- イテレータではなく添え字で管理するものもあった[5]
- 壁から出てしまう判定を、
LRUDすべての場合でまとめて処理する[6]
反省点
- ペナルティを生んだ原因は、一部の配列において
3 - さまざまなケースを入れて試したが、なかなか気づくことができなかった
- 壁を置くか、イテレーターをうまく使いこなして条件分岐させるかの判断は難しいが、後者の方が失敗しにくくなるのかなぁ
tourist[6:1]に従うのが一番なのかな。
E 問題
最速との差：6秒（すばらしい！）
自分の解法
木を作りました。
int main(){
cin >> q;
int cur = 0;
node_val[0] = -1;
REPS(i, q){
cin >> s;
if(s == "ADD"){
cin >> x;
node_val[i] = x;
g[cur].emplace_back(i);
rg[i] = cur;
cur = i;
}else if(s == "DELETE"){
cur = rg[cur];
}else if(s == "SAVE"){
cin >> x;
saved[x] = cur;
}else{
cin >> x;
cur = saved[x];
}
if(i != 1)cout << " ";
cout << node_val[cur];
}
cout << endl;
}
上位・運営陣に見られた解法・実装
- 自分の解法とあまり違いを感じなかった。
まとめ
前半のミスがパフォーマンスに大きく響いていることが分かったため、低難易度の問題を素早く解く練習を積んでいきたいと感じました。
Discussion