2024-04-09

競プロ精選 100 問 by C++<高速なべき乗計算>

精選100問

はじめに

べき乗大好きです 2問やります

70　NTL_1_B - べき乗

問題はこちらです！
問題文↓

m,nが与えられるので、mⁿを求めてください

繰り返し二乗法をします！
コードはこんな感じです

#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using namespace chrono;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i <= (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
ll smallMOD = 998244353;
ll bigMOD = 1000000007;
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

ll repeated_squaring(ll x, ll y, ll z = bigMOD)
{
    ll ans = 1;
    bitset<64> bits(y);
    string bit_str = bits.to_string();
    reverse(all(bit_str));
    rep(i, 64)
    {
        if (bit_str[i] == '1')
            ans = ans * x % z;
        x = x * x % z;
    }
    return ans;
}

int main()
{
    ll n, m;
    cin >> n >> m;
    cout << repeated_squaring(n, m) << endl;
    return 0;
}

repeated_squaring関数をライブラリとして持っておくと強い

71　Square869120Contest #1 E - 散歩

問題はこちらです！
問題文↓

N個の頂点があり、街i-1とiが結ばれているパスグラフがある
i-1とiの距離はA[i-1]^A[i]である
Q個のクエリが与えられる
初め頂点0からスタートして、0→C[0]→C[1]→...→C[Q-1]→0となるように移動する時、距離の総和を求めてください

まず、全ての頂点間の距離を繰り返し二乗法で求めます
そしたら、クエリを処理するためにLからRまでの区間の和を求めたいです
区間の和といえば累積和なので、累積和テーブルを作成し、O(1)で区間の和を求めます
したがってO(N+Q)で求めることができました
コードはこんな感じです

#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using namespace chrono;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i <= (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
ll smallMOD = 998244353;
ll bigMOD = 1000000007;
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

ll repeated_squaring(ll x, ll y, ll z = bigMOD)
{
    ll ans = 1;
    bitset<64> bits(y);
    string bit_str = bits.to_string();
    reverse(all(bit_str));
    rep(i, 64)
    {
        if (bit_str[i] == '1')
            ans = ans * x % z;
        x = x * x % z;
    }
    return ans;
}

int main()
{
    ll n, q;
    cin >> n >> q;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];

    // 距離を計算.
    vector<ll> dist(n - 1);
    rep(i, n - 1)
    {
        dist[i] = repeated_squaring(a[i], a[i + 1]);
    }

    // 区間の和といえば累積和.
    vector<ll> sum(n);
    sum[0] = 0;
    rep(i, n - 1)
    {
        sum[i + 1] = sum[i] + dist[i];
    }

    // クエリ処理.
    ll now = 0;
    ll ans = 0;
    rep(i, q)
    {
        ll go;
        cin >> go;
        ans += abs(sum[go - 1] - sum[now]);
        ans %= bigMOD;
        now = go - 1;
    }
    ans += abs(sum[0] - sum[now]);
    ans %= bigMOD;
    cout << ans << endl;
    return 0;
}

LとRは大きさが逆になることもあるので注意(ここでは絶対値を取りました)

おわり

べき乗マスターになりましたー
ではまた！
、、、区間DPは知らない子です(いつかやります)

2024-04-02

競プロ精選 100 問 by C++<高速な素数判定法>

精選100問

はじめに

ちょっと休憩程度に68、69をします(簡単っぽそうだった)

68　NTL_1_A - 素因数分解

問題はこちらです！
問題文↓

Nが与えられるので、素因数分解してください
出力形式は`${N}:`に続き各素因数の前に空白(スペース)を入れてください
例えば、12: 2 2 3などです

