2020-12-24

yukicoder：No.701 ひとりしりとり

yukicoder 競技プログラミング

スペシャルジャッジ問題は面白いなぁ

問題概要

yukicoder.me

ちょうど $N$ 個の単語でしりとりをせよ。ただし次のルールを守る必要がある。

小文字アルファベットのみからなる $1$ ~ $20$ 文字の単語のみ使用できる。
単語の末尾と次の文字を同じにする必要がある。
最後以外の単語の末尾は n 以外、最後の単語の末尾は n である必要がある。
はじめの単語には上記ルールに従う任意の単語を用いてよい。
同じ単語は用いてはならない。

制約

$1 \leq N \leq 10^{5}$

解法

結論から述べると、 $1$ ~ $N-1$ 個目の単語として

a + (かぶらない $5$ 文字の単語) + a

を用いて $N$ 個目に an を用いて終わらせばよい。

$5$ 文字の単語には aaaaa ~ zzzzz の $26^{5}=11881376$ 通りのバリエーションがあるので $N-1$ 通りは十分表現可能。

24 1 3 4 5

25 1 3 4 5

0 2 3 4 5

という風に配列で繰り上がりを表現して $N-1$ 通り作ればよい。

コード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define mod 1000000007ll
#define loop(i, n) for (int i = 0; i < n; i++)
#define all(v) v.begin(), v.end()
#define putout(a) cout << a << '\n'
#define Sum(v) accumulate(all(v), 0ll)

int main()
{
    ll N;
    cin >> N;
    vector<ll> num(5);
    loop(i, N - 1)
    {
        string now;
        num[0]++;
        ll j = 0;
        while (num[j] == 26)
        {
            num[j] = 0;
            num[j + 1]++;
            j++;
        }
        loop(j, 5) now += (char)('a' + num[j]);
        cout << "a" << now << "a" << endl;
    }
    putout("an");
    return 0;
}

2020-12-23

yukicoder：No.1103 Directed Length Sum

yukicoder 競技プログラミング

めちゃくちゃ教育的で面白い問題だった！

問題概要

yukicoder.me

$N$ 頂点の有向木がある。

この有向木は根以外の各頂点の親からその頂点へ $1$ 本の有向辺が伸びた構造をしている。

$f(a,b)$ を「頂点 $a$ から頂点 $b$ に移動するとき経由する辺の数」とするとき、

$\displaystyle \sum_{i=1}^{N} \sum_{j=1}^{N} f(i,j)$ $mod$ $10^{9}+7$ を求めよ。

但し $f(a,a)=0$ , $f(a,b)=0$ ( $a$ から $b$ へのパスが存在しないとき)とする。

制約

$3 \leq N \leq 10^{6}$

解法

$N$ が大きいのでまず愚直 $O(N^{2})$ は通らない。

この有向木は根以外の各頂点の親からその頂点へ $1$ 本の有向辺が伸びた構造をしている。(意訳)という文言が重要そうである。

なぜなら $a$ から $b$ へのパスが存在しないとき $f(a,b)=0$ なので、根からとある葉へのパスに異なる頂点 $a$ と $b$ が両方とも存在していて $a$ が根に近いときにのみ $f(a,b)$ が $0$ でなくなるという言い換えができるからである。

この言い換えをすることによって何が嬉しいのかというと、前回解説した問題 yukicoder：No.1096 Range Sums - kacho65535の競プロメモでも用いた考察典型である各要素が何回足されるかを考える問題に帰着できるからである。しかも、足される回数の求め方も前回の問題と本質的に同じである。

以上の考察から次のことが分かる。

ある有向辺 $a$ $\to$ $b$ が足される回数は、根から $a$ までのパスに含まれる頂点の個数(根や $a$ も含む)を $x$ 、この有向辺を取り除いたときにできる $b$ を含む部分木の頂点数を $y$ として、 $x×y$ 回である。

よってすべての有向辺に対する $x×y$ の総和が答えになる。(辺のコストが $1$ なので)

