📑

ABC276の振り返り(A~F問題)

2022/11/05に公開約5,700字

コンテストの振り返り

個人成績

成績:5完2ペナ 51分56秒

順位:1152位/7118人

パフォーマンス:1366

レート変化:1598→1577(-21)

自分の提出

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

2400(理論値) 2000 1600 1200
7完99:06 6完51:24 6完99:58 5完85:35

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

A B C D E F
0:29 1:19 0:35 1:27 7:47 5:03

各問題の振り返り

A問題

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

自分の解法

後ろから文字を見ていき、 a が出たらそこで探索を切る

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

  • 昇順に見ていって、 a があれば更新

反省点

  • 「昇順でもできる」といった発想が浮かばなかった

B問題

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

自分の解法

愚直に実装した

vector<int> g[202020];
 
int n, m;
 
int main(){
    cin >> n >> m;
    REP(i, m){
        int a, b;
        cin >> a >> b;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    REPS(v, n){
        cout << SZ(g[v]);
        sort(ALL(g[v]));
        REP(i, SZ(g[v])){
            cout << " " << g[v][i];
        }
        cout << endl;
    }
}

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

  • 変わった実装は確認できなかった

反省点

  • 実装スピードがやたらと遅い

C問題

最速との差:8分20秒(+0ペナ)

自分の解法

公式解説[1]と同じ実装をした

int n;
int p[101];
 
int main(){
    cin >> n;
    REP(i, n)cin >> p[i];
 
    int idx = n - 1;
 
    while(p[idx - 1] < p[idx])idx--;
    idx--;
    int less_idx = -1, less_max = -1;
    for(int i = idx;i < n;i++){
        if(p[idx] <= p[i])continue;
        if(chmax(less_max, p[i])){
            less_idx = i;
        }
    }
    swap(p[idx], p[less_idx]);
    sort(p + idx + 1, p + n);
    reverse(p + idx + 1, p + n);
 
    REP(i, n){
        if(i)cout << " ";
        cout << p[i];
    }
    cout << endl;
}

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

  • prev_permutation() を利用した[2]

反省点

  • prev_permutation() を使う発想はあったのだが、テンパって採用しなかった
    • 後半の問題にどうしても時間がかかってしまうので、前半の時間を短くしようとすると、ついつい焦ってしまう
  • swap をする部分でバグらせてしまった

D問題

最速との差:20分44秒(+2ペナ)

自分の解法

  1. 最終的にありうる A_i の値を列挙する
  2. その値になるための最小回数を求める
int n;
int a[1010];
 
int cnt = 0;
map<int, bool> visited;
map<int, int> idx;
vector<int> g[505050];
 
vector<int> edge_list;
 
void make_vertex(int num){
    if(visited[num])return;
    visited[num] = true;
    edge_list.emplace_back(num);
    if(num % 2 == 0)make_vertex(num / 2);
    if(num % 3 == 0)make_vertex(num / 3);
}
 
int calc(int num){
    int ret = 0;
    while(num % 3 == 0){
        ret++;
        num /= 3;
    }
    while(num % 2 == 0){
        ret++;
        num /= 2;
    }
    if(num != 1){
        return -1;
    }
    return ret;
}
 
int main(){
    cin >> n;
    REP(i, n)cin >> a[i];
 
    REP(i, n){
        make_vertex(a[i]);
    }
 
    sort(ALL(edge_list));
 
    int ans = HINF<int>();
 
    REP(i, SZ(edge_list)){
        int gl = edge_list[i];
        int value = 0;
        bool isok = true;
        REP(j, n){
            int cur = a[j];
            if(cur < gl || cur % gl){
                isok = false;
                break;
            }else{
                int ret = calc(cur / gl);
                if(ret == -1)isok = false;
                value += ret;
            }
        }
        if(isok)chmin(ans, value);
    }
 
    if(ans == HINF<int>()){
        cout << -1 << endl;
    }else{
        cout << ans << endl;
    }
}

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

  • 2^{x} \times 3^{y} \times z の形とみて比較をして求める[3]

反省点

  • 問題を見た瞬間に「数字を頂点としてみれば、LCAで行けそう!」という発想をしてしまった
    • 遷移が木ではないことにすぐ気づいたが、似たような考察に至ってしまった

E問題

最速との差:9分00秒(+0ペナ)

自分の解法

  • 4方向にそれぞれDFSをして、閉路検出をした
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
 
int h, w;
string fld[1010101];
vector<vector<bool>> visited;
 
bool dfs(int ci, int cj, int pi, int pj){
    bool ret = false;
 
    if(fld[ci][cj] == 'S')return true;
 
    visited[ci][cj] = true;
    REP(dir, 4){
        int ni = ci + dy[dir];
        int nj = cj + dx[dir];
        if(pi == ni && pj == nj)continue;
        if(!(0 <= ni && ni < h) || !(0 <= nj && nj < w))continue;
        if(fld[ni][nj] == '#')continue;
        if(visited[ni][nj])continue;
        visited[ni][nj] = true;
        ret |= dfs(ni, nj, ci, cj);
    }
    return ret;
}
 
int main(){
    cin >> h >> w;
 
    visited.resize(h, vector<bool>(w, false));
 
    REP(i, h)cin >> fld[i];
 
    int sr, sc;
 
    REP(i, h)REP(j, w){
        if(fld[i][j] == 'S'){
            sr = i, sc = j;
        }
    }
 
    REP(dir, 4){
        int ny = sr + dy[dir];
        int nx = sc + dx[dir];
        if(!(0 <= ny && ny < h) || !(0 <= nx && nx < w))continue;
        if(fld[ny][nx] == '#')continue;
 
        REP(i, h)REP(j, w)visited[i][j] = false;
        bool ret = dfs(ny, nx, sr, sc);
 
        if(ret){
            cout << "Yes" << endl;
            return 0;
        }
    }
 
    cout << "No" << endl;
}

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

  • bfsで S からの最短距離を求め、その途中で衝突が発生したら、そこで閉路となる[4]
  • 閉路検出に Union-Find を用いる[5]

反省点

  • 「閉路」という言葉とその検出方法を忘れてしまい、ググる時間が少々発生してしまった

F問題

※終了20分後に自力ACしました

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

自分の解法

  • 地道に期待値を求めた [6]
    • (たぶん)「今見ている値より小さい値の数」「今見ている値より大きい値の総和」を求めるパートが本質で、ここは 2 つのセグ木を用いた

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

  • 分母の値はどこも同じなので、まとめて割る[7]

反省点

  • 遷移と計算を冗長に書いてしまい、バグを処理するのにだいぶ時間をかけてしまった
    • X_i を求めるのに X_{i - 1} の情報しかいらないのなら、 X を配列で定義しない」というアイデアもあるかもしれない
脚注
  1. https://atcoder.jp/contests/abc276/editorial/5161 ↩︎

  2. https://atcoder.jp/contests/abc276/submissions/36221115 ↩︎

  3. https://atcoder.jp/contests/abc276/editorial/5167 ↩︎

  4. https://atcoder.jp/contests/abc276/editorial/5187 ↩︎

  5. https://atcoder.jp/contests/abc276/submissions/36144471 ↩︎

  6. https://atcoder.jp/contests/abc276/submissions/36263889 ↩︎

  7. https://atcoder.jp/contests/abc276/submissions/36232468 ↩︎

Discussion

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