2020-06-13

AtCoder Regular Contest 005 C - 器物損壊！高橋君

問題

スタート地点からゴール地点まで到達可能かを判断するよくあるグリッドBFSなのですが、今回は2回まで壁を壊していいとのこと。

atcoder.jp

考察

今回は幅優先探索はある程度知っている体で説明していきます。
そもそも幅優先探索ってなに？っていう方はこちらのけんちょんさんの記事に分かりやすく書いてあります。

qiita.com また、グリッドBFSの実装についてはこの問題を参考にしてみてください。

atcoder.jp

さて、今回は普通のBFSとは違い通路の移動にはコストはかからず、壁を壊すときにのみ1のコストが発生します。
なので 0-1-BFS というものを使います。（私もこの問題で知りました）

方針

探索の仕方は普通のBFSと同じなのですが、queueへの追加の仕方が異なります。
今回は通路の移動のコストがかからないので通路を優先して探索する必要があります。
そのため、今回はqueueではなくdequeを使います。
通路の座標は優先して探索する必要があるためdequeの先頭に追加し、壁の座標は通常通りdequeの末尾に追加します。
コスト0の移動から優先して探索するのであとから最小値が再び更新されることはなくまた同じマスからの探索をせずに済みます。
このことを除けばあとは普通のBFSになります。

実装

上記のことを実装していきます

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int h, w;
    int sy, sx;
    int gy, gx;
    int dy[] = {-1, 0, 0, 1};
    int dx[] = {0, -1, 1, 0};

    cin >> h >> w;

    //各座標への移動コストを大きい値で初期化
    vector<vector<int>> cost(h, vector<int>(w, 9999));
    //各座標が壁か通路か
    vector<vector<char>> area(h, vector<char>(w));

    //迷路の入力
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            cin >> area[i][j];
            //スタート座標, ゴール座標をメモする
            if(area[i][j] == 's') sy = i, sx = j;
            else if(area[i][j] == 'g') gy = i, gx = j;
        }
    }

    //今回はdequeなことに注意
    deque<pair<int, int>> q;

    //スタート地点の座標をpushしcostを0にする
    q.push_back({sy, sx});
    cost[sy][sx] = 0;

    while(!q.empty()){
        //dequeの先頭のこれから探索する座標
        int y = q.front().first;
        int x = q.front().second;
        q.pop_front();
        for(int i = 0; i < 4; i++){
            //次に探索する座標
            int ny = y + dy[i];
            int nx = x + dx[i];
            //座標が不適当なら探索しない
            if(ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
            //探索先が壁で, 移動costを更新するとき
            if(area[ny][nx] == '#' && cost[y][x] + 1 < cost[ny][nx]){
                cost[ny][nx] = cost[y][x] + 1;
                q.push_back({ny, nx});
            }
            //探索先が壁ではなく, 移動costを更新するとき
            else if(area[ny][nx] != '#' && cost[y][x] < cost[ny][nx]){
                cost[ny][nx] = cost[y][x];
                q.push_front({ny, nx});
            }
        }
    }

    //ゴール地点の移動costが2以下ならYES
    if(cost[gy][gx] <= 2) cout << "YES\n";
    else cout << "NO\n";

    return 0;
}

したがってBFS時の探索予定先の追加方法を少し応用することでこの問題を解くことが出来ました。

2020-05-10

AtCoder Grand Contest 023 A - Zero-Sum Ranges

$200$ 点問題最強といわれたZero-Sum Rangesを倒しましょう

問題概要

atcoder.jp

長さ $N$ の数列 $A$ の中で、和が $0$ になる区間はいくつあるか。ただし値が同じでも位置が違うなら異なるものとする。

例）
$N=6$
$A=\{1, 3, -4, 2, 2, -2\}$

$(1, 3, -4)$
$(-4, 2, 2)$
$(2, -2)$
この $3$ つの区間の和はそれぞれ $0$ になるので、この場合出力する答えは $3$ になります。

考察