これを求めるには、各 $x$ を根からのBFSで求めた後、木dpで部分木のサイズを記録していけばよい。

コード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define mod 1000000007ll
#define loop(i, n) for (int i = 0; i < n; i++)
#define all(v) v.begin(), v.end()
#define putout(a) cout << a << '\n'
#define Sum(v) accumulate(all(v), 0ll)
void bfs(vector<vector<ll>> &G, vector<ll> &dist, ll s)
{
    queue<ll> que;
    dist[s] = 0;
    que.push(s);
    while (!que.empty())
    {
        ll v = que.front();
        que.pop();
        for (auto next_v : G[v])
        {
            if (dist[next_v] != -1)
                continue;
            dist[next_v] = dist[v] + 1;
            que.push(next_v);
        }
    }
}
vector<ll> sz;
void dfs(vector<vector<ll>> &G, ll v, ll p)
{
    for (auto nv : G[v])
    {
        if (nv == p)
            continue;
        dfs(G, nv, v);
    }
    sz[v] = 1;
    for (auto nv : G[v])
    {
        if (nv == p)
            continue;
        sz[v] += sz[nv];
    }
}
int main()
{
    ll N;
    cin >> N;
    vector<vector<ll>> G(N);
    ll root = 0; //bとして1度も出現しないのが根
    sz.resize(N);
    vector<ll> A(N - 1), B(N - 1), x(N - 1), y(N - 1), used(N, false);
    loop(i, N - 1)
    {
        cin >> A[i] >> B[i];
        A[i]--;
        B[i]--;
        used[B[i]] = true;
        G[A[i]].emplace_back(B[i]);
    }
    loop(i, N) if (!used[i]) root = i;
    vector<ll> dist(N, -1);
    bfs(G, dist, root);
    dfs(G, root, -1);
    loop(i, N - 1) x[i] = dist[B[i]]; //dist[A[i]]+1でもよい
    loop(i, N - 1) y[i] = sz[B[i]];
    ll ans = 0;
    loop(i, N - 1)
    {
        ans += x[i] * y[i] % mod;
        ans %= mod;
    }
    putout(ans);
    return 0;
}

2020-12-21

yukicoder：No.1096 Range Sums

yukicoder 競技プログラミング

一部空のコードブロックがありますが、texの数式を正しく表示させるための応急処置なので許してください...

問題概要

yukicoder.me

$N$ 個の要素 $A_{i}$ からなる数列がある。

$\displaystyle \sum_{L=1}^{N} \sum_{R=L}^{N} \sum_{i=L}^{R} {A_{i}}$ を求めよ。

制約

$1 \leq N \leq 2×10^{5}$
$0 \leq A_{i} \leq 10^{6}$
答えは $10^{18}$ 以下に収まる

解法

まず、初期状態では範囲が広い $Σ$ が $3$ つ付いていて、愚直にやると計算に $O(N^{3})$ かかる。

累積和を用いれば各 $\displaystyle \sum_{i=L}^{R} {A_{i}}$ が $O(1)$ で計算できるようになるが、左側に $Σ$ が $2$ つ残っているので普通にやると間に合わない。

こういった問題でよく用いられる典型考察として、各要素が何回足されるかを考えるというものがある。

この考察が役立つAtcoder上の問題(ネタバレ防止のため隠してあります)

