AtCoder Beginner Contest 330 振り返り

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

https://atcoder.jp/contests/abc330

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

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

__提出したもの__
```c++: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である必要があるということに気づきました。

__提出したもの__
```c++: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++: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を解消できませんでした。)

__提出したもの__
```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);

    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問題の時もそうですが、実際の形を想像できていれば解けたのではないかと思います。やはり最強のプログラミングツールは紙とペンなのでしょうか...。

__提出したもの(コンテスト後)__
```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参加も検討したいです。
![Screenshot 2023-11-26 at 15.15.16.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1396642/3ab3e0b1-71a1-c0f7-205f-7151f28f2fa2.png)

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