素因数分解の関数を入れてたら簡単に出来ます
コードはこんな感じです

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i <= (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
ll smallMOD = 998244353;
ll bigMOD = 1000000007;
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

void prime_factorize(ll N, vector<pair<ll, ll>> &res)
{
    for (ll p = 2; p * p <= N; ++p)
    {
        if (N % p != 0)
            continue;
        int e = 0;
        while (N % p == 0)
        {
            ++e;
            N /= p;
        }
        res.emplace_back(p, e);
    }
    if (N != 1)
    {
        res.emplace_back(N, 1);
    }
}

int main()
{
    ll n;
    cin >> n;
    vector<pair<ll, ll>> res;
    prime_factorize(n, res);
    cout << n << ":";
    rep(i, res.size())
    {
        rep(j, res[i].second)
        {
            cout << " " << res[i].first;
        }
    }
    cout << endl;
    return 0;
}

ライブラリ入れているので簡単でしたー

69　AtCoder Beginner Contest 084 D - 2017-like Number

問題はこちらです！
問題文↓

Nも(N+1)/2も素数を満たす奇数Nを2017に似た数とします
区間L,Rにおいて、2017に似た数はいくつありますか？

制約が1e5までなので、そこまでの2017に似た数を全探索します
次に、区間の和として捉えて、累積和を作成することで、O(N+Q)で解くことが出来ました
コードはこんな感じです

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i <= (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
ll smallMOD = 998244353;
ll bigMOD = 1000000007;
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

bool isPrime(ll n)
{
    if (n == 1)
        return false;
    for (ll i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}

int main()
{
    // 先に2017に似た数を作る.
    map<ll, bool> like2017;
    rep(i, 1e5)
    {
        if (isPrime(i + 1) && (i + 2) % 2 == 0 && isPrime((i + 2) / 2))
        {
            like2017[i + 1] = true;
        }
    }
    // 区間の個数の累積和を作る.
    vector<ll> like2017sum(1e5 + 1, 0);
    rep(i, 1e5)
    {
        like2017sum[i + 1] = like2017sum[i] + like2017[i + 1];
    }
    // クエリを処理する.
    ll q;
    cin >> q;
    rep(i, q)
    {
        ll l, r;
        cin >> l >> r;
        cout << like2017sum[r] - like2017sum[l - 1] << endl;
    }
    return 0;
}

最後に

次こそは区間DPをしたい
無理だったらべき乗の計算に逃げる

2024-03-26

競プロ精選 100 問 by C++<動的計画法：ナップザック DP またはその亜種>

はじめに

今回は、39から45の7問解きました！ちゃんとcopilotなしでやりました(当たり前)

39　JOI 2011 予選 4 - 1 年生

問題はこちらです！
問題文↓

数列が与えられ、その間に+か-を入れていく
途中、「0未満になる」または「20を超える」ことのない式は何通りか

これは、縦N-1(数列の間の個数)、横21(0を含む)のDPを作成しました
もし、0未満、20を超えることがでたらDPに書き込まないようにすれば終わりです
コードはこんな感じです

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define Rep(i, n, a) for (int i = (a); i < (n); ++i)
#define All(a) (a).begin(), (a).end()
#define YesNo(b) ((b) ? "Yes" : "No")
using LL = long long;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int smallMOD = 998244353;
int bigMOD = 1000000007;

int main()
{
    int n;
    cin >> n;
    vector<int> A(n);
    rep(i,n) cin>>A[i];
    vector<vector<LL>> dp(n-1,vector<LL>(21));
    dp[0][A[0]] = 1;
    rep(i,n-2){
        rep(j,21){
            if(j-A[i+1]>=0){
                dp[i+1][j-A[i+1]]+=dp[i][j];
            }
            if(j+A[i+1]<=20){
                dp[i+1][j+A[i+1]]+=dp[i][j];
            }
        }
    }
    cout << dp[n-2][A.back()] << endl;
    return 0;
}

40　JOI 2012 予選 4 - パスタ

問題はこちらです！
問題文↓

3種類のパスタがある
3日以上同じパスタが来ないようにN日間パスタを食べるには何通りの方法があるか

3次の配列のDPです！
DP[i][j][k]として、、、
i:n日間
j:3種類のパスタ
k:連続した日数(2日まで)
となり、DP[n][3][2]を作成しました
コードはこんな感じです

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
ll smallMOD = 998244353;
ll bigMOD = 1000000007;

// 0,1,2のリストからx以外の数字のペアを返す.
pair<int, int> f(int x)
{
    if (x == 0)
    {
        return make_pair(1, 2);
    }
    else if (x == 1)
    {
        return make_pair(0, 2);
    }
    else
    {
        return make_pair(0, 1);
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> A(120, -1);
    rep(i, m)
    {
        int a, b;
        cin >> a >> b;
        A[a - 1] = b - 1;
    }
    vector<vector<vector<int>>> dp(n, vector<vector<int>>(3, vector<int>(2, 0)));
    if (A[0] == -1)
    {
        dp[0][0][0] = 1;
        dp[0][1][0] = 1;
        dp[0][2][0] = 1;
    }
    else
    {
        dp[0][A[0]][0] = 1;
    }
    rep1(i, n)
    {
        if (A[i] == -1)
        {
            // 計15本の遷移.
            rep(j, 3)
            {
                auto p = f(j);
                dp[i][j][0] += dp[i - 1][p.first][0] + dp[i - 1][p.first][1] + dp[i - 1][p.second][0] + dp[i - 1][p.second][1];
                dp[i][j][0] %= 10000;
            }
            rep(j, 3)
            {
                dp[i][j][1] += dp[i - 1][j][0];
                dp[i][j][1] %= 10000;
            }
        }
        else
        {
            // 計5本の遷移.
            dp[i][A[i]][1] += dp[i - 1][A[i]][0];
            dp[i][A[i]][1] %= 10000;
            auto p = f(A[i]);
            dp[i][A[i]][0] += dp[i - 1][p.first][0] + dp[i - 1][p.first][1] + dp[i - 1][p.second][0] + dp[i - 1][p.second][1];
            dp[i][A[i]][0] %= 10000;
        }
    }
    ll ans = 0;
    rep(i, 3)
    {
        ans += dp[n - 1][i][0] + dp[n - 1][i][1];
        ans %= 10000;
    }
    cout << ans << endl;
    return 0;
}

ちょっと慣れてきた！

41　JOI 2013 予選 4 - 暑い日々

問題はこちらです！
問題文↓

服の着ることができる"気温"と服の"派手さ"と、毎日の気温が与えられる
毎日の服を選ぶ時、1日前と今日との服の派手さの差の絶対値が最大になるように着ていきたい
この派手さの最大のコストを求めてください
ただし、服の気温に適した気温で無いと着ることが出来ません

DP[i][j]とすると、、、
i:D日間の派手さのステート
j:N種類の服のステート
のようにDP[D][N]を作成しました！
コードはこんな感じです

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
ll smallMOD = 998244353;
ll bigMOD = 1000000007;

bool canWear(ll a, ll b, ll t)
{
    return a <= t && b >= t;
}

int main()
{
    ll D, N;
    cin >> D >> N;
    vector<ll> T(D);
    rep(i, D) cin >> T[i];
    vector<vector<ll>> ABC(N, vector<ll>(3));
    rep(i, N) cin >> ABC[i][0] >> ABC[i][1] >> ABC[i][2];
    vector<vector<ll>> dp(D, vector<ll>(N, 0));
    rep1(i, D)
    {
        rep(j, N)
        {
            if (canWear(ABC[j][0], ABC[j][1], T[i - 1]))
            {
                rep(k, N)
                {
                    dp[i][k] = max(dp[i][k], dp[i - 1][j] + abs(ABC[j][2] - ABC[k][2]));
                }
            }
        }
    }
    ll ans = 0;
    rep(i, N)
    {
        if (canWear(ABC[i][0], ABC[i][1], T[D - 1]))
            ans = max(ans, dp[D - 1][i]);
    }
    cout << ans << endl;
    return 0;
}

だいぶ慣れてきた！

42　JOI 2015 予選 4 - シルクロード

問題はこちらです！
問題文↓

街を移動するのに2つの選択がある
・コストをかけて次の街へ移動する
・コストを掛けずに待機する
毎日コストが変わっていく時、最小のコストの値を出力してください

DP[m+1]n+1を作って、DP[i+1]jとDP[i+1]j+1を書き換えていきます
コードはこんな感じです

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
ll smallMOD = 998244353;
ll bigMOD = 1000000007;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> D(n), C(m);
    rep(i, n) cin >> D[i];
    rep(i, m) cin >> C[i];
    vector<vector<ll>> dp(m + 1, vector<ll>(n + 1, INT64_MAX));
    dp[0][0] = 0;
    rep(i, m)
    {
        rep(j, n + 1)
        {
            if (dp[i][j] != INT64_MAX)
            {
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
                if (j != n)
                {
                    dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + D[j] * C[i]);
                }
            }
        }
    }
    cout << dp[m][n] << endl;
    return 0;
}

43　パ研杯2019 D - パ研軍旗

問題はこちらです！
問題文↓

全行に色を上書きしていく
赤、青、白の色を塗っていき、1マス塗るのに1costかかる
もともと塗りたい色が塗っていた場合は塗らなくてもいい
各列の色が隣り合わないようにするとき、最小のコストを求めてください

DP[i][j]において
i:N行目のコスト
j:赤、青、白の三色のどれか(3)
として、DP[n][3]を作成します
returnOther関数さんを作っとくと便利だったりする
コードはこんな感じです！

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
ll smallMOD = 998244353;
ll bigMOD = 1000000007;

vector<int> returnOther(int x)
{
    if (x == 0)
    {
        return {1, 2};
    }
    else if (x == 1)
    {
        return {0, 2};
    }
    else
    {
        return {0, 1};
    }
}

int main()
{
    int n;
    cin >> n;
    vector<string> M(5);
    rep(i, 5) cin >> M[i];
    vector<vector<ll>> dp(n, vector<ll>(3, INT64_MAX));
    int nonR = 0, nonB = 0, nonW = 0;
    rep(i, 5)
    {
        if (M[i][0] != 'R')
            nonR++;
        if (M[i][0] != 'B')
            nonB++;
        if (M[i][0] != 'W')
            nonW++;
    }
    dp[0][0] = nonR;
    dp[0][1] = nonB;
    dp[0][2] = nonW;
    rep(i, n - 1)
    {
        int nonR = 0, nonB = 0, nonW = 0;
        rep(j, 5)
        {
            if (M[j][i + 1] != 'R')
                nonR++;
            if (M[j][i + 1] != 'B')
                nonB++;
            if (M[j][i + 1] != 'W')
                nonW++;
        }
        vector<ll> nonRBW = {nonR, nonB, nonW};
        rep(j, 3)
        {
            auto x = returnOther(j);
            rep(k, 2)
            {
                dp[i + 1][x[k]] = min(dp[i + 1][x[k]], dp[i][j] + nonRBW[x[k]]);
            }
        }
    }
    cout << min({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]}) << endl;
    return 0;
}

44　AOJ 1167 - ポロック予想

問題はこちらです！
問題文↓

n(n+1)(n+2) ⁄ 6という式の自然数nにある数を代入して求まった答えを正四面体数という
正四面体数のいくつかを取り出して、入力で与えられる数を作成して、作ることのできる最小の個数を求めてください  
また、正四面体数の中でも奇数のものでも同じ操作を行ってください

はじめ、正四面体数のindexが奇数のものと読み間違えていて、悩みました、、、
10⁶未満の正四面体数は180個しか無いので、普通の重複有りナップザック問題
DP[n][180]を作ってナップザックする
コードはこんな感じです！

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
ll smallMOD = 998244353;
ll bigMOD = 1000000007;

int main()
{
    ll x;
    cin >> x;
    vector<ll> items, oddItems;
    ll c = 1;
    while (c * (c + 1) * (c + 2) / 6 < 1e6)
    {
        items.push_back(c * (c + 1) * (c + 2) / 6);
        if (c * (c + 1) * (c + 2) / 6 % 2)
        {
            oddItems.push_back(c * (c + 1) * (c + 2) / 6);
        }
        c++;
    }
    vector<ll> dp(1e6, INT32_MAX), oddDp(1e6, INT32_MAX);
    dp[0] = 0;
    rep(i, items.size())
    {
        rep(j, 1e6)
        {
            if (j - items[i] >= 0)
            {
                dp[j] = min(dp[j], dp[j - items[i]] + 1ll);
            }
        }
    }
    oddDp[0] = 0;
    rep(i, oddItems.size())
    {
        rep(j, 1e6)
        {
            if (j - oddItems[i] >= 0)
            {
                oddDp[j] = min(oddDp[j], oddDp[j - oddItems[i]] + 1ll);
            }
        }
    }
    while (x != 0)
    {
        cout << dp[x] << " " << oddDp[x] << endl;
        cin >> x;
    }
    return 0;
}

AOJって意外とむずい

45　AOJ 2199 - 差分パルス符号変調

問題はこちらです！
問題文↓

ある数がn個とコードブック(数列)が与えられるので、y_0=128として、
y_i=y_(i-1)+C[x]で作られるy_iとある数のi番目の差の2乗の総和が最小になるような値を求めてください
ただし、y_iが0未満になる場合はy_i=0に、y_iが256以上になるときはy_i=255にまるめてください

結構難しいです、、、
N回の値のステートと、256個のステートを使うことで解けました
コードはこんな感じです

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
ll smallMOD = 998244353;
ll bigMOD = 1000000007;

int main()
{
    ll n, m;
    cin >> n >> m;
    while (!(n == 0 && m == 0))
    {
        vector<ll> C(m), X(n);
        rep(i, m) cin >> C[i];
        rep(i, n) cin >> X[i];
        vector<vector<ll>> dp(20001, vector<ll>(256, INT32_MAX));
        dp[0][128] = 0;
        rep(i, n)
        {
            rep(j, 256)
            {
                if (dp[i][j] == INT32_MAX)
                    continue;
                rep(k, m)
                {
                    ll yn = j + C[k];
                    if (yn < 0)
                        yn = 0;
                    if (yn > 255)
                        yn = 255;
                    ll s = (X[i] - yn) * (X[i] - yn);
                    dp[i + 1][yn] = min(dp[i + 1][yn], dp[i][j] + s);
                }
            }
        }
        ll ans = INT32_MAX;
        rep(i, 256)
        {
            ans = min(ans, dp[n][i]);
        }
        cout << ans << endl;
        cin >> n >> m;
    }
    return 0;
}

DPﾁｮｯﾄﾜｶﾙようになったはず,,,

終わりに

最後まで見てくださりありがとうございました！
次は区間DPです！
ではまた

2024-03-19

競プロ精選 100 問 by C++<動的計画法：ナップザック DP>

精選100問

はじめに

こんにちは！
今回から、5回連続DPです

34　ALDS_10_A - フィボナッチ数

問題はこちらです！
問題文↓

フィボナッチ数列のN番目を求めてください

再帰関数だとO(N²)だけど、前のデータをmemo化しておくことでDPによってO(N)となる基本問題！
コードはこんな感じになりました

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
int smallMOD = 998244353;
int bigMOD = 1000000007;

int main()
{
    vector<int> A = {1, 1};
    int n;
    cin >> n;
    rep(i, n - 1)
    {
        A.push_back(A[i] + A[i + 1]);
    }
    cout << A[n] << endl;
    return 0;
}

全てのデータをvectorに保存しなくても良い気もする？

35　DPL_1_B - 0,1ナップザック問題

問題はこちらです！
問題文↓

重さWを超えないようにN個のものから価値が最大になるように選んでください

DPの基本問題でした！
コードはこんな感じです

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
int smallMOD = 998244353;
int bigMOD = 1000000007;

int main()
{
    int n, w;
    cin >> n >> w;
    vector<pair<int, int>> items(n);
    rep(i, n)
    {
        int weight, value;
        cin >> value >> weight;
        items[i] = make_pair(weight, value);
    }
    // ナップザックDP
    vector<vector<int>> dp(n + 1, vector<int>(w + 1, 0));
    rep(i, n)
    {
        rep(j, w + 1)
        {
            if (j - items[i].first >= 0)
            {
                dp[i + 1][j] = max(dp[i][j], dp[i][j - items[i].first] + items[i].second);
            }
            else
            {
                dp[i + 1][j] = dp[i][j];
            }
        }
    }
    cout << dp[n][w] << endl;
    return 0;
}

基本問題なのでcopilotがほぼ書いてくれました(よくない)

36　DPL_1_C - ナップザック問題

問題はこちらです！
問題文↓

# 35に要素を追加する
・同じアイテムを何回も選ぶことが出来る

簡単なDPです！
コードはこんな感じ

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
int smallMOD = 998244353;
int bigMOD = 1000000007;

int main()
{
    int n, w;
    cin >> n >> w;
    vector<pair<int, int>> items(n);
    rep(i, n)
    {
        int weight, value;
        cin >> value >> weight;
        items[i] = make_pair(weight, value);
    }
    // 同じアイテムも選ぶことが出来るナップザックDP
    vector<int> dp(w + 1, 0);
    rep(i, n)
    {
        rep(j, w + 1)
        {
            if (j - items[i].first >= 0)
            {
                dp[j] = max(dp[j], dp[j - items[i].first] + items[i].second);
            }
        }
    }
    cout << dp[w] << endl;
    return 0;
}

DP練習しなきゃ,,,

37　DPL_1_A - コイン問題

問題はこちらです！
問題文↓

いくつかの額面がバラバラのコインが与えられる
それらを組み合わせてn円を作成する
そのときの最小のコインの枚数はいくつか
同じコインを使用してもよい

コードはこんな感じ

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
int smallMOD = 998244353;
int bigMOD = 1000000007;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> coins(m);
    rep(i, m) cin >> coins[i];
    // coinでn円を作る最小の枚数のDP
    vector<int> dp(n + 1, 100000);
    dp[0] = 0;
    rep(i, m)
    {
        rep(j, n + 1)
        {
            if (j - coins[i] >= 0)
            {
                dp[j] = min(dp[j], dp[j - coins[i]] + 1);
            }
        }
    }
    cout << dp[n] << endl;
    return 0;
}

