😸

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

2022/10/24に公開約4,300字

コンテストの振り返り

個人成績

成績:5完2ペナ 82分15秒

順位:825位

パフォーマンス:1579

レート変化:1598→1596(-2)

自分の提出

パフォーマンスのボーダー

2400(理論値) 2000 1600 1200
6完(ABCDEG)100:56 5完40:20 5完89:26 4完55:55

A~G問題の最速攻略時間

A B C D E F G
0:36 0:48 2:29 3:48 5:20 12:02 7:02

各問題の振り返り

A問題

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

自分の解法

誤差がこわかったので 10000 倍したものを計算して、そのあとに 10000 で割った。

0 埋めのマニピュレータの名前を探すのにてこずりました。

 
double a, b;
 
int main(){
    cin >> a >> b;
    
    int num = b * 10000 / a;
    num += 5;
    cout << num / 10000 << "."<<setfill('0') << right <<setw(3) << (num % 10000) / 10 << endl;
}

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

誤差を恐れずに愚直に出力したものがFAだった。[1]

反省点

  • setprecision(3) とすれば小数点以下 3 位までしか出力されないことを知っていたのに、なぜかこのような回りくどいことをしてしまった。
  • 誤差には気を付けたいので、FAは見習わないようにする

復習のためにも、コンテストに取り組んでる様子を録画するべきなのかなぁと感じました。


B問題

最速との差:1分11秒(+0ペナ)

自分の解法

int h, w;
 
char c[1010][1010];
 
int main(){
    cin >> h >> w;
 
    REP(i, h)REP(j, w)cin >> c[i][j];
 
    REP(j, w){
        int cnt = 0;
        REP(i, h)if(c[i][j] == '#')cnt++;
        if(j)cout << " ";
        cout << cnt;
    }
    cout << endl;
}

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

あまり差はありませんでした。

反省点

特に差が見られなかったので、合格とします。


C問題

最速との差:2分54秒(+0ペナ)

自分の解法

愚直に実装しました。

int n;
 
int a[202020];
 
vector<int> g[404040];
 
int ans[404040];
 
int main(){
    cin >> n;
    REPS(i, n){
        cin >> a[i];
        g[a[i]].emplace_back(i * 2);
        g[a[i]].emplace_back(i * 2 + 1); 
    }
 
    REPS(i, 2 * n + 1)ans[i] = HINF<int>();
 
    ans[1] = 0;
    queue<int> q;
    q.push(1);
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        for(auto to : g[cur]){
            if(ans[to] == HINF<int>()){
                ans[to] = ans[cur] + 1;
                q.push(to);
            }
        }
    }
    REPS(i, 2 * n + 1){
        cout << ans[i] << endl;
    }
}

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

  • 親のアメーバに関する答えを持ちながら、入力されるデータをを待てばいい[2]

反省点

  • 考察を挟まずに愚直に実装してしまった。

この程度の考察であれば 30 秒程度でできると思うので、手を動かす前に少し立ち止まることを意識したいです。


D問題

最速との差:25分27秒(+0ペナ)

自分の解法

DP をしました。どこかでバグを生んだせいでタイムロスしてしまったのですが、どこか忘れてしまいました。

int n, x, y;
 
int a[1010];
 
int geta = 10005;
 
bool can_move[1010][20010];
 
int main(){
    cin >> n >> x >> y;
    REP(i, n)cin >> a[i];
 
    x += geta;
    y += geta;
 
    can_move[0][geta] = true;
    can_move[1][geta] = true;
    
 
    for(int i = 0;i < n;i++){
        int cur = i;
        int nxt = i + 2;
        if(i == 0){
            can_move[nxt][geta + a[i]] = true;
            continue;
        }
        REP(j, 20010){
            if(j - a[i] >= 0)   can_move[nxt][j - a[i]] |= can_move[cur][j];
            if(j + a[i] < 20010)can_move[nxt][j + a[i]] |= can_move[cur][j];
        }
 
        REP(j, 20010)can_move[cur][j] = false;

    }
 
    int last_even, last_odd;
 
    if(n % 2){
        last_odd = n;
        last_even = n + 1;
    }else{
        last_even = n;
        last_odd = n + 1;
    }
 
    if(can_move[last_even][x] && can_move[last_odd][y]){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl; 
    }
 
}

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

  • ポインタをうまく利用することによって、負の座標を表現していた[3]
  • 偶奇で dp を分けていた[3:1]
  • 2 値の dp であり、遷移も単純なので、 bitset を利用した[4]

反省点

  • バグ取りに時間をかけてしまった

考察にはあまり時間がかからなかったので、実装の方針に問題があると感じました。


E問題

最速との差:76分55秒(+2ペナ)

自分の解法

DP[訪れた都市の集合][最後に訪れた都市][使ったブースターの数]

という形の bitDP をしました。計算量は O((NM)^2 \times 2^{(N + M)}) でした。[5]

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

  • std::hypot() を使う[6]
  • 拾ったブースターの数は、訪れた都市の集合から求まるので、情報として持たなくてよい[6:1]
  • そもそも、 2^i 倍の速度になるので、拾ったら即使ってよい[6:2]

反省点

  • 最初、2^i 倍ではなく i 倍だと誤読してから実装してしまったのが、タイムロスおよびデバッグのしにくいコードの生成につながったと思います。

まとめ

DP の実装の遅さが結果に響いているので、DPの問題を精進する際は、実装する速度を上げる訓練を積もうと思いました。

脚注
  1. https://atcoder.jp/contests/abc274/submissions/35861569 ↩︎

  2. https://atcoder.jp/contests/abc274/editorial/5019 ↩︎

  3. https://atcoder.jp/contests/abc274/editorial/5079 ↩︎ ↩︎

  4. https://atcoder.jp/contests/abc274/submissions/35786430 ↩︎

  5. https://atcoder.jp/contests/abc274/submissions/35892415 ↩︎

  6. https://atcoder.jp/contests/abc274/submissions/35892415 ↩︎ ↩︎ ↩︎

Discussion

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