$N$ の最大値は $2×10^{5}$ なので、愚直に探索しては $O(N^{2})$ になってしまい間に合いません。

区間和を扱うには累積和が便利なので累積和を使いましょう。

累積和をとった時に和が $0$ になる区間はどうなるのかというと、累積和の値が等しくなります。

ということは、まず累積和をとったあとに各値がいくつあるのかを数えます。

そして区間の数ということは、その同じ値の中から $2$ つを選ぶ場合の数なので、各値の数を $M$ とすると、各値の ${} _ M C _ 2$ の総和が答えとなります。

そして、 ${} _ M C _ 2$ は $\frac{M(M-1)}{2}$ でも求められるのですが、これはまた $1$ ~ $M-1$ の総和でもあるので、以下のように実装することも出来ます。

long long ans = 0;
map<long long, int> m;
//累積和をとった0項目は0とするので加算する
m[0]++;

for(int i = 1; i < n + 1; i++){
    //出てくるを数える前に答えに加算する
    ans += m[a[i]];

    //出てくる数を数える
    m[a[i]]++;
}

$map$ を使って各値が出てくる回数を数えるのですが、 $M$ 回出てきた値に対して $1$ ~ $M-1$ の総和を求めるので、先に答えの変数に出てきた数を加算してから出てくる数を数えることで、上手に $1$ ~ $M-1$ の総和を求めることが出来ます。

実装

よって今までのことを実装すると以下のようになります。

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    long long ans = 0;
    vector<long long> a(n+1);
    map<long long, int> m;
    //累積和をとった0項目は0とするので加算する
    m[0]++;
    for(int i = 1; i < n + 1; i++){
        cin >> a[i];
        //累積和をとる
        a[i] += a[i-1];
        //出てくるを数える前に答えに加算する
        ans += m[a[i]];
        //出てくる数を数える
        m[a[i]]++;
    }
    cout << ans << endl;
}

先ほどの方法で ${} _ M C _ 2$ を求めたので、入力と同時に累積和をとりながら答えも求めることが出来ました。

2020-04-16

AtCoder Beginner Contest 133 D - Rain Flows into Dams

解説PDFが微妙に見づらかったので自分用にまとめました。

問題概要

atcoder.jp

円形に山が並びその間にたまった水の量が入力される。山に降った雨は左右のダムに均等に流れ込む。各ダムに流れこんだ水の量を参考にして各山に降った雨の量を求める。

f:id:amami0522:20200416172704p:plain — 概要図

各ダムに流れ込んだ $A _ i$ をもとに $x _ i$ を求める。

考察

各 $A _ i$ についての方程式をたててn元連立方程式を解けばこの問題は解けるのですが、それでは間に合わないので上手くできないか考えます。

試しに1つ目の山に降った雨の量を $x$ とおいてみます。そして基準にした $x$ から時計回りに各値を求めていくと最終的に $x$ は以下のようになることが分かります。

f:id:amami0522:20200416182913p:plain — X を基準に時計回りに各値を求める

図の左上にあるとおり、 $x$ 自身は、基準にした $x$ から見て奇数番目の $A _ i$ を足して、偶数番目の $A _ i$ を引いた値になることが分かりました。（制約より、ダムの数は奇数なのでこれが成り立つ）

これで基準となる $x _ 1$ が求まったので、あとは各 $x _ i$ $(2 \leq i \leq N)$ について、ダム $i$ には山 $i$ と $i-1$ の降水量の半分ずつが均等に水が流れてくることから
$A _ {i} = \frac{x _ {i-1}}{2} + \frac{x _ {i}}{2}$ より

$x _ {i} = 2A _ {i}-x _ {i-1}$

の漸化式を求めていけば̪各値が求まります。

実装

