A - Similar String

問題概要

S,Tが同じ文字列か判定せよ。ただし、1とl、0とoは同じものとする。

解説

愚直に同じかどうか判定する関数を作って、1つでもfalseを返したらNoを出力するようにします。

こういうときは、forループの前にbool ok = trueみたいなものを用意しておいて、1つでも条件に一致しなかったらok = falseを代入してやるとシンプルな実装になりやすいです！

#include <atcoder/all>

using namespace std;
using namespace atcoder;

using lint = long long;

bool same(const char st, const char tt)
{
    if (st == tt) return true;
    else if (st == 'l' && tt == '1') return true;
    else if (st == 'o' && tt == '0') return true;
    else if (st == '0' && tt == 'o') return true;
    else if (st == '1' && tt == 'l') return true;
    else return false;
}

int main()
{
    int n;
    cin >> n;
    string s, t;
    cin >> s >> t;
    bool ok = true;
    for (lint i = 0; i < s.size(); i++)
    {
        if (!same(s[i], t[i])) ok = false;
    }

    cout << (ok ? "Yes" : "No") << endl;
}

反省

最初is_same()という名前にしたらコンパイラに怒られました。今度からはis_ok()とかにしようかな...

B - Discord

問題概要

$(2\leq N\leq 50)$ までの連番がある。 $(1\leq M\leq 50)$ 個の数字列が与えられるので、一度も隣り合わせになっていない番号の組の個数を求めよ。

なお、数字列の長さは $N$ であり、必ず1回ずつ数字が出現する。

解説

B問題にしてはちょっと難しいと思いました...

制約は小さいので「やるだけ問題」なのは間違いないのですが、一度も隣り合わせになっていない番号をカウントする方法をちょっと考えさせられました。

私は、 $N*N$ の二次元配列を用意しておいて、総当たり戦の表みたいに管理することを考えました。隣り合う番号 $a,b$ について、ans[a][b]とans[b][a]両方をプラスしておけば、隣り合ったやつは見つけられるはずです。あとは探索範囲を限定してやれば、正しい答えが出力されます！（答えを2で割ってもいいと思います）

このように、順不同のものを管理したいときは、2次元配列や2つの配列を用意するのが有用なことがあると思っています。

私は最初にすべての選び方を計算してから隣り合わせの人を見つけるたびに-1していきましたが、普通に隣り合わせじゃない人を見つけるたびに0から増やした方がいいと思います。

#include <atcoder/all>

using namespace std;
using namespace atcoder;

using lint = long long;

int main()
{
    lint n, m;
    cin >> n >> m;
    vector<vector<lint>> ans(n, vector<lint>(n)); // ans[i][j] と ans[j][i]にiとjが隣り合わせであるかどうかの情報を格納
    vector<vector<lint>> a(m, vector<lint>(n));
    for (lint i = 0; i < m; i++)
    {
        for (lint j = 0; j < n; j++)
        {
            cin >> a[i][j];
            a[i][j]--;
        }
    }

    for (lint i = 0; i < m; i++)
    {
        for (lint j = 0; j < n - 1; j++)
        {
            lint left = a[i][j];
            lint right = a[i][j + 1];
            ans[left][right]++;
            ans[right][left]++;
        }
    }

    lint cnt = n * (n - 1) / 2; // 全ての選び方
    for (lint i = 0; i < n; i++)
    {
        for (lint j = i + 1; j < n; j++) // ダブらないように探索範囲を限定
        {
            if (ans[i][j] > 0) cnt--;
        }
    }
    cout << cnt << endl;
}

C - Dash

問題概要（多分ちゃんと問題見た方がいい）

二次元平面と点 $T(0,0)$ がある。最初Tの体力は $H$ である。以下の操作にて、体力が負になったらNoを出力せよ。最後まで負にならなかったらYesを出力せよ。

$(1\leq N\leq 2\times 10^{5})$ 回、4方向いずれかの1マス分のグリッド移動をする(文字列のRLUDで与えられる)。
移動ごとに体力が $-1$ される。
$(1\leq M\leq 2\times 10^{5})$ 個の体力回復アイテムが各 $i$ に対して点 $(x_i,y_i)$ に存在する。Tの体力が $K$ 未満のときに到達すると、そのアイテムを消費して $K$ まで回復する。そうでないときは消費もせず、回復もしない。

解説

問題がややこしい！勝手に解釈をミスってWAしそうな問題なので注意したい。

間違いなくシミュレーション系の問題なので、とりあえず愚直に実装していきます。

#include <atcoder/all>

using namespace std;
using namespace atcoder;

using lint = long long;

lint n, m, h, k;
string s;
vector<pair<lint, lint>> co;

