はまやんはまやんはまやん

hamayanhamayan's blog

Collision [AtCoder Beginner Contest 209 D]

https://atcoder.jp/contests/abc209/tasks/abc209_d

前提知識

解説

https://atcoder.jp/contests/abc209/submissions/24156786

この問題はアルゴリズム力が要求される問題。
何が分かれば問題が解けるかという所から考えていく。
なお、想定解法は全然違います。

何が分かれば問題が解けるか

この問題は木上の2点間の距離が分かれば、解くことができる。
距離が偶数であれば頂点上で出会うし、距離が奇数であれば道上で出会う。
まずは、この部分に気付く所が第一段階になる。

木上の2点間の距離

木上の2点間の距離を解く問題はアルゴリズム的な典型問題であるので、それを適用して解いていく。
この部分が本質ではあるのだが、この部分は他方でも多く解説されているので、適当に以下にまとめておく。
意外と要求知識も多くLCAを求める段階もそれほど簡単ではない。
だが、汎用的に使えるのでライブラリを持ってない場合は整備しておくことを勧める。

想定解法

2部グラフか…なるほど、賢い…

int N, Q;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;

    HLDecomposition hld;
    hld.init(N);

    rep(i, 0, N - 1) {
        int a, b; cin >> a >> b;
        a--; b--;
        hld.add(a, b);
    }
    hld.build(0);

    rep(i, 0, Q) {
        int c, d; cin >> c >> d;
        c--; d--;

        int len = hld.distance(c, d);

        if (len % 2 == 0) printf("Town\n");
        else printf("Road\n");
    }
}

Not Equal [AtCoder Beginner Contest 209 C]

https://atcoder.jp/contests/abc209/tasks/abc209_c

前提知識

  • modつき計算

解説

https://atcoder.jp/contests/abc209/submissions/24156090

問題をそのまま受け取ると難しい問題。
mod 109 + 7での計算ができることが前提条件。
とりあえず解きたい場合はAC Library Modintを使って解いてもいいと思う。

条件を見直す

条件が2つである。

  • 1~Cの範囲内に数を収める必要がある
  • もう1つ数をかぶらせることができない

ここで1つ思考のbreakthroughを起こす必要がある。
それは「数を割り当てる順番に特に指定はない」ということである。

競技プログラミングのテクとして、配列のソートができる場合はソートすることで解ける場合があるというのがある。
今回の配列Cはソートをしたものを考えても最終的な答えは変わらない。
今後、配列Cはソート済みであると仮定する。

ソート後はどうか

ソートした後に先頭から順番に決めていくことにする。
最初の数A[0]は1≦A[0]≦C[0]となり、これはC[0]通りの組み合わせがある。

2番目の数A[1]は1≦A[1]≦C[1]、かつ、A[0]でない数である。
配列Cはソート済みなので、A[0]は必ず1からC[1]の間にあることが分かる。
よって、組合せはC[1]-1通りの組み合わせとなる。

3番目の数A[2]は1≦A[2]≦C[2]、かつ、A[0]でもA[1]でもない数である。
配列Cはソート済みなので、A[0],A[1]は必ず1からC[2]の間にあることが分かる。
よって、組合せはC[2]-2通りの組み合わせとなる。

これを順番に行っていけば、各部分の組み合わせが求められるので、総積を取れば答えになる。

int N, C[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> C[i];
    sort(C, C + N);
    
    mint ans = 1;
    rep(i, 0, N) ans *= C[i] - i;
    cout << ans << endl;
}

Can you buy them all? [AtCoder Beginner Contest 209 B]

https://atcoder.jp/contests/abc209/tasks/abc209_b

解説

https://atcoder.jp/contests/abc209/submissions/24155585

問題で指定されているように偶数番目の商品は定価の1円引きで購入して、奇数番目の商品は定価通りで購入したとして
合計金額を計算していこう。
これと所持金X円を比較して、買うことができるかできないかを判定しよう。

特に注意点はないが、実装時に配列は0-indexedなので、実装的には偶数奇数は反転したように見える。
0-indexedはindexが0から始まっているという意味で使用している。

int N, X, A[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> X;
    rep(i, 0, N) cin >> A[i];

    int tot = 0;
    rep(i, 0, N) {
        if (i % 2 == 0) tot += A[i];
        else tot += A[i] - 1;
    }
    
    if (tot <= X) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Counting [AtCoder Beginner Contest 209 A]

https://atcoder.jp/contests/abc209/tasks/abc209_a

解説

https://atcoder.jp/contests/abc209/submissions/24155463

制約を見るとA≦Bが保証されていないので、それに気を付ける必要がある。
普通にA~Bでループを回せば、A≦Bでない場合はループが回らないだけなので、問題ない。
B-A+1をして負になったら0を返すというのでもいいかと思う。

int A, B;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> A >> B;
    int ans = 0;
    rep(x, A, B + 1) ans++;
    cout << ans << endl;
}

