💭

ABC295 参加記録

2023/03/27に公開・約5,000字

AtCoder

tech

ABC295に参加しました。解説と、感想(?)をだらだら書いていきます~~~

コンテスト:

https://atcoder.jp/contests/abc295

A - Probably English

問題概要

英小文字のみからなる文字列 $W_1,W_2,\dots,W_N$ がある。
このうち、少なくとも一つがand,not,that,the,youに一致するか判定してください

解法

一致判定するのが若干めんどくさいので、std::setに追加するとちょっと楽できます

実装

AC:7ms

#include<iostream>
#include <set>
using namespace std;
int main(){
    const set<string> st = {"and", "not", "that", "the", "you"};

    int n;
    cin >> n;
    for (int i = 0; i < n;i++){
        string w;
        cin >> w;
        //stにwが含まれているか?
        if (st.find(w) != st.end()) {
            cout << "Yes\n";
            return 0;
        }
    }
    //stに含まれる要素が存在しない
    //すなわち、"and", "not", "that", "the", "you"のいずれかに一致するようそが無かった
    cout << "No\n";
}

B - Bombs

問題概要

縦 $R$ ,横 $C$ のグリッドがある。
マス $(i,j)$ の情報は文字 $B_{i,j}$ で与えられる。.は空きマス、#は壁、1,2...9はそれぞれ威力 $1,2,...,9$ の爆弾を表す。

次の瞬間、すべての爆弾は同時に爆発します。
爆弾が爆発すると、爆弾の威力が $x$ であるとき、爆弾のマスからマンハッタン距離が $x$ 以下のマスすべてが空きマスになります。

爆発後のマスの状況を出力してください。

$1\leq R,C\leq 20$

解法

$R,C$ ともに十分小さいので、普通にforを回せばいい。めんどくさい...けど、頑張ろう。

実装

AC:9ms

#include <iostream>
#include <vector>
using namespace std;
int main() {
    //入力
    int r, c;
    cin >> r >> c;
    vector<string> s(r);
    for (auto& ss : s) {
        cin >> ss;
    }

    vector<string> ans = s;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            //影響を与えないマスは無視しておく
            if (s[i][j] == '.' || s[i][j] == '#') {
                continue;
            }


            //爆発させる
            int k = s[i][j] - '0';  // 威力
            for (int ii = 0; ii < r; ii++) {
                for (int jj = 0; jj < c; jj++) {
                    if (abs(ii - i) + abs(jj - j) <= k) {
                        ans[ii][jj] = '.';
                    }
                }
            }
        }
    }

    //出力
    for (auto& ss : ans) {
        cout << ss << '\n';
    }
}

C - Socks

問題概要

$N$ 枚の靴下がある。 $i$ 番目の靴下の色は $A_i$ である。
以下の操作が最大で何回行えるか、出力してください。

まだペアになっていない靴下の中から同じ色の靴下を $2$ 枚選んでペアにする。

$1\leq N\leq5\times10^5$
$1\leq A_i\leq10^9$
入力はすべて整数

解法

まず、手元で簡単なケースは実験してみるといい。次のような性質が得られる

色 $i$ の靴下の個数を $c_i$ とする。この時、色 $i$ の靴下同士で作れるペアの個数は $\left\lfloor\frac{c_i}{2}\right\rfloor$

これを使うと、答えは $\sum_{i\in A}{\left\lfloor\frac{c_i}{2}\right\rfloor}$ となる。
ということで、 $c_i$ を求めればよいことになる。これは単に配列で管理するとメモリが死ぬ( $i$ は最大で $10^9$ )
ということで、少し工夫する。求め方は主に二通り

連想配列で管理する
座標圧縮してから管理する

1

まず、連想配列で管理するほうについて。これは知ってればやるだけで、std::mapというのを使う。
これを使えば、普通に管理できる。詳しいことは実装を見てほしい。
計算量は $O(N\log N)$

ちなみに、mapの代わりにunordered_mapを使えば $O(N)$ となる

2

座標圧縮というテク(?)がある。これは、簡単に言えば、各 $A_i$ を

$A_i$ は $A$ の中で何番目に小さいか?(重複は消去して考える)

というのに置き換えるというやつ。例えば $A=(1,10,5,2,4,2)$ とかだと $A=(0,4,3,1,2,1)$ みたいになる。
コードに書くと、次のようになる。

void press(vector<int>& a) {
    vector<int> a_val = a;  // aに入っている要素を全部つっこむ

    //ソートする
    sort(a_val.begin(), a_val.end());
    //重複消去
    a_val.erase(unique(a_val.begin(), a_val.end()), a_val.end());

    for (auto& ai : a) {
        //a_iが何番目か求める(0-index)
        ai = lower_bound(a_val.begin(), a_val.end(), ai) - a_val.begin();
    }
}

これの性質として、以下のようなものがある(というか、これが座標圧縮に要求されている条件)

$A$ を座標圧縮すると $A'$ になるとする。この時、すべての組 $i,j$ に対して

$A_i > A_j \Leftrightarrow A'_i > A'_j$

$A_i = A_j \Leftrightarrow A'_i = A'_j$

$A_i < A_j \Leftrightarrow A'_i < A'_j$

要は、大小関係が全く崩れない。
特に、 $2$ 番目の性質から、与えられる $A$ は座標圧縮してから扱っても問題はないことが分かる。
また、圧縮後には各 $i$ について $A_i < N$ が成り立つ。

Why?

$A'_i$ の定義は

$A_i$ は $A$ の中で何番目に小さいか?(0-index)

なので、 $N$ 番目とかにはなり得ない(あったら $A$ の要素の種類数が $N(=|A|)$ を超えることになっておかしくなっちゃう...)

$A_i<N$ なら、色の管理に必要な配列の長さは $N$ となり配列で管理できる。

計算量は、座標圧縮がボトルネックとなって $O(N\log N)$

実装

map:AC:526 ms

#include<iostream>
#include<map>
using namespace std;
int main() {
    int n;
    cin>>n;
    map<int, int> cnt;

    for (int i = 0; i < n;i++){
        int ai;
        cin >> ai;
        cnt[ai]++;
    }

    long long ans = 0;
    for (auto& [color, count] : cnt) {
        ans += count / 2;
    }

    cout << ans << '\n';
}

座標圧縮:AC:238 ms

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void press(vector<int>& a) {
    vector<int> a_val = a;  // aに入っている要素を全部つっこむ

    //ソートする
    sort(a_val.begin(), a_val.end());
    //重複消去
    a_val.erase(unique(a_val.begin(), a_val.end()), a_val.end());

    for (auto& ai : a) {
        //a_iが何番目か求める(0-index)
        ai = lower_bound(a_val.begin(), a_val.end(), ai) - a_val.begin();
    }
}
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& ai : a){
        cin >> ai;
    }
    press(a);

    vector<int> cnt(n);
    for (auto& ai : a) {
        cnt[ai]++;
    }

    long long ans = 0;
    for (auto& ci : cnt) {
        ans += ci / 2;
    }
    cout << ans << '\n';
}

Discussion

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