上記のことを実装すると以下のようになります。

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);    //各ダムの降水量
    vector<int> ans(n);  //各山の降水量
    for(int i=0;i<n;i++){
        cin >> a[i];
        //基準のとなる山の降水量を求める
        //奇数番目は足して偶数番目は引く
        if(i%2==0) ans[0] += a[i];
        else ans[0] -= a[i];
    }
    for(int i=1;i<n;i++){
        //漸化式をもとに代入
        ans[i] = 2*a[i-1]-ans[i-1];
    }
    for(auto&& e:ans) cout << e << " ";
    cout << "\n";
    return 0;
}

終わりに

こういった数学系は、実装はそんなに難しくないけど自分はその発想に至るまでの時間が結構かかるのでもっと慣れていきたいです。

2020-04-09

AtCoder Beginner Contest 156 D - Bouquet

解説放送ではライブラリを使って解いていたので自分用にまとめてみました

問題概要

$n$ 種類の花の中から $1$ 本以上を選ぶ場合の数を求める。
ただし、ちょうど $a , b$ 本になる場合は除く。
また、答えが非常に大きくなることがあるので $(10^{9}+7)$ で割った値を出力する。

atcoder.jp

考察

この問題、答えとなる数式自体は簡単で、 $2^{n}-1-nC _ {a}- nC _ {b}$ となり最終的にこれを求めることになります。

$2^{n}$ : すべての花の選び方
$1$ : $0$ 本選ぶの時の場合の数
$nC _ {a} , nC _ {b}$ : $n$ 本の花から $a , b$ 本選ぶ場合の数

ここで、 $2^{n}$ は、繰り返し2乗法を使えば高速に求められます。
しかし、問題なのは $nC _ {a} , nC _ {b}$ の方です。

組み合わせの公式を用いると

$\displaystyle{ nC _ {r} = \frac{n(n-1)(n-2)...(n-r+1)}{r!} }(mod10^{9}+7)$

となっていて、除算が含まれます。この場合普通に $mod$ をとることが出来ません。

除算で $mod$ をとる場合には逆元というものを用いることで求めることができます。

フェルマーの小定理より
$p$ を素数、 $a$ を $p$ の倍数でない任意の整数としたとき
$a^{p-1}\equiv1$ $(mod$ $p)$

これより
$a^{p-2}\equiv\frac{1}{a}$ $(mod$ $p)$

となるので、先ほどの組み合わせの公式 $\frac{1}{r!}$ $(mod10^{9}+7)$ が $r!^{10^{9}+7-2}$ $(mod10^{9}+7)$ と等価であるとみることが出来ます。

以上のことから求める式が以下のようになります

$\displaystyle{ nC_{r}=(n(n-1)(n-2)...(n-r+1))r!^{10^{9}+7-2} }(mod10^{9}+7)$

これで除算が消えたので $mod$ をとって計算することが出来ます。

実装

これまでのことを実装すると以下のようになります

#include<bits/stdc++.h>
using namespace std;

const int mod = 1000000007;

//繰り返し2乗法
long long powmod(long long a, long long b){
    long long c = 1;
    while(b){
        if(b & 1) c = a * c % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return c;
}

//組み合わせを求める
long long nCr(long long n, long long r){
    long long x = 1, y = 1;
    //x : n*(n-1)*(n-2)*...*(n-r+1)
    //y : r!
    for(int i = 0; i < r; i++){
        x = x * (n - i) % mod;
        y = y * (i + 1) % mod;
    }
    //逆元をかけてmodをとる
    return x * powmod(y, mod - 2) % mod;
}

int main()
{
    long long n, a, b;
    cin >> n >> a >> b;
    long long ans = powmod(2, n) - 1 - nCr(n, a) - nCr(n, b);

    //引き算なのでmodの取り方に注意
    cout << (ans % mod + mod) % mod << endl;
    return 0;
}

答えを求める式が引き算なので、最後の $mod$ のとり方に注意して出力すれば終了です。

参考にした資料

qiita.com

最後に

今までは $nC _ {r}(mod10^{9}+7)$ を求める時には、二項係数の $mod$ テーブルを使って求めていたけど、 $n$ が大きい場合については使うことが出来ないので、今回のこの問題で逆元について知れて良かったと思いました。