Index Trio [モノグサプログラミングコンテスト2022（AtCoder Beginner Contest 249） D]

https://atcoder.jp/contests/abc249/tasks/abc249_d

前提知識

• 約数列挙

解説

https://atcoder.jp/contests/abc249/submissions/31211388

とある数xの約数列挙をO(sqrt(x))で行う方法がある。
もし分からない場合は「約数列挙」あたりで検索して、勉強してくる必要がある。
（今回は、naiveに約数列挙するより、区間で約数列挙を事前計算でしておいた方が早そうな気もするが…未検証）

何から考えるか

まずi,j,kの全列挙を考えてみる。これはO(N³)で当然間に合わない。
だが、経験則から、こういった添え字の列挙問題はどれか1つは全列挙して、他を最適化する方針が多い。
とりあえずiを全列挙して、他をうまく効率化できないか、使える性質を探してみよう。

約数

条件で、A[i] / A[j]というのがあるが、計算結果がA[k]になるかを考えるので、
この分数は計算すると整数になる必要がある。
iを全探索、つまり、A[i]を固定して他を最適に考えるとすると、A[j]というのはA[i]の約数である必要が最低限ある。
しかも、A[j]が定まればA[k]も一意に定まるので、実質A[i]が固定化されているときの選択肢はA[i]の約数個数分しかない。
これは使えそうな性質である。

約数を列挙する方法については、高速なやり方があるので、それを利用する。
約数の個数は問題にならないかという疑問があるが、「高度合成数」という概念があり、
2*10⁵だと160くらいが上限っぽいのでこれなら問題ない。

解法へ

以下を前計算しておく。
cnt[x] := A[i]=xとなるiの個数

iを全列挙してA[i]を固定化させたら、次は条件を満たすjを列挙する。
これは約数だけでいいので、代わりに、jの全列挙はA[i]の約数の全列挙をする。

とあるA[i]の約数divとなるjの個数はcnt[div]個であり、A[k]はA[i]/divとなるのでkの個数はcnt[A[i]/div]個となる。
jとkの組はどんな組でも問題ないので、cnt[div] * cnt[A[i]/div]通りが
その約数を使った時の条件を満たす組み合わせとなる。

あとは全部総和を取れば答え。

int N, A[201010];
int cnt[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cnt[A[i]]++;

    ll ans = 0;
    rep(i, 0, N) {
        auto divs = enumdiv(A[i]);
        fore(div, divs) {
            int cntJ = cnt[div];
            int cntK = cnt[A[i] / div];
            ans += 1LL * cntJ * cntK;
        }
    }
    cout << ans << endl;
}

Just K [モノグサプログラミングコンテスト2022（AtCoder Beginner Contest 249） C]

https://atcoder.jp/contests/abc249/tasks/abc249_c

前提知識

• bit全列挙

解説

https://atcoder.jp/contests/abc249/submissions/31208645

この問題ではbit全列挙が分かっているとスムーズに解くことができる。
bit全列挙については、他に詳しい解説があるので、そちらを参照して学習することをすすめる。

全列挙

競技プログラミングの基本は全列挙である。
今回、文字列を好きな個数選ぶことができるということであるが、Nがとても小さいので、
その文字列の選び方を全て列挙して検証することができる。

今回のような、選ぶ選ばないというのを全列挙するのに使えるのがbit全列挙である。
bitの01を選ぶ選ばないにマッピングすることで選択状態をbit列、ないし、数値として考えることができる。
全列挙するにあたってbit全列挙を使うことは必須ではないのだが、とてもお手軽な書き方であるし、
かつ、多くの解説がbit全列挙を前提に書いてあることが多いので、理解しておくといい。

とある選択方法について種類数を数える

全ての選択方法は列挙しても間に合うので、後はそれぞれの選び方について
『「選んだ文字列の中でちょうど K 個の文字列に登場する英小文字」の種類数』が計算できればいい。
これは全ての文字列に対して文字をカウントして、K個であるものを最後に数えればいい。
自分はmapを使って、

cnt[c] := 文字cが現れる回数

を選択した文字列に対して集計して、回数がK個である文字数を数えて、その最大値を取るようなコードを書いた。

int N, K;
string S[15];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> S[i];

    int ans = 0;
    rep(msk, 0, 1 << N) {
        map<char, int> cnt;
        rep(i, 0, N) if (msk & (1 << i)) fore(c, S[i]) cnt[c]++;

        int ok = 0;
        fore(p, cnt) if (p.second == K) ok++;
        chmax(ans, ok);
    }
    cout << ans << endl;
}

