A - Attack

問題概要

$A$ から $B$ を引いて $0$ 以下にするための最小の回数を求めよ。

解説

いわゆる割り算切り上げ問題。例えば $A=8,B=2$ のときは $8/2=4$ 回、 $A=8,B=3$ のときは $8/3 + 1 = 3$ 回になります。これを実現する最も簡単な方法は $(a-1)/b+1$ ！

#include <atcoder/all>

using namespace std;
using namespace atcoder;

using lint = long long;

int main()
{
    lint a, b;
    cin >> a >> b;
    cout << (a - 1) / b + 1 << endl;
}

B - Find snuke

問題概要

$5 \leqq H \leqq 100$ , $5 \leqq W \leqq 100$ なる文字のグリッド上に、"snuke"と書かれている部分があるかどうかを判定せよ。
ただし、縦、横、斜めいずれの方向でもよく、上下いずれから始まってもよいものとする（つまり、8方向について調べる必要がある）。

解説

8方向について全探索をしていく問題。方針はそのままだけど、意外と実装が面倒です。特に配列外参照のエラーや探索漏れには注意！

#include <atcoder/all>

using namespace std;
using namespace atcoder;

using lint = long long;

// 全方向
vector<lint> dx_all = {-1, -1, -1, 0, 0, 1, 1, 1};
vector<lint> dy_all = {-1, 0, 1, -1, 1, -1, 0, 1};

// 縦、横、斜めのみ（下から上の方向のみ）
vector<lint> dx_3 = {1, 0, 1};
vector<lint> dy_3 = {0, 1, 1};

// 縦、横のみ
vector<lint> dx_4 = {-1, 0, 1, 0};
vector<lint> dy_4 = {0, -1, 0, 1};


// @brief 特定の文字列が存在する位置を判定
// @return 位置のlist,なければ空list
vector<pair<lint, lint>> find_string_in_grid(const vector<string>& s, const string& target,
                                             const lint direction_amount = 8)
{
    lint x = 0;
    lint y = 0;
    const lint h = s.size();
    const lint w = s[0].length();
    const lint target_length = target.length();

    vector<lint> dx;
    vector<lint> dy;

    switch (direction_amount)
    {
    case 3:
        dx = dx_3;
        dy = dy_3;
        break;
    case 4:
        dx = dx_4;
        dy = dy_4;
        break;
    case 8:
        dx = dx_all;
        dy = dy_all;
        break;
    default: break;
    }

    vector<pair<lint, lint>> res;
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            for (int k = 0; k < direction_amount; k++)
            {
                string cur;
                for (int t = 0; t < target_length; t++)
                {
                    x = i + t * dx[k];
                    y = j + t * dy[k];
                    if ((x < 0) || (x >= h) || (y < 0) || (y >= w)) break;
                    cur += s[x][y];
                }

                if (cur == target)
                {
                    for (int t = 0; t < target_length; t++)
                    {
                        x = i + t * dx_all[k] + 1;
                        y = j + t * dy_all[k] + 1;
                        res.emplace_back(x, y);
                    }
                    return res;
                }
            }
        }
    }

    return {};
}

int main()
{
    lint h, w;
    cin >> h >> w;
    vector<string> s(h);

    for (int i = 0; i < h; i++)
    {
        cin >> s[i];
    }

    vector<pair<lint, lint>> ans = find_string_in_grid(s, "snuke");
    for (auto a : ans)
    {
        cout << a.first << " " << a.second << endl;
    }
}

反省

正直こういう問題にあまり手を付けてなかったので凄く時間がかかったあげく後回ししてしまいました。探索はちゃんとforやdfs()を利用して解くべき！
反省してライブラリに書きました。上のコードは作ったライブラリからコピペしたものです。

https://github.com/Noth827/atc_library_cpp/blob/c91f55ec8f38548017c967731d9555b490385bc2/atc_library_cpp/atc_grid/search.h

C - Almost Equal

問題概要

( $1 \leqq M \leqq 5$ )文字の文字列が( $2 \leqq N \leqq 8$ )個与えられる。このとき、

abcd

abed

bbed

fbed

のように、1文字変化させて次の文字列になり続けるような文字列の並べ方が存在するか判定せよ。

解説

まずは全探索を考えます。すると、 $2 \leqq N \leqq 8$ と非常に小さい制約なので、順列を全探索しても間に合うことが分かります。
つまり、順列全探索をして判定をする問題！
順列全探索についてはこちら(E869120様の記事)を参考にすると分かりやすいです。

#include <atcoder/all>

using namespace std;
using namespace atcoder;

using lint = long long;

int main()
{
    lint n, m;
    cin >> n >> m;
    vector<string> s(n);
    for (int i = 0; i < n; i++)
    {
        cin >> s[i];
    }
    sort(s.begin(), s.end());

    bool res = false;
    do
    {
        bool tempRes = true;
        for (int i = 0; i < n - 1; i++)
        {
            string cur = s[i];
            string nex = s[i + 1];
            lint diff = 0;
            for (int j = 0; j < m; j++)
            {
                if (cur[j] != nex[j]) diff++;
            }

            if(diff != 1) tempRes = false;
        }

        if(tempRes) res = true;
    }
    while (next_permutation(s.begin(), s.end()));

    if(res) cout << "Yes" << endl;
    else cout << "No" << endl;
}

D - Impartial Gift（解けず）

問題概要

( $1 \leqq N \leqq 2\times10^{5}$ )の配列 $A_N$ と、( $1 \leqq M \leqq 2\times10^{5}$ )の配列 $B_M$ がある。それぞれから選んだ値 $A_i, B_j$ について、 $| A_i - B_j | \leqq D$ となるようなものの中から、 $A_i + B_j$ の最大値を求めよ。