基本問題はcopilotに任せて、コードを理解することに専念します

38　ALDS_10_C - 最長共通部分列

問題はこちらです！
問題文↓

最長共通部分列とは、{x_1,x_2,x_3,...,x_n}と{y_1,y_2,y_3,...,y_m}という文字列があった時、いくつかの文字を取り出して等しくなった文字列のうち、最長の長さのものです
例えば、abcdeはacdという文字列を部分列として持っており、acdfという文字列もacdという部分列を持っています
このacdという文字列を共通部分列ということにします
この共通部分列のうち、最長のものの長さを求めてください

コードはこんな感じ

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
int smallMOD = 998244353;
int bigMOD = 1000000007;

int main()
{
    int n;
    cin >> n;
    // 最長共通部分列問題をDPで解く
    rep(i, n)
    {
        string x, y;
        cin >> x >> y;
        int m = x.size();
        int l = y.size();
        vector<vector<int>> dp(m + 1, vector<int>(l + 1, 0));
        rep(i, m)
        {
            rep(j, l)
            {
                if (x[i] == y[j])
                {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                }
                else
                {
                    dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
                }
            }
        }
        cout << dp[m][l] << endl;
    }
    return 0;
}

めっちゃむずい、、、

おわりに

お疲れ様でした！
次は真面目にDPの精進をします
ではまた！