Digit Products [AtCoder Beginner Contest 208 E]

https://atcoder.jp/contests/abc208/tasks/abc208_e

前提知識

解説

https://atcoder.jp/contests/abc208/submissions/23995133

桁DPの知識が必要になる。
桁DPに慣れていれば真っ先に桁DPが思い浮かびそうな問題設定であるので、
もし知らない場合は桁DPについて学習してきてほしい。
より簡単な問題もある。
この先知っている前提で話を進める。

桁DPのDPテーブル

以下のようなDPテーブルで計算を行う。

dp[digit][isLess][leadingZero][seki] :=
上からdigit桁目まで確定していて
既にNよりも小さいかどうかがisLess(=1なら既に小さい)であり、
まだ先頭の0であるかがleadingZeroであり、
各桁の数字の積がsekiである数の個数

digit, isLess, leadingZeroは桁DPでは普通に使うものなので特に説明しない。
(流派によって使ったり使わなかったりするかも)
ここでこの問題固有なのがsekiの部分である。

seki

アレなネーミングはさておき、ここに積を置いたら状態数がKになってダメでは?という疑問がある。
しかし、問題の性質上、ここはそれほど組み合わせ数が無く、状態に積を置くことができる。
各桁は0~9になるので、素因数的に考えると、2,3,5,7しか使われない。
例えば全部2であると仮定しても60個くらいしか含むことができない。
なので、雑に計算して、全部60個としても604通りくらいだが、どう考えてもそれよりかはむっちゃ減る。
他の状態数も大したことないので、これは普通に間に合いそうと判断できる。
実際はちゃんと積の個数を計算した方がいい。

DP計算

まず、DP定義についてだが、こういった、数は大きくなりうるが使用される状態数がそれほど多くない
という場合はmap(dictionary型)で定義して使用するのがいい。
後は桁DPに従って頑張って書いていくしかない。

一応自分の実装について方針を軽く書いておく。
dp[digit][isLess][leadingZero][seki]から、nxtという数をdigit桁に置く場合を考える。
~2は次の状態。

  • digit2はdigit+1(1桁確定するので)
  • isLess2はnxtが現在の数より小さかったら1(=true)になる、そうでないならisLessのまま
  • leadingZero2はnxtが0以外なら0(=false)になる、そうでないならleadingZeroのまま
  • sekiはnxtをかける(leadingZeroが1ならまだ数が始まってないのでかけない)

注意点として最初の状態はdp[0][0][1][1]=1であるということと、sekiは基本K以下で打ち切ればいいのだが、
Kより大きくなっても0が出てきたら総積が0になるので問題ない。
よって、Kより大きくなった場合でも切り捨てるのではなくinfとしてKより大きいというひとくくりの状態として
保持していく。
あとは、桁あふれとかに注意。
桁DPはとにかくバグるので頑張ってほしい。

string N; int K;
map<int, ll> dp[20][2][2];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    int M = N.size();

    dp[0][0][1][1] = 1;
    rep(digit, 0, M) rep(isLess, 0, 2) rep(leadingZero, 0, 2) fore(p, dp[digit][isLess][leadingZero]) {
        int seki = p.first;
        ll com = p.second;

        int cur = N[digit] - '0';

        rep(nxt, 0, 10) {
            if (isLess == 0 && cur < nxt) continue;

            int digit2 = digit + 1;

            int isLess2 = isLess;
            if (nxt < cur) isLess2 = 1;

            int leadingZero2 = leadingZero;
            if (0 < nxt) leadingZero2 = 0;

            int seki2 = seki;
            if (leadingZero2 == 0) {
                if (K < 1LL * seki * nxt) seki2 = inf;
                else seki2 *= nxt;
            }

            dp[digit2][isLess2][leadingZero2][seki2] += com;
        }
    }

    ll ans = 0;
    rep(isLess, 0, 2) fore(p, dp[M][isLess][0]) if (p.first <= K) ans += p.second;
    cout << ans << endl;
}

Shortest Path Queries 2 [AtCoder Beginner Contest 208 D]

https://atcoder.jp/contests/abc208/tasks/abc208_d

前提知識

解説

https://atcoder.jp/contests/abc208/submissions/23994717

ワーシャルフロイドを正確に理解していれば解ける問題。
いや、この問題を理解することがワーシャルフロイドを正確に理解することを助けるのかもしれない。
ワーシャルフロイドの知識がない前提で説明を試みる。
前半はほぼフィクションです。

何から手を付けようか

クエリ問題への取り組み方の1つとして差分計算だけすることで高速化するという方針がある。
状況を整理してみると、kの値が増えることで使える遷移が増えて、差分的な要素が出てくる。
なので、kの値を1から増やしていくことで差分計算ができないかということを考える。

初期状態

初期状態を考えよう。
今回はk=0から始めてみよう。
(k=1からじゃないの?という突っ込みはちょっと置いておいて…)
これで一旦f(s,t,0)を考えてみると、使えるのはs->tへの直接の遷移だけとなる。
これを頭において、二次元配列にマッピングしてみる。