Keep Connect [ユニークビジョンプログラミングコンテスト2022（AtCoder Beginner Contest 248） F]

https://atcoder.jp/contests/abc248/tasks/abc248_f

前提知識

• （連結DP）

解説

https://atcoder.jp/contests/abc248/submissions/31047647

全くメジャーな言い回しではないが、連結DPをする。
ただ単に連結性を状態として持つDP。
一般にこの手のDPでは行列累乗を求めることが多いが、この問題ではそこまで要求もしておらず、
かつ、比較的シンプルな連結性の管理なので、連結DPの入門問題としてかなりいい問題。

DP？

連結DPになじみが無い人にとっては、この問題をDPで解くというのがなんともピンとこないかもしれない。
DPテーブルの定義としては、N列ある点の内、「i列目までの辺の有無が決定している」というのを使っていく。
最終的な条件として、グラフが連結であるということと、取り除く辺の本数も聞かれているので、
以下のようなDPを考える。

dp[cu][del][con]
:= cu列目まで辺の有無が決定していて、
既にdel本辺を削除していて、
上と下が連結しているかがcon（0非連結、1連結）
であるような辺の削除の仕方の組み合わせ

さて、cu列目まで確定していて、そこからcu+1列方面（ざっくり→方面）に辺を確定させると考えたときに
既にcu列目までですべて連結していれば、特に条件については問題ない。
しかし、非連結である場合、

連結成分 連結成分 cu+1列目  

のように横に連結成分が離れている場合は、それ以降で修復することはできない。
なので、修復可能な場合は

連結成分 cu+1列目  
連結成分 cu+1列目  

ちょっと分かりにくいかもだけれど、上下に連結成分が離れている場合のみである。
上下と書いたが、

┌―――  
└―　―  

このような感じでも後でつなげればいいので、上下に連結成分が分かれていると考えて問題ない。
よって、連結性についての状態は「0：上下に非連結」か「1：連結」だけを考えればいい。

初期状態

最初は1列目なので、縦の辺を使うか使わないかで判断する。

dp[1][0][1] = 1;  
dp[1][1][0] = 1;  

これは良いかなという感じ。

遷移

コの字で辺を使うかどうかを考える。
ソースコードを見てもらえばわかるが、どの辺を消したかを全通り人力で遷移を書いている。
全部で8通りなので、まだ人力でやれるレベルではあるが、注意しながらやること。
遷移の流れはコメントでソースコードにインラインで追加した。
そちらを見て理解してほしい。

int N, P;
int dp[3010][9010][2];

void chadd(int& x, int y) {
    x = (x + y) % P;
}

void _main() {
    cin >> N >> P;

    dp[1][0][1] = 1;
    dp[1][1][0] = 1;

    rep(i, 1, N) rep(del, 0, 9000) {
        // all -> ng

        // 2 del -> ‾
        // 上だけを残すので、連結状態であることが前提。遷移後は非連結
        chadd(dp[i + 1][del + 2][0], dp[i][del][1]);

        // 2 del -> _
        // 同上
        chadd(dp[i + 1][del + 2][0], dp[i][del][1]);

        // 1 del -> ‾|
        // 上と縦を残す。連結状態であることが前提。遷移後は縦があるので連結になる
        chadd(dp[i + 1][del + 1][1], dp[i][del][1]);

        // 1 del -> _|
        // 同上
        chadd(dp[i + 1][del + 1][1], dp[i][del][1]);

        // 1 del -> ‾_
        // 上下を残す。連結かどうかは問わず使えるが、連結状態は継承される
        chadd(dp[i + 1][del + 1][1], dp[i][del][1]);
        chadd(dp[i + 1][del + 1][0], dp[i][del][0]);

        // 0 del -> ‾_|
        // 全部残す。連結かどうかは問わずに使うことができ、どんな状態でも連結状態になる
        chadd(dp[i + 1][del][1], dp[i][del][0]);
        chadd(dp[i + 1][del][1], dp[i][del][1]);
    }

    rep(i, 1, N) {
        if (i != 1) printf(" ");
        printf("%d", dp[N][i][1]);
    }
    printf("\n");
}

K-colinear Line [ユニークビジョンプログラミングコンテスト2022（AtCoder Beginner Contest 248） E]

