😇

ABC273の個人的な振り返り(A~E問題)

2022/10/23に公開約3,800字

これが私の初めての 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]
  • あとで掛ける方式(後述)

あとで掛ける方式

最終結果は、 A \times 10 ^ B という形になります。また、 10^k の位以下を四捨五入する際に、 10^{k-1} の位以下を気にする必要がありません。なので、割り算をしながら下位の桁についての処理を行い、最後に桁を合わせればよいです。[2]

int main(){
    cin >> x >> k;
    REP(i, k) x += 5, x /= 10;
    REP(i, k) x *= 10;
    cout << x << endl;
}

反省点

  • 考察を捨ててしまった

最近のABCは、たとえ前半の問題であっても、問題文のまま実装するより、多少考えてから実装した方がいいように感じることが増えてきましたね。

C問題

最速との差:5分31秒

自分の解法

上位・運営陣に見られた解法・実装

map で数と個数を一緒に管理し、数の逆順に、個数を出力していた[3]

反省点

  • STL の使い方を結構忘れてしまっている
  • 問題の言い換えをすることによって、実装の簡単化をすることを怠ってしまった

自力で解けた問題でも、改めて解説を見てみると、改善すべき点が多く見つかることがわかりました。

D問題

最速との差:52分34秒(+4ペナ)

自分の解法

  1. 0-indexed[4]
  2. 二次元座標圧縮 + 入力に応じて二分探索[4:1]
  3. REを起こさないようにするために、座標 -1, w, h にも壁を置いた[4:2]

上位・運営陣に見られた解法・実装

  • 疑似的な壁を置かずに、二分探索をして結果がbegin(), end() なのかで分類していた
    • イテレータではなく添え字で管理するものもあった[5]
  • 壁から出てしまう判定を、LRUD すべての場合でまとめて処理する[6]

反省点

  • ペナルティを生んだ原因は、一部の配列において 3 の処理を忘れていたため
    • 様々なケースを入れて試したが、なかなか気づくことができなかった
  • 壁を置くか、イテレーターをうまく使いこなして条件分岐させるかの判断は難しいが、後者の方が失敗が少なくなるのかなぁ

tourist[6:1]に従うのが一番な気がします。

E 問題

最速との差:7分53秒

自分の解法

木を作りました。

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;
}

上位・運営陣に見られた解法・実装

  • 自分の解法とあまり違いを感じませんでした。
  • 考察のスピードで負けてしまった気がします。

まとめ

前半のミスがパフォーマンスに大きく響いていることが分かったため、低難易度の問題を素早く解く練習を積んでいきたいと感じました。

脚注
  1. https://atcoder.jp/contests/abc273/editorial/5056 ↩︎

  2. https://atcoder.jp/contests/abc273/submissions/35648697 ↩︎

  3. https://atcoder.jp/contests/abc273/editorial/5018 ↩︎

  4. https://atcoder.jp/contests/abc273/submissions/35691604 ↩︎ ↩︎ ↩︎

  5. https://atcoder.jp/contests/abc273/submissions/35668584 ↩︎

  6. https://atcoder.jp/contests/abc273/submissions/35669870 ↩︎ ↩︎

Discussion

ログインするとコメントできます