2024-03-12

競プロ精選 100 問 by C++<幅優先探索>

精選100問

はじめに

今回は幅優先探索の6問をやりました！精選100問はこちら！

28　ALDS_11_C - 幅優先探索

問題はこちらです！
問題文↓

グラフを与えるので頂点1からの一番短い距離をBFSで求めてください

基本問題でした！
コードは以下のようになりました

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
int smallMOD = 998244353;
int bigMOD = 1000000007;

ll n;
vector<vector<ll>> graph;

// BFS
vector<ll> BFS(ll start)
{
    // 頂点の数だけ-1で初期化された配列を作る
    vector<ll> dist(n, -1);
    // 頂点startからの距離は0
    dist[start] = 0;
    // キューを作る
    queue<ll> que;
    // キューにstartを追加
    que.push(start);
    // キューが空になるまで繰り返す
    while (!que.empty())
    {
        // キューの先頭を取り出す
        ll v = que.front();
        que.pop();
        // vから行ける頂点をすべて調べる
        for (auto nv : graph[v])
        {
            // すでに発見済みの頂点は探索しない
            if (dist[nv] != -1)
                continue;
            // 新たな頂点nvについて距離情報を更新してキューに追加
            dist[nv] = dist[v] + 1;
            que.push(nv);
        }
    }
    return dist;
}