https://atcoder.jp/contests/abc248/tasks/abc248_e

解説

https://atcoder.jp/contests/abc248/submissions/31046558

幾何問題。
以下解法、非常に面倒なので、別の解法があるかも…

（解法に移る前に）

以下のケースでちょっとはまったので、WAではまってる人はこれを確認してみるといいかも。

6 3  
1 3  
1 4  
1 5  
6 10  
6 11  
6 12  

Infinityのとき

K=1の場合はどのような場合でも無数に解が存在する。
K=1の時は、Infinityと出して終了しよう。

どういった方針を取るか

今回は点を通る直線を題材とした問題であるが、直線は少なくとも2点があれば作成することができる。
逆に3点あると複数の直線ができてしまったり、色々面倒なので、2点を使った直線から解法が導けないか考えてみる。

ここから思考が飛ぶが、試行錯誤がこの間にあったと考えてほしい…

例えば、任意のa番目の点とb番目の点（a＜b）について直線を列挙していったときに、
同一直線状に3点ある直線は3回現れる。点abcを通っていれば、ab,ac,bcの列挙時に出てくる。
同一直線状に4点ある直線は6回現れる。点abcdを通っていれば、ab,ac,ad,bc,bd,cdの列挙時に出てくる。
つまり、同一直線についてはn点あれば、C(n,2)回現れることになる。（関数Cは二項係数）

よって、
cnt[ (ある直線を表す何らかの情報）] := 任意の2頂点を選んだときにある直線が何通りあるか
というのが計算できれば、その個数から直線に何個点があるかを逆算することができる。

『ある直線を表す何らかの情報』

自分はこれに傾きと切片を使った。
入力値が[-10⁹,10⁹]だったので、doubleは落ちそうな気配があり、有理数でどちらも保持する道を選んだ。
傾きをdx/dy, 切片をbup/bdownという風に有理数で定義して、2つの分数について正規化をすれば、
(dx, dy, bup, bdown)の数の組がとある直線を一意に表してくれるようになる。
以下の関数を作って計算している。

getParameter(a,b) := 2頂点a,bを通る直線を表す(dx, dy, bup, bdown)を返す

具体的には
https://blog.hamayanhamayan.com/entry/2018/09/30/203639
っぽいことをやる。

a = (ya - yb) / (xa - xb)
b = (xa * yb - xb * ya) / (xa - xb)

という感じで分数を作って、ソースコードにあるnormalization関数みたいに有理化する感じである。
(xa - xb)が0になるときが注意で、傾きは分子を1にするが、切片は分子をそのままにしている。
縦の直線なので、傾きと切片を定義はできないのだが、便宜上このようにして直線を同一視させている。

pair<ll, ll> normalization(ll up, ll down, bool slope = true) {
    if (down < 0) {
        up *= -1;
        down *= -1;
    }

    if (down == 0) {
        if (slope) up = 1;
    }
    else {
        ll g = gcd(abs(up), down);
        up /= g;
        down /= g;
    }

    return {up, down};
}

int N, K; ll X[301], Y[301];

tuple<ll, ll, ll, ll> getParameter(int a, int b) {
    ll dx = X[a] - X[b];
    ll dy = Y[a] - Y[b];

    tie(dy, dx) = normalization(dy, dx);

    // ya = dy * xa / dx + b
    // b = (ya * dx - dy * xa) / dx

    ll bup = Y[a] * dx - dy * X[a];
    ll bdown = dx;

    tie(bup, bdown) = normalization(bup, bdown, false);
    return { dy, dx, bup, bdown };
}

void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> X[i] >> Y[i];

    if (K == 1) {
        cout << "Infinity" << endl;
        return;
    }

    map<tuple<ll, ll, ll, ll>, int> cnt;

    rep(a, 0, N) rep(b, a + 1, N) cnt[getParameter(a, b)]++;

    map<int, int> rcomb;
    rep(n, K, N + 1) rcomb[n * (n - 1) / 2] = 1;

    int ans = 0;
    fore(p, cnt) ans += rcomb[p.second];
    cout << ans << endl;
}

Range Count Query [ユニークビジョンプログラミングコンテスト2022（AtCoder Beginner Contest 248） D]

https://atcoder.jp/contests/abc248/tasks/abc248_d

前提知識

• 二分探索

解説

https://atcoder.jp/contests/abc248/submissions/31044881