AGC005 B - Minimum Sum
Aiが答えに加算される回数を考えるところが本質です。
[https://atcoder.jp/contests/agc005/tasks/agc005_b]
ABC140 E - Second Sum
Minimum Sumの完全上位互換です。まだ解けてません(←?)
[https://atcoder.jp/contests/abc140/tasks/abc140_e]
第6回 ドワンゴからの挑戦状 予選 B - Fusing Slimes
スライムがxi,x(i+1)間を移動する確率をそれぞれ求めるのが本質という点で類似しています。
[https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_b]

$A_{i} (1 \leq i \leq N)$ は、 $L$ が $1$ 以上 $i$ 以下かつ $R$ が $i$ 以上 $N$ 以下のときにのみ足されるので、合計で $i(N-i+1)$ 回足されることになる。

実装上では $0$ -indexedで計算する必要があることに注意しながら足し合わせていけばよい。

計算量は $O(N)$ 。

コード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define mod 1000000007ll
#define loop(i, n) for (int i = 0; i < n; i++)
#define all(v) v.begin(), v.end()
#define putout(a) cout << a << '\n'
#define Sum(v) accumulate(all(v), 0ll)

int main()
{
    ll N, a, ans = 0;
    cin >> N;
    loop(i, N)
    {
        cin >> a;
        ans += a * (1 + i) * (N - i);
    }
    putout(ans);
    return 0;
}

課題残ってるけど毎日 $1$ 問位なんか解説書いたほうがいいかなと思って、投稿...

い、息抜き代わりということで...

2020-12-21

yukicoder：No.944 煎っぞ!

yukicoder 競技プログラミング

計算量解析を大分さぼったけど投げたらACできた...(あまりよろしくない)

問題概要

yukicoder.me

$N$ 個の要素からなる数列を、順序を維持したまま $k$ 等分( $k$ 個の連続部分列の要素の和が等しくなるように分ける)するときの $k$ の最大値を求めよ。

制約

$1 \leq N \leq 10^{5}$

$1 \leq A_{i} \leq 10^{2}$

解法

まず、 $N$ 個の要素の和 $S$ の最大値が $10^{7}$ と小さめであることに着目する。

$k$ 等分できるとき、 $k$ は $S$ の約数であることを考慮すると、約数の個数は $2×\sqrt{S}$ 個を超えないため(実際には大分少ない)、 $k$ の候補として $S$ の約数を全て調べても $1$ 回のチェックが $O(N)$ でできるので制限時間に間に合う。

枝狩りをしたところ $26ms$ でACできた。

コード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define mod 1000000007ll
#define loop(i, n) for (int i = 0; i < n; i++)
#define all(v) v.begin(), v.end()
#define putout(a) cout << a << '\n'
#define Sum(v) accumulate(all(v), 0ll)
template <typename T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b; // aをbで更新
        return true;
    }
    return false;
}
int main()
{
    ll N;
    cin >> N;
    vector<ll> A(N);
    ll maxx = 0;
    loop(i, N)
    {
        cin >> A[i];
        chmax(maxx, A[i]);
    }
    ll S = Sum(A);
    for (int i = N; i >= 1; i--)
    {
        if (S % i != 0 || (S / i) < maxx)
            continue;
        ll now = 0;
        bool ng = false;
        ll div = S / i; //各豆のおいしさ
        loop(j, N)
        {
            now += A[j];
            if (now > div)
            {
                ng = true;
                break;
            }
            if (now == div)
                now = 0;
        }
        if (ng || now != 0)
            continue;
        putout(i);
        return 0;
    }
    return 0;
}

2020-12-20

あ

あいさつ

お久しぶりです。kacho65535です。

競技プログラミングにはまっていたときにその場の勢いではてなブログを始めたものの全く更新していなかったので、その反省も兼ねて来年はちょこちょこ更新していきたいと思います。

なぜ更新をさぼっていたのかというと、単純に怠けていたのもありますが、大学が始まって忙しくなったりAtcoder Problemsで今埋めている最中の青diff中盤が自分の実力にあわず解けずに放置していたり、初見で分からなかった問題の解説を書く気が失せてしまったからです。

なんやかんやAtcoderを始めてから1年が過ぎようやく水色コーダーになれましたが、あまり競プロのモチベーションは上がっていないので改善していくためにatcoderではなく、あえてyukicoderの問題を簡単なところから埋めていきつつ解説記事を書いていけたらいいなと思っています。

2020-04-27

AtCoder Beginner Contest 164 E - Two Currencies

Atcoder 競技プログラミングダイクストラ法

解説が自分には難しかったので備忘録として書きます

問題

https://atcoder.jp/contests/abc164/tasks/abc164_e

$配点:500点$

解法

