Zenn
🙌

ABC275の個人的な振り返り(A~F問題)

2022/10/30に公開
C
競技プログラミング
AtCoder
tech

コンテストの振り返り

個人成績

成績：5完0ペナ（34分48秒）

順位：648位

パフォーマンス：1609

レート変化：1596→1598(+2)

自分の提出

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

2400(理論値) 2000 1600 1200
6完36:33 6完60:44 5完39:30 4完41:07

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

A B C D E F
0:17 0:25 3:41 1:23 3:04 3:59

各問題の振り返り

A問題

最速との差：1分5秒（+0ペナ）

自分の解法

愚直に実装をしました

int n;
int maxl, maxh;
int h[101010];
 
int main(){
    cin >> n;
    REP(i, n){
        cin >> h[i];
        if(chmax(maxh, h[i]))maxl = i;
    }
    cout << maxl + 1 << endl;
}

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

  • (H_i, i) をソートして、先頭を出力[1]

B問題

最速との差：1分29秒（+0ペナ）

自分の解法

modint構造体を用意して、実装しました

modint<998244353> ans1 = 1, ans2 = 1;
 
LL a, b, c, d, e, f;
 
int main(){
    cin >> a >> b >> c >> d >> e >> f;
    ans1 *= a;
    ans1 *= b;
    ans1 *= c;
    ans2 *= d;
    ans2 *= e;
    ans2 *= f;
    cout << (ans1 - ans2).a << endl;
}

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

  • 多倍長整数を使う[2]

反省点

  • 実装量の割には時間がかかってて気になるが、撮影をし忘れたので原因がわからない。

C問題

最速との差：13分24秒（+0ペナ）

自分の解法

左上の頂点と、その次の頂点を全探索しました

string s[101];
 
int main(){
    REP(i, 9)cin >> s[i];
 
    LL ans = 0;
 
    REP(i, 9)REP(j, 9){
        if(s[i][j] != '#') continue;
        REP(r1, 9)REP(r2, 9){
            if(r1 == 0 && r2 == 0)continue;
            if(r2 == 0)continue;
            if(!(0 <= i + r2 && i + r2 < 9))continue;
            if(!(0 <= j + r1 && j + r1 < 9))continue;
            if(s[i + r2][j + r1] == '.')continue;
 
            if(!(0 <= i + r1 + r2 && i + r1 + r2 < 9))continue;
            if(!(0 <= j + r1 - r2 && j + r1 - r2 < 9))continue;
            if(s[i + r1 + r2][j + r1 - r2] == '.')continue;
 
            if(!(0 <= i + r1 && i + r1 < 9))continue;
            if(!(0 <= j - r2 && j - r2 < 9))continue;
            if(s[i + r1][j - r2] == '.')continue;
            ans++;
        }
    }
    cout << ans << endl;
}

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

  • 条件を調べるパートをまとめてラムダ式で記述した[3]
  • まとめて計算して、あとで割る[4]

反省点

  • 最初に問題文を読んだときに、数え上げる正方形は「2次元座標軸に平行なものと限る」と勘違いしていた
    • 問題文を読むときに、入出力例にも目を通すべき
  • 配列外かどうかの判定を各パートが冗長すぎた
    • 上位の例のように、関数やラムダ式にしてまとめるべきだった

D問題

最速との差：2分38秒（+0ペナ）

自分の解法

メモ化再帰をしました

map<LL, LL> mp;
 
map<LL, bool> visited;
 
LL solve(LL cur){
    if(mp[cur] != 0)return mp[cur];
    if(cur == 0){
        mp[0] = 1;
        return 1;
    }
 
    mp[cur] = solve(cur / 2) + solve(cur / 3);
    
    return mp[cur];
}
 
LL n;
 
int main(){
    cin >> n;
    cout << solve(n) << endl;
}

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

  • 同様にメモ化再帰を行っていた[5]

E問題

最速との差：12分21秒（+0ペナ）

自分の解法

modint構造体等を用いて、愚直にDPをしました[6]

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

  • 同様の実装をしていた[7]

反省点

  • 「K 回の操作が終了したときゴールにいる確率」を求める問題だと勘違いしてしまっていた
    • 「入力例 2」によってその勘違いに気づいたが、出力の形式的に気づきにくかった
    • 落ち着いて問題文を読むしかない（？）
      • 本番を想定した練習を増やすべき

F問題

最速との差：∞（通せませんでした）

自分の解法

DP[i][j][k][l]:= i 番目まで見て、和が j で

  • k が 0 のとき

    • a_i を集合に含まない

  • k が 1 のとき

    • a_i を集合に含む

  • l が 0 のとき

    • a_0 を集合に含まない

  • l が 1 のとき

    • a_0 を集合に含む

という 4 次元DPをするつもりでした[8]

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

  • 最初に適宜条件分岐をさせることによって、 l の状態を持たずに済んだ[9][10]
  • i - 1 から i にしか遷移しないDPなので、配列をそれぞれ用意した[10:1]

反省点

  • TLEやWAの多くは、配列外参照によるものだった
    • 定義が面倒だが、こういう時こそ動的配列を使うべき
脚注

  1. https://atcoder.jp/contests/abc275/submissions/36014879 ↩︎

  2. https://atcoder.jp/contests/abc275/submissions/36032946 ↩︎

  3. https://atcoder.jp/contests/abc275/submissions/35935491 ↩︎

  4. https://atcoder.jp/contests/abc275/submissions/36039452 ↩︎

  5. https://atcoder.jp/contests/abc275/editorial/5110 ↩︎

  6. https://atcoder.jp/contests/abc275/submissions/36055256 ↩︎

  7. https://atcoder.jp/contests/abc275/editorial/5116 ↩︎

  8. https://atcoder.jp/contests/abc275/submissions/36074388 ↩︎

  9. https://atcoder.jp/contests/abc275/editorial/5140 ↩︎

  10. https://atcoder.jp/contests/abc275/submissions/36042633 ↩︎ ↩︎

Discussion