色々な解法が見える問題。
実際WaveletMatrixというデータ構造を使えば、一瞬で答えが出るのだが、二分探索解法で説明する。

以下、配列の要素については0-indexed（0始まり）で説明している。

手動でクエリを計算してみる

手動で答えてくださいと言われたら、L番目からR番目まで順番にXがあるかを見ていくような感じになると思う。
ここで、Xだけを見ることが出来れば、高速化できそうという気持ちになり、そういった方法を探してみる。

数が同じものをまとめておく

クエリを処理前の段階でとある数について、その数がある添え字（index）をまとめた配列を用意しておくことにする。

indexes[x] := 値がxである数列の要素の添え字の集合

具体的には入力例1 3 1 4 1 5であれば、

indexes[1] = { 1, 3 }
indexes[3] = { 0 }
indexes[4] = { 2 }
indexes[5] = { 4 }

というのをあらかじめ用意しておく。
こうすれば、とある数Xが含まれる場所は前計算で求めたこれを使えば高速に求められることになる。

要求問題が変わる

こうすると、要求される問題が以下のように変化する。

与えられた配列の中にLからRの数は何個あるか

これを計算するには二分探索が使える。
二分探索するためには配列がソートされている必要があるので注意。
自分の作成方法だと、構築すると既にソートされているが、実装によってはそうでないかもしれない。
自分の作成方法はコードを確認してほしい。

さて、二分探索で求めるのは、

• L以上の数が初めて現れる場所 st
• Rより大きい数が初めて現れる場所 gl

である。これが求まれば、個数はgl - stとなるので、これを求めればいい。

C++であれば、iteratorというのを理解する必要があるが、

• ソート済みの配列に対して～以上の数が初めて現れる場所はlower_bound
• ソート済みの配列に対して～より大きいの数が初めて現れる場所はupper_bound

で二分探索を意識しなくても計算することができる。
二分探索ではO(logN)の計算量なので、全体でO(QlogN)となって間に合う。

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

    map<int, vector<int>> indexes;
    rep(i, 0, N) indexes[A[i]].push_back(i);

    rep(q, 0, Q) {
        int L, R, X;
        cin >> L >> R >> X;
        L--; R--;

        auto st = lower_bound(all(indexes[X]), L);
        auto gl = upper_bound(all(indexes[X]), R);

        int ans = gl - st;
        printf("%d\n", ans);
    }
}

Dice Sum [ユニークビジョンプログラミングコンテスト2022（AtCoder Beginner Contest 248） C]

https://atcoder.jp/contests/abc248/tasks/abc248_c

前提知識

• 動的計画法

解説

https://atcoder.jp/contests/abc248/submissions/31043632

この問題では動的計画法を用いて、答えを作成していく。
動的計画法の入門の次の一手くらいの問題なので、全く分からないという方は他の入門サイトで学習してくることをすすめる。

何から始めるか

とある数列の構築方法の組数を計算する問題であり、かつ、modで組み合わせ数を計算するような問題である。
このような問題の解法として動的計画法は良く使われており、既視感から動的計画法を使った解法を考え始める人も多いだろう。
実際自分はノータイムでDPを考え始めたので、この部分は経験によって埋まる部分だと思う。

動的計画法

動的計画法と言えば、

dp[i] := 数列のi番目まで確定しているときの組み合わせ

なので、これをベースに考えてみよう。
数列は1～Mの数が選択できるので、M=3であるとすると、2番目までの作り方は以下の9通りである。

1 1  
1 2  
1 3  
2 1  
2 2  
2 3  
3 1  
3 2  
3 3  

この時、dp[2] = 9のように計算することができ、dp[3]を計算するためには、3番目を1～Mで選択した場合を考えて遷移を考える。
だが、今回の問題では最終的に数列の総和について条件が課されている。
ということは数列の長さという特徴以外に、総和という特徴も考慮して分類する必要が出てくることになる。
しかも、ここで重要なのが、総和さえ求めておけば、今までどんな数列が選ばれていたかは後の選択には影響しないということである。
つまり、総和が4である「1 3」と「2 2」は数列の3番目以降を選ぶという観点では、条件が全く同じになる。
よって、特徴として総和を選ぶことで最終的な条件判定はできるまま、計算をまとめてしまうことができるようになる。
次のようなDPを考えよう。

dp[i][sum] := 数列のi番目まで確定していて、これまでの総和がsumである組み合わせ

上の例でいうと、

