AtCoder Beginner Contest 330 振り返り

ABC330

概要

実力的には二年前に茶色になって放置して暫くぶりの参加なので詳しい解説などは期待しないでもらえると。
同じぐらいの初心者さんがこんな感じで解いたのかぁ的な見方か、上級者の方が愉悦として見ていただけると幸いです。

コンテスト中に触ることができたのはA,B,C,D問題。ACできたのはC問題までです。
触れた問題で解説を見て理解できたものについては振り返っていきたいと考えています。

A - Counting Passes

考えてたこと
点数を全て受け取って基準の点数を超えた人の数を数えるだけです。

提出したもの

a.cpp

int main() {
    int n,l;
    cin >> n >> l;
    int cnt = 0;
    rep(i,0,n){
        int a;
        cin >> a;
        if(a>=l){
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

振り返り
特になし。

B - Minimize Abs 1

考えてたこと
そもそも問題の理解に時間がかかりました。よくわからなくてテストケース見た感じ大体LかR返すんじゃないかなぁと考えてLとRの距離が近い片方を返すコードを書きました、それで1WA。
考え直してAがLとRの範囲内に存在する場合、yがAの時abs(y-a)が0で最小値、xもAである必要があるということに気づきました。

提出したもの

b.cpp

int main() {
    int n, l, r;
    cin >> n >> l >> r;

    rep(i, 0, n) {
        int a;
        cin >> a;

        if (l <= a && a <= r) {
            cout << a;
            if (i != n - 1) {
                cout << " ";
            }
            continue;
        }

        if (abs(l - a) > abs(r - a)) {
            cout << r;
        } else
            cout << l;

        if (i != n - 1) {
            cout << " ";
        }
    }
    return 0;
}

振り返り
一応開始12分ぐらいでACできたのですが、かなり時間がかかってしまったと思います。問題の読解や絶対値で困惑し理解に時間がかかりました。

C - Minimize Abs 2

考えてたこと
シンプルに解くだけならxとyを0から無限まで回してx^2+y^2とDの距離をできるだけ近づければ良いんだろうなぁと考えました。ただもちろんその方針だと計算量が全く足りないので計算量を減らす術を考えます。

まず二重ループを避けたかったのでxの値だけで全探索してyはxの値に応じて変えることにしました。
xは0からsqrt(d)+1の範囲で全探索しました。sqrt(d)+1というのは、D以下の値ではなくDとの距離の最小値を求めたいのでDを超える場合についても考える必要があると思ったからです。
(説明がうまくできないので例を出して。Dが15の場合、xが3で15-3^3=6より、xが4で15-4^4=-1で、xが4の場合の方が距離が近いみたいな感じです。)

そうして、x^2のパターンを求めた後Dから引きます。引いた値をnumとコードではしましたが、numが0以下の場合はabs(num)を解としました。
numが0より大きな場合はsqrt(num)を求めnowからsqrt(num)の二乗、sqrt(num)+1の二乗を引きその絶対値の小さい方を解としました。ここの理屈はxの時と同じです。

提出したもの

c.cpp

int main() {
    ll d;
    cin >> d;
    ll sqrt_d = sqrt(d) + 1;

    ll ans = 100100100100100;
    ll now;

    for (ll i = 0; i <= sqrt_d; i++) {
        ll num = d - i * i;
        if (num < 0) {
            now = abs(num);
        } else {
            ll sqrt_num = sqrt(num);
            now = min(abs(num - sqrt_num * sqrt_num), abs(num - (sqrt_num + 1) * (sqrt_num + 1)));
        }
        ans = min(now, ans);
    }
    cout << ans << endl;
    return 0;
}

振り返り
解説読んでもよく分からなかったけど、原案さんがyoutubeであげてた解説とかpythonのコードと同じ感じだったのでまあ良いかなぁという感じ。
問題設定が円と、整数で表される座標との距離っていうイメージがつけばもっと早く回答できたかな、というところ。
それと、コンテストとは関係ないですが上の考えたところまとめです、感覚で解いてたので文字に起こしての説明が難しいです...。

D - Counting Ls

考えてたこと
まずは値を受け取る。その後シンプルに解くなら三重ループだろうなぁと考えつつそれだとTLEを起こすことは明らかなので解決する術を考えます。(結局TLEを解消できませんでした。)

提出したもの

d.cpp

int main() {
    vector<vector<char>> table(2010, vector<char>(2010));
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> table[i][j];
        }
    }

    vector<ll> row(2020);
    vector<ll> column(2020);

    map<int, vector<int>> row_map;

    for (int i = 0; i < n; i++) {
        ll cnt = 0;
        for (int j = 0; j < n; j++) {
            if (table[i][j] == 'o') {
                row_map[i].push_back(j);
                cnt++;
            }
        }
        row[i] = cnt;
    }

    for (int i = 0; i < n; i++) {
        ll cnt = 0;
        for (int j = 0; j < n; j++) {
            if (table[j][i] == 'o') {
                cnt++;
            }
        }
        column[i] = cnt;
    }

    ll ans = 0;

    for (int i = 0; i < n; i++) {
        if (row[i] < 2) {
            continue;
        }

        for (int j = 0; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                if (table[i][j] == 'o' && table[i][k] == 'o') {
                    ans += column[j] - 1;
                    ans += column[k] - 1;
                }
            }
        }
    }

    cout << ans << endl;
    return 0;
}

振り返り
解いている最中同じ行の2点をとってそれらが共にoならその列のoの数を加算するみたいなことを書いたのですが、そもそも1点をとって(行内のoの数-1)*(列内のoの数-1)とすれば同じものが数えられることがないと解説を見て気づきました、反省です。
C問題の時もそうですが、実際の形を想像できていれば解けたのではないかと思います。やはり最強のプログラミングツールは紙とペンなのでしょうか...。

提出したもの(コンテスト後)

d.cpp

int main() {
    vector<vector<char>> table(2010, vector<char>(2010));
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> table[i][j];
        }
    }

    vector<ll> row(2020);
    vector<ll> column(2020);

    for (int i = 0; i < n; i++) {
        ll cnt = 0;
        for (int j = 0; j < n; j++) {
            if (table[i][j] == 'o') {
                cnt++;
            }
        }
        row[i] = cnt;
    }

    for (int i = 0; i < n; i++) {
        ll cnt = 0;
        for (int j = 0; j < n; j++) {
            if (table[j][i] == 'o') {
                cnt++;
            }
        }
        column[i] = cnt;
    }

    ll ans = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (table[i][j] == 'o') {
                ans += (row[i] - 1) * (column[j] - 1);
            }
        }
    }

    cout << ans << endl;
    return 0;
}

感想

C,Dなど総じてイメージ力が足りないように思えます...。この辺の感覚はやっていけばついていくものだと信じるばかりです。頭の処理能力が足りないので紙とペンを使って補佐していきたいところ...。
unratedで参加していたため一時間ぐらいで頭が限界になって離脱したのですがパフォーマンスは想定よりかなり高くて驚きました...。C問題を回答するまでのスピードが大事なのでしょうか...? この調子なら次からのrated参加も検討したいです。

終わり

前回の記事に比べて考えることをうまく言語化することができていないと思いそこが反省です。言語化できていないというのは自分自身がなんとなくで問題を解いているという点に原因の一端があると思うので鍛えていきたいところです。