頂点間の距離に加えて、金貨銀貨の設定が加わっているため一気に複雑になります。幸い頂点数 $N$ と銀貨の運賃 $A_i$ の制約が、 $1\leqq N \leqq 50$ , $2\leqq A_i \leqq 50$ と抑え目になっているため、ここを生かすことを考えます。

制約からグラフは連結であることがわかるので、任意の2頂点間を移動するとき、最悪の条件でも運賃が銀貨 $50$ 枚である辺を $N-1$ 本移動移動すればたどり着けることがわかります。つまり、任意の頂点にいる時のコインの枚数は $0～50(N-1)$ 枚の範囲しか持つ必要がないことがわかります。(もっと言うと運賃の最大値を $A_M$ として $0～A_M (N-1)$ 枚の範囲)しかし、先ほどの制約からここは思い切って $0～2500$ 枚として考えてしまっても問題ないことがわかります。さて、一つの頂点上でコインを持つ状態を複数重ねるという実装をするときは、イメージ的には頂点の真上にエッジを張るようにして遷移させればよいです。要するに、頂点 $2501i+x (i=0,1,...,n-1,x=0,1,...2500)$ は頂点 $i$ で銀貨を $x$ 枚持つ状態を表す、として $2501n$ 個の頂点を持つグラフを構築したのちに普通のダイクストラ法で単一始点最短路を求めればよいです。

ここからは、具体的なグラフの構築方法のまとめです。

頂点上で金貨 $1$ 枚を $D_i$ 分かけて銀貨 $C_i$ に交換するという操作を表すために、まずは頂点 $i(i=0,1,...n-1)$ について、銀貨を $x$ 枚持っている状態から銀貨を $x+C_i$ 持っている状態へ、コスト $D_i$ の有向辺を張るという操作を $x=0～2499$ まで繰り返します。ここで注意したいのが、先ほど決めた添え字のルール上、どの頂点についても、銀貨を $2501$ 枚以上持つという状態を考えることができないので、 $x+C_i$ が $2501$ を超える場合は、辺を問答無用で銀貨 $2500$ 枚持っている状態に繋ぎます。(ここが公式の解説で"持ちきれない銀貨は捨てる"と表現されている部分)

次に頂点 $U_i$ , $V_i$ を結ぶ作業に入ります。まず、頂点の値が1-indexedだと扱いづらいので、どちらもデクリメントしておきます。次に、頂点 $U_i$ から頂点 $V_i$ に有向辺を結ぶ操作を考えます。移動には必ず正の枚数の銀貨を運賃として払う必要があるので、頂点 $U_i$ で銀貨を2500枚持っている状態をはじめとして段々と枚数を下げていけばよいです。運賃は銀貨 $A_i$ 枚なので、頂点 $U_i$ で銀貨を $y$ 枚持っているとして、実際の実装では頂点 $2501U_i+y$ から頂点 $2501V_i+(y-A_i)$ にコスト $B_i$ (移動にかかる時間)の有向辺を張ります。頂点 $U_i$ で銀貨の枚数が $A_i$ 未満ならば辺は張れないことに注意しましょう。これと全く同様の操作を頂点 $V_i$ から頂点 $U_i$ に対しても行えば、いよいよ目的のグラフの完成です！あとは始点を決めてダイクストラ法を実行すればよいのですが、銀貨の初期値 $S$ も2501以上は切り捨てるよう注意しましょう。あとはそれぞれの頂点への最短経路を求めて出力すれば終了です！お疲れ様でしたー！

コード