ない場合は、-1を出力せよ。

考えたこと

本番ではそもそもほとんど問題見てない（Eが解けそうなのでEに行ったっきりだった）ので時間がある今もう一度考えてみます...
まず、全探索は制約上無理です。
配列の最大値・最小値問題はとにかくsort()した方がいいと思っているので、sort()してみます。すると、右端から順に探索すると取り敢えず和の最大値から調べられることが分かります。
貪欲法も考えてみます。貪欲に最大から調べていきます。
1. $| A_n - B_m | \leqq D$ ならそれが答えになります。
2. 違ったら、との大小を考えます。
  1. $A_n > B_m$ なら、それより $B$ の左を調べる必要はありません。なぜなら、 $A_n - B_j$ の値はどんどん大きくなっていくからです。つまり、 $A$ の添え字を1つ減らせばいいです。
  2. 逆なら、 $A$ と $B$ を逆にして同じことをすればいいです。

これ（結果的に貪欲法ではないけど...）を続ければいつか最大値が更新されるはずなので、これで探索が出来ます。上記の計算量は $O(N+M)$ なので、ソートがボトルネックになりますが、十分間に合います！

#include <atcoder/all>

using namespace std;
using namespace atcoder;

using lint = long long;

template <class T>
bool chmax(T& a, T b)
{
    return ((a < b) ? (a = b, true) : (false));
}

int main()
{
    lint n, m, d;
    cin >> n >> m >> d;
    vector<lint> a(n), b(m);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for (int i = 0; i < m; i++)
    {
        cin >> b[i];
    }

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    lint cur_a_index = n - 1;
    lint cur_b_index = m - 1;
    lint res = -1;
    while (true)
    {
        if (cur_a_index < 0 || cur_b_index < 0) break;

        lint ai = a[cur_a_index];
        lint bi = b[cur_b_index];

        if (ai > bi)
        {
            if (ai - bi <= d)
            {
                chmax(res, ai + bi);
                cur_b_index--;
            }
            else
            {
                cur_a_index--;
            }
        }
        else
        {
            if (bi - ai <= d)
            {
                chmax(res, bi + ai);
                cur_a_index--;
            }
            else
            {
                cur_b_index--;
            }
        }
    }

    cout << res << endl;
}

E - Isolation（ほぼ分かったけど解けず）

問題概要

( $2 \leqq N \leqq 3\times10^{5}$ )頂点 $0$ 辺の無向グラフがあり、 $1$ から $N$ まで番号が付いている。( $1 \leqq Q \leqq 3\times10^{5}$ )個のクエリを処理しながら、各クエリについて「他のどの頂点とも辺で結ばれていない頂点の数」を出力せよ。

【クエリ】

1 u v: uとvを辺で結ぶ（すでに結ばれていることは無い）

2 v: vと他の頂点を結ぶ辺をすべて削除する（vは消えない）

考えたこと

色々考えたけど結局工夫できるところがそんなにないと思ったので、基本はそのままやればいいとは思いました。

毎回頂点数を数えてたら間に合わないのが容易に想像がつきますが、クエリの処理と出力する値の差分に法則性がありそうだと分かり、実際に手を動かしてみると、以下のことが分かります！

法則

クエリ1
- 孤立点同士を結んだら-2
- 1個孤立、もう1個が他とつながってるなら-1
- 両方他と繋がってるなら変動なし
クエリ2
- vが孤立してたら変動なし
- vが他と繋がってたら+1
- vに繋がっている各頂点nvについて、nvがvとしかつながってないなら+1

あとはクエリを実行しながら実際にグラフを更新しつつ、差分を見ていけばいいと分かりますが、普通のgraph = vector<int<int>>だとクエリ2の探索が間に合いません。そこで、自然に考えると、高速に値を見つけたいので、これを解決できるsetを利用することが考えられます。 実際にvector<set<int>>にすれば、値の検索が2分探索で高速に処理できるので、制約にギリ間に合います。

#include <set>
#include <atcoder/all>

using namespace std;
using namespace atcoder;

using lint = long long;
using graph = vector<set<lint>>;

int main()
{
    lint n, q;
    cin >> n >> q;
    graph g(n + 1);

    lint res = n;
    for (int i = 0; i < q; i++)
    {
        lint type;
        cin >> type;
        if (type == 1)
        {
            lint u, v;
            cin >> u >> v;
            g[u].insert(v);
            g[v].insert(u);

            if (g[u].size() == 1 && g[v].size() == 1) res -= 2;
            else if (g[u].size() > 1 && g[v].size() > 1)
            {
                //do nothing
            }
            else res -= 1;

            cout << res << endl;
        }
        else
        {
            lint v;
            cin >> v;
            for (auto nv : g[v]) //(i)
            {
                if (g[nv].size() == 1) res++;
                g[nv].erase(v);
            }

            if (g[v].size() > 0) res++;
            g[v] = {};

            cout << res << endl;
        }
    }
}

反省

本番ではsetの仕様をド忘れして2分探索を書いてしまって、逆に間に合いませんでした。勿体ない...

やはり基礎は大事ですね。

for (auto nv : g[v]) //(i)
{
    if (g[nv].size() == 1) res++;
    auto i = lower_bound(g[nv].begin(), g[nv].end(), v);
    g[nv].erase(i);
}

参考↓ rsk0315.hatenablog.com

Qemelly(けめる)のプログラム備忘録

Unity / AtCoderについて書きます

【AtCoder】ABC302 A~Eの解説・反省

A - Attack

問題概要

解説

B - Find snuke

問題概要

解説

反省

C - Almost Equal

問題概要

解説

D - Impartial Gift（解けず）

問題概要

考えたこと

E - Isolation（ほぼ分かったけど解けず）

問題概要

考えたこと

法則

反省