int main()
{
    cin >> n >> m >> h >> k;
    cin >> s;
    for (int i = 0; i < m; i++)
    {
        lint x, y;
        cin >> x >> y;
        co.push_back(make_pair(x, y));
    }

    lint cur_x = 0;
    lint cur_y = 0;
    lint cur_health = h;
    bool ok = true;
    for (lint i = 0; i < n; i++)
    {
        const auto move = s[i];
        cur_health--;
        if (cur_health < 0)
        {
            ok = false;
            break;
        }

        if (move == 'L') cur_x--;
        else if (move == 'R') cur_x++;
        else if (move == 'U') cur_y++;
        else if (move == 'D') cur_y--;

        if (/*アイテムが今の座標にあったら*/)
        {
            if (cur_health < k)
            {
                // アイテムを消す
                cur_health = k;
            }
        }
    }

    cout << (ok ? "Yes" : "No") << endl;
}

問題は座標の探索/検索ですが、探索と言えばまずは二分探索。座標を先にソートして二分探索すると、全体の計算量は $O(N\log N)$ となって間に合いそうです。

C++には勝手にデータを平衡二分探索木として整理してくれるset()というライブラリがあるので、それを使うのが一番手っ取り早いです。

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

using namespace std;
using namespace atcoder;

using lint = long long;

lint n, m, h, k;
string s;
set<pair<lint, lint>> co;

int main()
{
    cin >> n >> m >> h >> k;
    cin >> s;
    for (int i = 0; i < m; i++)
    {
        lint x, y;
        cin >> x >> y;
        co.push_back(make_pair(x, y));
    }

    lint cur_x = 0;
    lint cur_y = 0;
    lint cur_health = h;
    bool ok = true;
    for (lint i = 0; i < n; i++)
    {
        const auto move = s[i];
        cur_health--;
        if (cur_health < 0)
        {
            ok = false;
            break;
        }

        if (move == 'L') cur_x--;
        else if (move == 'R') cur_x++;
        else if (move == 'U') cur_y++;
        else if (move == 'D') cur_y--;

        if (co.find(make_pair(curx, cury)) != co.end())
        {
            if(cur_health < k)
            {
                co.erase(make_pair(curx, cury));
                cur_health = k;
            }
        }
    }

    cout << (ok ? "Yes" : "No") << endl;
}

D - Shift vs. CapsLock

問題概要

A,aからなる長さ $1\leq |S| \leq 3 \times 10^{5}$ の文字列 $S$ が与えられる。これをキーボード入力する際、以下の $X$ , $Y$ , $Z$ が与えられるので、かかる時間の最小値を出力せよ。

$X$ : aキー入力時間 $Y$ : Shift+aキー入力時間 $Z$ : CapsLockキー入力時間

解説

まずは全探索を考えますが、 $O(3^{|S|})$ になるので無理です。貪欲法も考えますが、できないです。貪欲に選べる選択肢がありません。

今回は、dp(動的計画法)を利用したいです。というのも、dpは必要最低限の情報を保存しながら探索するのにうってつけの方法であり、今回の「CapsLockがオンかどうか」を管理するのにぴったりだからです！

そこで、

dp[i][j] := j文字目までの最短時間(iはCapsLockがonのとき1,offのとき0)

とします。こうすれば、CapsLockの情報を管理しながら最小値の更新が出来ます！

#include <atcoder/all>

using namespace std;
using namespace atcoder;

using lint = long long;

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

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

lint x, y, z;
string s;
lint dp[2][300010]; //dp[i][j] := i文字目までの最短時間,jはcapsがonのとき1,offのとき0

int main()
{
    cin >> x >> y >> z >> s;

    // dpの初期化
    for (lint i = 0; i < 2; i++)
    {
        for (lint j = 0; j < 300010; j++)
        {
            dp[i][j] = 1e18;
        }
    }

    dp[0][0] = 0;
    dp[1][0] = z; // 最初CapsLockをつけるのにzかかる
    for (lint i = 0; i < s.size() + 1; i++)
    {
        bool isA = (s[i] == 'A');
        if (isA) // 大文字のとき
        {
            dp[0][i + 1] = min(dp[0][i] + y, dp[1][i] + x + z);
            dp[1][i + 1] = min(dp[1][i] + x, dp[0][i] + y + z);
        }
        else // 小文字のとき
        {
            dp[0][i + 1] = min(dp[0][i] + x, dp[1][i] + y + z);
            dp[1][i + 1] = min(dp[1][i] + y, dp[0][i] + x + z);
        }
    }

    lint res = min(dp[0][s.size()], dp[1][s.size()]);
    cout << res << endl;
}

反省