#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
struct edge
{
    long long to;
    long long cost;
};
typedef pair<long long, long long> P; //P.first:最短距離,P.second:頂点の番号
//頂点V個の負閉路なし重み付きグラフGにおける始点sからの最短距離を求める
long long VV;
vector<vector<edge>> G;
void dijkstra(vector<long long> &dist, long long s)
{
    //greater<P>によってfirstが小さい順に取り出される
    priority_queue<P, vector<P>, greater<P>> que;
    for (long long i = 0; i < VV; i++)
        dist[i] = 1e18;
    dist[s] = 0;
    que.push(P(0, s));
    //queが空になるまで繰り返す
    while (!que.empty())
    {
        P p = que.top();
        que.pop();
        long long v = p.second;
        if (dist[v] < p.first)
            continue; //すでに最短距離ならスルー
        for (long long i = 0; i < G[v].size(); i++)
        {
            edge e = G[v][i];
            //更新作業
            if (dist[e.to] > dist[v] + e.cost)
            {
                dist[e.to] = dist[v] + e.cost;
                que.push(P(dist[e.to], e.to));
            }
        }
    }
}
int main()
{
    cout << fixed << setprecision(30);
    long long N, M, S;
    cin >> N >> M >> S;
    VV = N * 2501; //とりあえず2500枚あれば安泰(0~2500の遷移)
    G.resize(VV);  //グラフを確保
    //入力受け取り
    vector<long long> U(M), V(M), A(M), B(M);
    vector<long long> C(N), D(N);
    for (long long i = 0; i < M; i++)
    {
        cin >> U[i] >> V[i] >> A[i] >> B[i];
        U[i]--;
        V[i]--;
    }
    for (long long i = 0; i < N; i++)
        cin >> C[i] >> D[i];
    //まずは同じ頂点の上部(銀貨が多い方向)へ向かう有向辺を結ぶ
    for (long long i = 0; i < N; i++)
    {
        for (long long j = 0; j < 2500; j++)
        {
            edge e;
            if (j + C[i] >= 2501)
                e.to = i * 2501 + 2500; //行きすぎたら切り捨てる(max2500枚)
            else
                e.to = i * 2501 + (j + C[i]);
            e.cost = D[i];
            G[i * 2501 + j].push_back(e);
        }
    }
    //次に違う頂点間を渡るとき銀貨の必要枚数だけ下るような有向辺を結ぶ(頂点の最下部(銀貨0)より下にいったら結ばない)
    for (long long i = 0; i < M; i++)
    {
        //uからvへの有向辺
        for (long long j = 2500; j >= 0; j--)
        {                                  //j=2500~>0,jはuの現在のコインの枚数
            long long nextcoin = j - A[i]; //nextcoin:vの現在のコインの枚数
            if (nextcoin < 0)
                break;
            edge e;
            e.to = V[i] * 2501 + nextcoin;
            e.cost = B[i];
            G[U[i] * 2501 + j].push_back(e);
        }
        //vからuへの有向辺
        for (long long j = 2500; j >= 0; j--)
        {                                  //j=2500~>0,jはvの現在のコインの枚数
            long long nextcoin = j - A[i]; //nextcoin:uの現在のコインの枚数
            if (nextcoin < 0)
                break;
            edge e;
            e.to = U[i] * 2501 + nextcoin;
            e.cost = B[i];
            G[V[i] * 2501 + j].push_back(e);
        }
    }
    vector<long long> dist(VV);
    dijkstra(dist, min(S, 2500ll)); //頂点0でコインをmin(S,2500)持っている状態からスタート
    //都市t(t=1~>N-1)について、各コインの状態を全探索(一応)
    for (long long i = 1; i < N; i++)
    { //i=1~>N-1
        long long ans = 1e18;
        for (long long j = 0; j <= 2500; j++)
            ans = min(dist[i * 2501 + j], ans);
        cout << ans << endl;
    }
    return 0;
}

2020-04-12

あ

概要

競技プログラミングの問題を解く過程や、解説でなるほどと思った小ネタを綴る(予定)

多分数項目書いて飽きると思うのでそこはよしなに...

自然数の逆数和は意外と大したことない

出典(ABC134-D)

そのまんま。自然数の逆数和(調和数)は発散するものの、そのスピードが極めて遅く、 $O(\frac{n}{1} + \frac{n}{2} +...+ \frac{n}{n})$ は $O(nlogn)$ で抑えられるため、 $n \leqq 10^{6}$ 位でも一見間に合わなそうだが(多分)間に合う

この解説がわかりやすい

$O(nlogn)$ で抑えられることの証明はこっち