dp[2][2] = 1
dp[2][3] = 2
dp[2][4] = 3
dp[2][5] = 2
dp[2][6] = 1

となる。

dp[i][sum]からの遷移としては、1～Mのいずれかnxtを選ぶような遷移になり、
dp[i + 1][sum + nxt] += dp[i][sum]
という感じでやっていくと良い。ソースコードを見てもらう方が分かりやすいかもしれない
。
このように状態が2つ以上になるDPも頻繁に出てくるので、DPの雰囲気をつかんだら、このような問題にも取り組んでみてほしい。

int N, M, K;
mint dp[51][3010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> K;

    dp[0][0] = 1;
    rep(i, 0, N) rep(sum, 0, K + 1) rep(nxt, 1, M + 1) dp[i + 1][sum + nxt] += dp[i][sum];

    mint ans = 0;
    rep(sum, N, K + 1) ans += dp[N][sum];
    cout << ans << endl;
}

Bishop 2 [AtCoder Beginner Contest 246 E]

https://atcoder.jp/contests/abc246/tasks/abc246_e

前提知識

• 拡張ダイクストラ

解説

https://atcoder.jp/contests/abc246/submissions/30681205

問題文とはxとyの解釈を逆にして説明している。
好みの問題ではあるのだが、つまり、チェス盤の上からy行目、左からx列目としてx,yを扱う。

今回の問題は最短経路問題であるため、最短経路問題と解くために使用されるダイクストラやBFSを
ベースに解法を作成していく。
これをベースに解法を考えていくと答えが導けたみたいな流れとなる。

拡張ダイクストラ

通常のダイクストラでは、頂点、つまり、場所だけを状態として考えて最短経路問題を行うが、
拡張ダイクストラでは、場所以外の何らかの情報（ないし状態）も合わせて状態を考えて最短経路問題を解くことを指す。
なので、状態の持ち方が変わるだけなので「拡張」という言葉をつける必要もないのだが、なんとなくついている。
（ググるときに便利なワードではあるが、誤用というか不適切では？と言われることも多いので注意）

さて、状態としてどのマスにいるかということ以外にコストに関わってきそうなことを考えてみよう。
ビショップはポーンが無ければコストを増やすことなくずっと進んでいくので、ダイクストラのような1手ずつ
進んでいくことを前提に考えると、直前に（最後に）どの方向に移動したかという情報があれば、
コストがかかるかどうかを判別できそうである。
なので、ダイクストラを行う場合に以下のような配列（グラフ的には頂点か）を考えて更新していく。

opt[y][x][dir] := マス(x,y)にいて、直前に進んだ方向がdirである場合の、最小手数

後は、ダイクストラをしていくだけなので、それほど難しくない。
自分のコードは以下。
https://atcoder.jp/contests/abc246/submissions/30679961

int N;
int Ax, Ay, Bx, By;
string S[1510];

template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
int dx[4] = { 1, 1, -1, -1 };
int dy[4] = { 1, -1, 1, -1 };
int opt[1510][1510][5];
bool vis[1510][1510][5];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    //cin >> Ax >> Ay >> Bx >> By;
    cin >> Ay >> Ax >> By >> Bx;
    Ax--; Ay--; Bx--; By--;
    rep(y, 0, N) cin >> S[y];

    min_priority_queue<pair<int, tuple<int, int, int>>> que;
    rep(x, 0, N) rep(y, 0, N) rep(dir, 0, 5) opt[y][x][dir] = inf;
    rep(x, 0, N) rep(y, 0, N) rep(dir, 0, 5) vis[y][x][dir] = false;

    opt[Ay][Ax][4] = 0;
    que.push({ 0, { Ax, Ay, 4 } });

    while (!que.empty()) {
        int x, y, dir;
        tie(x, y, dir) = que.top().second;
        que.pop();

        if (vis[y][x][dir]) continue;
        vis[y][x][dir] = true;

        if (x == Bx && y == By) {
            cout << opt[y][x][dir] << endl;
            return;
        }

        rep(d, 0, 4) {
            int xx = x + dx[d];
            int yy = y + dy[d];
            if (0 <= xx && xx < N && 0 <= yy && yy < N) {
                if (S[yy][xx] == '#') continue;
                if (chmin(opt[yy][xx][d], opt[y][x][dir] + (dir != d))) {
                    que.push({ opt[yy][xx][d], { xx, yy, d } });
                }
            }
        }
    }

    cout << -1 << endl;
}