dist[s][t] := sからtへ移る場合の最短距離

これを定義すると、k=0の場合は、

dist[i][i] = 0 (同じ場所の場合は0)
dist[A][B] = C (直接遷移がある場合)
dist[other][other] = inf (遷移が無い場合は∞)

到達できない場合は他の最短距離でも良くやっているようなinfにしておく。
これが初期状態となる。

差分計算

この状態からk=1を考えてみよう。
これは遷移の経由点として1が使えるようになっていることになる。
端的にはs->1->tができるようになったことになる。
なので、1を経由したパターンだけを見て最短経路の更新をしていこう。
つまり、

dist[s][t] = min(dist[s][t], dist[s][1] + dist[1][t])

で更新していくことになる。
こうすると1を経由する遷移をすべて反映させたdist配列が用意される。
こうやって更新すると、f(s,t,1) = dist[s][t]となっている。
なので、これを答えに足し合わせていこう。

更にもう一歩差分計算

同様にもう一歩計算してみよう。

dist[s][t] = min(dist[s][t], dist[s][2] + dist[2][t])

これをやると、dist[s][2]の間は1が考慮された最短経路になっているし、dist[2][t]の間も同様に1が考慮された最短経路になっている。
なのでdist[s][t]は2以下が考慮された最短経路になっている。
よって、この差分計算を進めていくとkがインクリメントされていって、上手く計算ができる。

で、これをやっているアルゴリズムがワーシャルフロイドになる。

計算量

実際に実装してみて眺めてみるとはっきり理解ができると思うが、差分計算をk=1~NまでN回行うのでO(N)、
差分計算自体の計算量はsとtの列挙をやるのでO(N2)
よって全体O(N3)となり、間に合う。

int N, M;
int dist[401][401];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;

    rep(i, 0, N) rep(j, 0, N) dist[i][j] = inf;
    rep(i, 0, N) dist[i][i] = 0;

    rep(i, 0, M) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        dist[a][b] = c;
    }

    ll ans = 0;
    rep(k, 0, N) {
        rep(i, 0, N) rep(j, 0, N) chmin(dist[i][j], dist[i][k] + dist[k][j]);
        rep(i, 0, N) rep(j, 0, N) if (dist[i][j] < inf) ans += dist[i][j];
    }
    cout << ans << endl;
}

Fair Candy Distribution [AtCoder Beginner Contest 208 C]

https://atcoder.jp/contests/abc208/tasks/abc208_c

解説

https://atcoder.jp/contests/abc208/submissions/23993957

シミュレーションを高速化することを考える。
今回は2段階で分配が行われる。

  1. 持っているお菓子がN個以上なら1個ずつおかしを配る
  2. N個未満になったら、国民番号が小さい方から余りを配っていく

それぞれを高速化することを考える。

分配1

この部分が一番時間がかかる所なので、ここを解決できるかが山。
例えばK=1018でN=2*105だと、かなり時間がかかってしまうことが分かると思う。

説明のため、もう少し小さい例で考えてみる。

K=10でN=3の場合、分配1を1回やって

K=7で分配済みは1,1,1

となる。さらにもう一回やると、

K=4で分配済みは2,2,2

最後にやると、

K=1で分配済みは3,3,3

となる。
これを眺めてみると、分配1をやれるだけやり切ったときに、

残るKはKをNで割った余り
各人に分配された個数はKをNで割った切り捨て

になっていることが分かる。
よって、分配1の操作はKをNで割った余りにして、各個々人にK/Nを配った状態にしておこう。
自分の実装では、allという変数を用意して、みんなにそれぞれall個配ったということを記録しておくことにした。

分配2

後は残っている個数もN個未満なので、ループで配っていけば間に合う。
問題が、国民番号が小さい方から配っていくという部分だが、色々な手段があって、どれを使ってもいい。

  • 特殊なソートをする
  • pairで持ってソート
  • priority_queueを使う

なんでもいいのだが、自分は特殊なソートを使った。
C++ではsortの比較に使う関数を自分で実装ができるので、ord配列(=orderの略として使ってます)で国民の添え字を保持しておき、
ソート時には添え字ではなく、国民番号で昇順ソートするように記載をした。
これでord配列の先頭からK人を指定して配っていく。
この差分をdiff配列で管理して起き、分配1で配られた個数を足して答えるとAC

int N; ll K;
int a[201010];
int diff[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> a[i];

    // 分配1
    ll all = K / N;
    K %= N;

    // 分配2
    vector<int> ord;
    rep(i, 0, N) ord.push_back(i);
    sort(all(ord), [&](int i, int j) { return a[i] < a[j]; });
    rep(i, 0, K) diff[ord[i]]++;

    // 集計と答え
    rep(i, 0, N) {
        ll ans = all + diff[i];
        printf("%lld\n", ans);
    }
}