int main()
{
    // n個の頂点があるので、nを入力
    cin >> n;

    // 2次元配列のグラフを作る
    graph.resize(n);

    // n回繰り返して、u k v1,v2,v3...vkを入力
    rep(i, n)
    {
        ll u, k;
        cin >> u >> k;
        rep(j, k)
        {
            ll v;
            cin >> v;
            // グラフに辺を追加
            graph[u - 1].push_back(v - 1);
        }
    }
    // BFSを実行
    vector<ll> dist = BFS(0);

    // 各頂点までの距離を出力
    rep(i, n)
    {
        cout << i + 1 << " " << dist[i] << endl;
    }
    return 0;
}

29　AtCoder Beginner Contest 007 C - 幅優先探索

問題はこちらです！
問題文↓

地図を与えるので、sx,syからgx,gyまでの最短距離を出力してください

こちらも基本問題でした！
こんな感じです

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
int smallMOD = 998244353;
int bigMOD = 1000000007;

int main()
{
    // 入力.
    int h, w, sx, sy, gx, gy;
    cin >> h >> w >> sx >> sy >> gx >> gy;
    vector<string> s(h);
    rep(i, h) cin >> s[i];

    // BFSを実行する.
    vector<vector<int>> dist(h, vector<int>(w, -1));
    queue<pair<int, int>> q;
    q.push({sx - 1, sy - 1});
    dist[sx - 1][sy - 1] = 0;
    while (!q.empty())
    {
        auto [x, y] = q.front();
        q.pop();
        for (int dx = -1; dx <= 1; dx++)
        {
            for (int dy = -1; dy <= 1; dy++)
            {
                if (dx == 0 || dy == 0)
                {
                    int nx = x + dx;
                    int ny = y + dy;
                    if (nx < 0 || nx >= h || ny < 0 || ny >= w)
                        continue;
                    if (s[nx][ny] == '#')
                        continue;
                    if (dist[nx][ny] != -1)
                        continue;
                    dist[nx][ny] = dist[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }
    }
    cout << dist[gx - 1][gy - 1] << endl;
    return 0;
}

30　JOI 2011 予選 5 - チーズ

問題はこちらです！
問題文↓

初期座標・1からnまでの数字(1≦n≦9)・'.'+'X'という地面と障害物の書かれた地図を渡すので
初期座標から初めて、1,...,nと行くのに最小で何歩進めばよいかを求めてください

n回BFSを実行して、足し合わせればいいですね！
こんな感じに書きました！

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
int smallMOD = 998244353;
int bigMOD = 1000000007;

int main()
{
    // h,w,nを受け取る
    int h, w, n;
    cin >> h >> w >> n;
    // 地図を受け取る
    vector<string> s(h);
    rep(i, h) cin >> s[i];
    // 現在地Sと'1'～'n'までの位置を記録する
    int Sx, Sy;
    vector<pair<int, int>> pos(n + 1);
    rep(i, h)
    {
        rep(j, w)
        {
            // 自分の初期位置.
            if (s[i][j] == 'S')
            {
                Sx = i;
                Sy = j;
            }

            // チーズの位置.
            if (s[i][j] >= '1' && s[i][j] <= '9')
            {
                pos[s[i][j] - '0' - 1] = make_pair(i, j);
            }
        }
    }

    // 現在地から初めて、1,...nまでの最短距離をBFSで求める
    int ans = 0;
    rep(i, n)
    {
        vector<vector<int>> dist(h, vector<int>(w, -1));
        queue<pair<int, int>> q;
        q.push(make_pair(Sx, Sy));
        dist[Sx][Sy] = 0;
        while (!q.empty())
        {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            if (x == pos[i].first && y == pos[i].second)
            {
                ans += dist[x][y];
                Sx = x;
                Sy = y;
                break;
            }
            rep(j, 4)
            {
                int nx = x + (j == 0) - (j == 1);
                int ny = y + (j == 2) - (j == 3);
                if (nx < 0 || nx >= h || ny < 0 || ny >= w)
                    continue;
                if (s[nx][ny] == 'X')
                    continue;
                if (dist[nx][ny] != -1)
                    continue;
                dist[nx][ny] = dist[x][y] + 1;
                q.push(make_pair(nx, ny));
            }
        }
    }
    cout << ans << endl;
    return 0;
}

31　JOI 2012 予選 5 - イルミネーション

問題はこちらです！
問題文↓

六角形をつなぎ合わせたような図を作成する
このとき、黒い部分の周りの長さを求めよ

(画像は問題文より参照)
重要だと思ったことは2つありました
・偶数行・奇数行によって見る場所が変わること
・与えられた地図の周りに白色の土地を作成して、BFSをすること
です！
一度、周りに新しく土地を作って、BFSを実行することで、赤枠の外側の白色の六角形を判定することが出来ました
また、奇数行は上、下、右上、右下、左、右・偶数行は上、下、左上、左下、左、右というふうに見る場所が変わってきます
こんな感じのコードを書きました

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
int smallMOD = 998244353;
int bigMOD = 1000000007;

int main()
{
    // h,w
    int h, w;
    cin >> w >> h;

    // aに周りに0を追加した配列を作成
    vector<vector<int>> a(h + 2, vector<int>(w + 2, 0));
    rep(i, h)
    {
        rep(j, w)
        {
            cin >> a[i + 1][j + 1];
        }
    }

    // a[0][0]から初めて、0と2は通れる、1は通れない
    // BFSで(0,0)から移動可能なマスを全て2に置き換える
    queue<pair<int, int>> q;
    q.push({0, 0});

    // ただし、地図は六角形の組み合わさったハニカム構造になっている
    // そのため、奇数行と偶数行で移動可能な方向が異なる
    // 奇数行は上、下、右上、右下、左、右
    // 偶数行は上、下、左上、左下、左、右
    auto directionX = vector<vector<int>>{
        {0, 0, -1, -1, -1, 1},
        {0, 0, 1, 1, -1, 1},
    };
    auto directionY = vector<vector<int>>{
        {-1, 1, -1, 1, 0, 0},
        {-1, 1, -1, 1, 0, 0},
    };
    while (!q.empty())
    {
        auto [x, y] = q.front();
        q.pop();
        rep(i, 6)
        {
            int nextX = x + directionX[y % 2][i];
            int nextY = y + directionY[y % 2][i];
            if (nextX < 0 || nextX >= w + 2 || nextY < 0 || nextY >= h + 2)
            {
                continue;
            }
            if (a[nextY][nextX] == 0)
            {
                a[nextY][nextX] = 2;
                q.push({nextX, nextY});
            }
        }
    }

    // 全部のマスを見て、1があれば、その周りにある2の個数を数える
    int ans = 0;
    rep(i, h + 2)
    {
        rep(j, w + 2)
        {
            if (a[i][j] == 1)
            {
                rep(k, 6)
                {
                    int nextX = j + directionX[i % 2][k];
                    int nextY = i + directionY[i % 2][k];
                    if (nextX < 0 || nextX >= w + 2 || nextY < 0 || nextY >= h + 2)
                    {
                        continue;
                    }
                    if (a[nextY][nextX] == 2)
                    {
                        ans++;
                    }
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

いい問題です！

32　AOJ 1166 - 迷図と命ず

問題はこちらです！
問題文↓

ブロック状の迷路でなく、線が書かれている迷路がある
その迷路の左上から右下への最短距離を求めよ

普通のBFS問題です！
ただ、移動できる場所に注意
コードはこんな感じに書きました

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
int smallMOD = 998244353;
int bigMOD = 1000000007;

int main()
{
    int h, w;
    cin >> w >> h;
    while (h != 0 && w != 0)
    {
        // 2 * h - 1行の配列を作成
        vector<vector<int>> field(2 * h - 1);
        rep(i, 2 * h - 1)
        {
            rep(j, w - !(i % 2))
            {
                int x;
                cin >> x;
                field[i].push_back(x);
            }
        }

        // BFSを実行
        vector<vector<int>> dist(h, vector<int>(w, -1));
        queue<pair<int, int>> que;
        que.push(make_pair(0, 0));
        dist[0][0] = 1;
        bool canG = false;
        while (!que.empty())
        {
            pair<int, int> p = que.front();
            que.pop();
            int x = p.first;
            int y = p.second;

            // ゴールに到達したら終了
            if (x == w - 1 && y == h - 1)
            {
                cout << dist[y][x] << endl;
                canG = true;
                break;
            }

            // 4方向に移動
            if (x > 0 && field[2 * y][x - 1] == 0 && dist[y][x - 1] == -1)
            {
                que.push(make_pair(x - 1, y));
                dist[y][x - 1] = dist[y][x] + 1;
            }
            if (x < w - 1 && field[2 * y][x] == 0 && dist[y][x + 1] == -1)
            {
                que.push(make_pair(x + 1, y));
                dist[y][x + 1] = dist[y][x] + 1;
            }
            if (y > 0 && field[2 * y - 1][x] == 0 && dist[y - 1][x] == -1)
            {
                que.push(make_pair(x, y - 1));
                dist[y - 1][x] = dist[y][x] + 1;
            }
            if (y < h - 1 && field[2 * y + 1][x] == 0 && dist[y + 1][x] == -1)
            {
                que.push(make_pair(x, y + 1));
                dist[y + 1][x] = dist[y][x] + 1;
            }
        }
        if (!canG)
        {
            cout << 0 << endl;
        }
        cin >> w >> h;
    }
    return 0;
}

33　AtCoder Beginner Contest 088 D - Grid Repainting

問題はこちらです！
問題文↓

迷路をクリアして、スタートからゴールまでの一方通行の道を作って、それ以外を黒色で埋めてください
もし、迷路がゴールできないのなら-1を出力してください

BFSを実行して、hw-(最短距離+1)-黒いマスの数で求まります！
以下のようになりました

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
int smallMOD = 998244353;
int bigMOD = 1000000007;

int main()
{
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    rep(i, h) cin >> s[i];
    // BFSで(1,1)から(h,w)までの最短距離を求める
    int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
    vector<vector<int>> dist(h, vector<int>(w, -1));
    queue<pair<int, int>> que;
    dist[0][0] = 0;
    que.push(make_pair(0, 0));
    while (!que.empty())
    {
        int y, x;
        tie(y, x) = que.front();
        que.pop();
        rep(dir, 4)
        {
            int ny = y + dy[dir], nx = x + dx[dir];
            if (ny < 0 || ny >= h || nx < 0 || nx >= w)
                continue;
            if (s[ny][nx] == '#')
                continue;
            if (dist[ny][nx] != -1)
                continue;
            dist[ny][nx] = dist[y][x] + 1;
            que.push(make_pair(ny, nx));
        }
    }
    if (dist[h - 1][w - 1] == -1)
    {
        cout << -1 << endl;
        return 0;
    }
    // すべてのマスから#の個数を数える
    int num = 0;
    rep(i, h) rep(j, w) if (s[i][j] == '#') num++;
    cout << h * w - (dist[h - 1][w - 1] + num) - 1 << endl;
    return 0;
}

おわりに

BFSが終わりました！
次からはDP問題です！
ではまた

2024-03-05

競プロ精選 100 問 by C++<深さ優先探索>

精選100問

はじめに

今回は深さ優先探索の4問をやりました！
精選100問はこちら！

24　ALDS_11_B - 深さ優先探索

問題はこちらです！
問題文↓

グラフを与えるので、小さい順にDFSしてください

基本問題でした！
コードは以下のようになりました

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
int smallMOD = 998244353;
int bigMOD = 1000000007;

// DFSのテンプレ.
vector<bool> seen;
vector<int> first_order;
vector<int> last_order;
void dfs(const vector<vector<ll>> &G, int v, int &ptr)
{
    first_order[v] = ptr;
    ptr++;
    seen[v] = true;
    for (auto next_v : G[v])
    {
        if (seen[next_v])
            continue;
        dfs(G, next_v, ptr);
    }
    last_order[v] = ptr;
    ptr++;
}

int main()
{
    // 入力.
    int n;
    cin >> n;
    vector<vector<ll>> G(n);
    rep(i, n)
    {
        int u, k;
        cin >> u >> k;
        rep(j, k)
        {
            int x;
            cin >> x;
            G[u - 1].push_back(x - 1);
        }
    }

    // DFSセットアップ.
    seen.assign(n, false);
    first_order.resize(n);
    last_order.resize(n);
    int ptr = 0;

    // 全ての頂点に対して、行ったことがなければDFS→頂点1から離れている木も探索.
    rep(i, n)
    {
        if (!seen[i])
        {
            dfs(G, i, ptr);
        }
    }

    // 結果出力.
    for (int v = 0; v < n; ++v)
        cout << v + 1 << " " << first_order[v] + 1 << " " << last_order[v] + 1 << endl;

    return 0;
}

けんちょんさんの記事がわかりやすい！
参考はこちらです！(参考)

25　AOJ 1160 - 島はいくつある？

問題はこちらです！
問題文↓

2次元平面上に陸と海が書かれています
斜めも入れて8方向に進むことが出来る場合、島の個数はいくつになりますか？

これは、DFSをして、1回目のDFSの回数をカウントしていくだけですね！
コードはこのようになりました

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
int smallMOD = 998244353;
int bigMOD = 1000000007;

int w, h;
vector<vector<bool>> seen;
vector<vector<int>> A;
vector<pair<int, int>> directions = {pair(1, -1),
                                     pair(0, -1),
                                     pair(-1, -1),
                                     pair(1, 0),
                                     pair(-1, 0),
                                     pair(1, 1),
                                     pair(0, 1),
                                     pair(-1, 1)};
void dfs(int i, int j)
{
    seen[i][j] = true;
    rep(k, 8)
    {
        int x = directions[k].first;
        int y = directions[k].second;
        if (i + x >= 0 && i + x < h && j + y >= 0 && j + y < w)
        {
            if (!seen[i + x][j + y] && A[i + x][j + y])
            {
                dfs(i + x, j + y);
            }
        }
    }
}

int main()
{
    cin >> w >> h;
    while (!(w == 0 && h == 0))
    {
        int cnt = 0;
        A.assign(h, vector<int>(w, 0));
        seen.assign(h, vector<bool>(w, false));
        rep(i, h)
        {
            rep(j, w)
            {
                cin >> A[i][j];
            }
        }
        rep(i, h)
        {
            rep(j, w)
            {
                if (!seen[i][j] && A[i][j])
                {
                    dfs(i, j);
                    cnt++;
                }
            }
        }
        cin >> w >> h;
        cout << cnt << endl;
    }
    return 0;
}

resizeとassignの違いを知ることができた！
向きは配列に入れて管理が一番スマートだと思います！

26　AtCoder Beginner Contest 138 D - Ki

問題はこちらです！
問題文↓

1 から N までの番号がついた N 個の頂点を持つ根付き木が与えられ、それぞれ、初期値が0のカウンターを持っています
この木の根は頂点1とします
いくつかのクエリが与えられるので、ある頂点を根とする部分木に含まれるすべての頂点のカウンターに値を足してください

3ペナになったけれど、行けた！
1ペナ目:根が頂点1であることを見ずに、すべての頂点に対してDFSをした結果TLE
2ペナ目:頂点1のみにDFSをしたけれど、頂点1に対してつながっていない頂点のカウンターの値が出力されていなかった
3ペナ目:after contestのせいで死んだ→1に直接的にはつながっていないノードが存在したときにうまく行っていなかった
てことでこんなコードを書きました

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
int smallMOD = 998244353;
int bigMOD = 1000000007;

// 変数.
int n, q;
vector<vector<int>> G;
vector<int> dat;
vector<bool> seen;

// DFS.
void dfs(int now, int item)
{
    dat[now] = item;
    seen[now] = true;
    rep(i, G[now].size())
    {
        if (!seen[G[now][i]])
            dfs(G[now][i], item + dat[G[now][i]]);
    }
}

int main()
{
    // 入力.
    cin >> n >> q;
    G.resize(n);
    dat.resize(n, 0);
    seen.resize(n, false);

    // 無向グラフとしてグラフを作成.
    rep(i, n - 1)
    {
        int x, y;
        cin >> x >> y;
        G[x - 1].push_back(y - 1);
        G[y - 1].push_back(x - 1);
    }

    // 親の頂点に対して加算しておき、後で部分木に加算していく.
    rep(i, q)
    {
        int x, y;
        cin >> x >> y;
        dat[x - 1] += y;
    }

    // 根1に対してDFS.
    dfs(0, dat[0]);

    // 全て出力.
    rep(i, n)
    {
        cout << dat[i] << endl;
    }
    return 0;
}

27　JOI 2009 予選 4 - 薄氷渡り

問題はこちらです！
問題文↓

陸と海に分けられた地図が与えられます
陸続きになっているとき、最大で何マス移動できますか？
移動方法は4方向とします

DFSを全てのマスについて行えば制約が小さいので、実行時間に間に合います！
このようなコードを書きました！

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
int smallMOD = 998244353;
int bigMOD = 1000000007;

int h, w, ans = 0;
vector<vector<int>> M;
vector<vector<bool>> seen;
vector<pair<int, int>> direction = {
    pair(1, 0),
    pair(-1, 0),
    pair(0, 1),
    pair(0, -1),
};

void dfs(int i, int j, int now)
{
    seen[i][j] = true;
    now++;
    ans = max(ans, now);
    rep(k, 4)
    {
        int ni = i + direction[k].first;
        int nj = j + direction[k].second;
        if (0 <= ni && ni < h && 0 <= nj && nj < w)
        {
            if (!seen[ni][nj] && M[ni][nj])
            {
                dfs(ni, nj, now);
            }
        }
    }
    seen[i][j] = false;
}

int main()
{
    cin >> w >> h;
    M.resize(h, vector<int>(w));
    seen.resize(h, vector<bool>(w, false));
    rep(i, h)
    {
        rep(j, w) cin >> M[i][j];
    }
    rep(i, h)
    {
        rep(j, w)
        {
            if (M[i][j])
            {
                seen.assign(h, vector<bool>(w, false));
                dfs(i, j, 0);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

JOIはいい問題ですねー！

さいごに

最後まで読んでくださりありがとうございました！
ではまた！

2024-03-05

Yukicoder緑<No.42B>

yukicoder contest-緑

問題

問題はこちら
問題文↓

'+'は掛け算を表す演算子、'*'は足し算を表す演算子です
式が与えられるので、左から順番にこの計算をしてください

解法

演算子の定義を間違えずに、左から順番に見ていく
演算子が来たら、前の演算子を計算して、保存を繰り返す

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
int smallMOD = 998244353;
int bigMOD = 1000000007;

int main()
{
    string s;
    cin >> s;
    string num1 = "";
    string num2 = "";
    char op = 'x';
    rep(i, s.size())
    {
        if (s[i] == '+' || s[i] == '*')
        {
            if (op == 'x')
            {
                op = s[i];
                num1 = num2;
                num2 = "";
            }
            else
            {
                if (op == '*')
                    num1 = to_string(stoi(num1) + stoi(num2));
                else
                    num1 = to_string(stoi(num1) * stoi(num2));
                num2 = "";
                op = s[i];
            }
        }
        else
            num2 += s[i];
    }
    if (op == '*')
        num1 = to_string(stoi(num1) + stoi(num2));
    else
        num1 = to_string(stoi(num1) * stoi(num2));
    cout << num1 << endl;
    return 0;
}

はじめに

70 NTL_1_B - べき乗

71 Square869120Contest #1 E - 散歩

おわり

はじめに

68 NTL_1_A - 素因数分解

69 AtCoder Beginner Contest 084 D - 2017-like Number

最後に

はじめに

39 JOI 2011 予選 4 - 1 年生

40 JOI 2012 予選 4 - パスタ

41 JOI 2013 予選 4 - 暑い日々

42 JOI 2015 予選 4 - シルクロード

43 パ研杯2019 D - パ研軍旗

44 AOJ 1167 - ポロック予想

45 AOJ 2199 - 差分パルス符号変調

終わりに

はじめに

34 ALDS_10_A - フィボナッチ数

35 DPL_1_B - 0,1ナップザック問題

36 DPL_1_C - ナップザック問題

37 DPL_1_A - コイン問題

38 ALDS_10_C - 最長共通部分列

おわりに

はじめに

28 ALDS_11_C - 幅優先探索

29 AtCoder Beginner Contest 007 C - 幅優先探索

30 JOI 2011 予選 5 - チーズ

31 JOI 2012 予選 5 - イルミネーション

32 AOJ 1166 - 迷図と命ず

33 AtCoder Beginner Contest 088 D - Grid Repainting

おわりに

はじめに

24 ALDS_11_B - 深さ優先探索

25 AOJ 1160 - 島はいくつある？

26 AtCoder Beginner Contest 138 D - Ki

27 JOI 2009 予選 4 - 薄氷渡り

さいごに

問題

解法

70　NTL_1_B - べき乗

71　Square869120Contest #1 E - 散歩

68　NTL_1_A - 素因数分解

69　AtCoder Beginner Contest 084 D - 2017-like Number

39　JOI 2011 予選 4 - 1 年生

40　JOI 2012 予選 4 - パスタ

41　JOI 2013 予選 4 - 暑い日々

42　JOI 2015 予選 4 - シルクロード

43　パ研杯2019 D - パ研軍旗

44　AOJ 1167 - ポロック予想

45　AOJ 2199 - 差分パルス符号変調

34　ALDS_10_A - フィボナッチ数

35　DPL_1_B - 0,1ナップザック問題

36　DPL_1_C - ナップザック問題

37　DPL_1_A - コイン問題

38　ALDS_10_C - 最長共通部分列

28　ALDS_11_C - 幅優先探索

29　AtCoder Beginner Contest 007 C - 幅優先探索

30　JOI 2011 予選 5 - チーズ

31　JOI 2012 予選 5 - イルミネーション

32　AOJ 1166 - 迷図と命ず

33　AtCoder Beginner Contest 088 D - Grid Repainting

24　ALDS_11_B - 深さ優先探索

25　AOJ 1160 - 島はいくつある？

26　AtCoder Beginner Contest 138 D - Ki

27　JOI 2009 予選 4 - 薄氷渡り