最初res = min(dp[0][s.size()], dp[1][s.size()])とせずにdp[0][s.size()]を出力していたせいでサンプルが正しくならなくて焦りました。

先に出力したい値を書いておく方が方針も見えやすくなるし、ミスりにくくなるしで一石二鳥な気がするので、以降そうします。

E - A Gift From the Stars（解けず）

問題概要

以下の条件を満たす $k+1$ 頂点 $k$ 辺のグラフをレベル $k (k \geq 2)$ の星と呼ぶ。

$1$ つの頂点が、他の $k$ 個の頂点と $1$ 本ずつ辺で結ばれており、それ以外の辺は存在しない。

最初、ランダムな個数の（それぞれのレベルもランダムな）星がある。すべてのグラフの頂点が連結になるまで星の端を結ぶ辺を張る。

この操作後のグラフ（頂点数は $(1\leq N\leq 2\times 10^{5})$ 、辺数は $N-1$ ）の情報が与えられるので、最初の星の個数とレベルを復元して出力せよ。

解説

なんだか色々やり方がありそうな問題です。一旦状況を整理してみます。

分かりやすい例で考えてみると、こんな感じのグラフからオレンジとその次数を復元したいです。

]]

グラフ問題は安易に構築せずに、構築段階で工夫できることがないかを考えるのが重要だと思います。単純に、次数が違うことで判断できることを考えると、構築の段階で出現回数が一定（具体的には3つ）以上の頂点についてはその時点でオレンジになるはずです！

問題は、サンプルケース1のように、レベル２の星が含まれるときです。これをどう扱うかが本問の最も難しいところ...。

私は木の端からdfs()をしながら、次数が2の部分が連続して3回続いたらレベル2の星が1個あるはずだと思ってお祈り実装してみるとACしました！

#include <atcoder/all>

using namespace std;
using namespace atcoder;

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

int height[200100]; // -1 means not visited
int max_length = -1;
// 端点
int max_at = -1;

bool seen[200100];

// 木の端点を見つけるためのdfs
void dfs_length(const graph& g, const int v)
{
    for (const auto nv : g[v])
    {
        if (height[nv] != -1) continue;

        height[nv] = height[v] + 1;
        if (height[nv] > max_length)
        {
            max_length = height[nv];
            max_at = nv;
        }

        dfs_length(g, nv);
    }
}

// レベル２のカウント
lint cnt_2 = 0;

void dfs(const graph& g, const int v, int cnt)
{
    lint size = g[v].size();
    if (size <= 2) cnt++;
    seen[v] = true;
    
    if (cnt >= 3)
    {
        cnt_2++;
        cnt = 0;
    }
    
    for (const auto nv : g[v])
    {
        if (seen[nv]) continue;

        if (size <= 2)
        {
            dfs(g, nv, cnt);
        }
        else
        {
            dfs(g, nv, 0);
        }
    }
}

int main()
{
    lint n;
    cin >> n;
    graph g(n);
    vector<lint> c(n);
    for (int i = 0; i < n - 1; i++)
    {
        lint a, b;
        cin >> a >> b;
        a--;
        b--;
        g[a].push_back(b);
        c[a]++;
        g[b].push_back(a);
        c[b]++;
    }

    for (lint i = 0; i < n; i++)
    {
        height[i] = -1;
    }
    height[0] = 0;
    dfs_length(g, 0);
    dfs(g, max_at, 0);

    vector<lint> res;
    for (lint i = 0; i < n; i++)
    {
        if (c[i] >= 3) res.push_back(c[i]);
    }
    for (lint i = 0; i < cnt_2; i++)
    {
        res.push_back(2);
    }

    sort(res.begin(), res.end());
    for (lint i = 0; i < res.size(); i++)
    {
        cout << res[i] << " ";
    }
    cout << endl;
}

反省

ACしました...コンテスト終了8秒後に。

D問題で変なミスしてなければ解けたのにな...。まだまだ1問にかかっている時間が長いのは何とかしたいですね。

あと、解説読んでなるほどなーとなりました。

要するに、ここまでグラフの制約が厳密で決定論的だと、簡単な解法が出やすいように感じます。

レベル3以上の星を見つけた後、残りの頂点数を数えればレベル2も計算できるというのが目から鱗でした。確かにレベル2の星の数はレベル3の星以外の数なので、普通に余事象で解けるというわけですね。

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

Unity / AtCoderについて書きます

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

A - Similar String

問題概要

解説

反省

B - Discord

問題概要

解説

C - Dash

問題概要（多分ちゃんと問題見た方がいい）

解説

D - Shift vs. CapsLock

問題概要

解説

反省

E - A Gift From the Stars（解けず）

問題概要

解説

反省