ARC 067 F - Yakiniku Restaurants 別解

editorial で紹介されている解法は だが，別解として と の 2 通りで解けたので ( の制約だとあまり差は出なさそう)．

問題

atcoder.jp

解法

基本的な考え方は，初めに訪れる焼肉店 を降順に動かしながら差分を計算するというもの．

焼肉店 で終了する場合の最適値と焼肉店 で終了する場合の最適値の差分 を管理する． を動かしたときに， を高速に更新することが出来れば， を固定した場合の最適値は として求まる．これは毎回愚直に求めても全体で である．

とする．

の更新には， 本の stack を用いる． 番目の stack を とし， には のペアを積んでいく．ただし， の場合は積まないものとする．

を動かすごとに，各 に対して を以下の手続きにより更新する．

1. とする．
2. が空でなく，かつ であるならば，3 へ．そうでなければ，4 へ．
3. の先頭 を pop する． ならば， として 2 へ．そうでなければ， に を push して 4 へ．
4. に を push する．

つまるところ， であるような に対応するペアを から取り除き，初めて となる に対してその差分を更新している．

に関しては， が pop される度に と更新し，push される度に と更新する．また，移動距離を考慮して とする必要がある．

および の更新にかかる計算量は一見すると であるが，実は となっている．

[tex: O(MN)] の理由

各 に対して更新回数が全体で となっていることが言えればよい．

手続きの 3. において push が起こる回数は，各 に対して高々 回 *1 で，合計 回である．また， 4. において push が起こる回数も各 に対して高々 回である．従って， への push が起こる回数は 回である． から pop する回数は への push の回数以下なので，pop の回数も である．

以上より，各 に対して，手続き全体にかかる計算量は である．

および の更新に ， を求めるのに かかるので，結局全体 でこの問題が解けた．

上の解法において， の定義を累積和に変更して区間 add，区間 max の遅延セグ木に載せれば となる．

実装 (Python)

提出リンク (AC)

def solve():
    N, M = map(int, input().split())
    A = [*map(int, input().split())]
    B = [[*map(int, input().split())] for _ in range(N)]
    d = [0] * N
    S = [[] for _ in range(M)]
    ans = 0
    for l in reversed(range(N)):
        if l < N - 1:
            d[l + 1] -= A[l]
        for j in range(M):
            v = B[l][j]
            while S[j] and v:
                x, y = S[j].pop()
                d[x] -= y
                if v >= y:
                    v -= y
                else:
                    S[j].append((x, y - v))
                    d[x] += y - v
                    break
            S[j].append((l, B[l][j]))
            d[l] += B[l][j]
        d_sum = 0
        for r in range(l, N):
            d_sum += d[r]
            ans = max(ans, d_sum)
    return ans

if __name__ == '__main__':
    print(solve())

*1:push が起こると即座に 4. へと移り，更新が終了するため

AtCoder Regular Contest 111 F - Do you like query problems?

めちゃくちゃ計算した．こんなんどうやったら時間内に解けるんだろう？ クエリの読み替えが本質だったっぽくて，これに気付くことが出来ればあるいは...？みたいな感じかもしれない．ただ，今の自分では厳しい...

問題

atcoder.jp

解法

以降，操作対象の数列を とし，0-indexed とする．

列全体の動作を考えるのは難しいので，数列の添え字 を固定して要素 1 つ 1 つに注目する．クエリの範囲は全部で 通りあるが，このうち が範囲内に含まれるのは かつ のときで，即ち 通り．これらの数を毎回書くと大変なので，, とおいておく．

解法 (泥臭いので読み飛ばしてもらってもよいです)

現在の の値を持てば DP が出来そうなので，DP テーブルを次のように定義してみる．

に関して，全ての に対して である．

個目のクエリが ，， である場合のそれぞれについて， への遷移を考える (集める DP)．

クエリ

がクエリの範囲内であるかどうかで更に場合分けをする．

が範囲内の場合

が範囲内となるような範囲の選び方は 通りである．

クエリにおいて となるのは，

• クエリの前は で， のクエリが飛んでくる場合
• クエリの前は で， のクエリが飛んでくる場合

の 2 つのケースが考えられる．従って，このケースの寄与は次の式 で表される．

が範囲外の場合

が範囲内となるような範囲の選び方は 通りである．

が範囲外の場合は元から である必要があり， の値は関係ない．従って，このケースの寄与は次の式 で表される．

クエリ

がクエリの範囲内であるかどうかで更に場合分けをする．

が範囲内の場合

が範囲内となるような範囲の選び方は 通りである．

クエリにおいて となるのは，

• クエリの前は で， のクエリが飛んでくる場合
• クエリの前は で， のクエリが飛んでくる場合

の 2 つのケースが考えられる．従って，このケースの寄与は次の式 で表される．

が範囲外の場合

クエリにおいて が範囲外の場合と全く同様であり，このケースの寄与は次の式 で表される．

クエリ

まず， クエリにおいて の値は変化しないので，任意の範囲に対して からの寄与があり， () からの寄与はない．従って， この場合の寄与は式 で表される．

また， クエリにおいてはクエリ自体による寄与が存在する． が範囲内である必要があるので，これは以下のように書ける．

ここで， が分からないので別で求める必要がある．

取り敢えずこの値を とおけば，クエリ自体の寄与は次の式 で表される．

以上 より， の表示は式 のようになる．

そして，この問題で求めたいのは を について和をとったものなので， を次のように定義する．

式 の両辺を について和をとって，式 を得る．

良い感じになってきたが， が分からないのでこれ以上は計算が進まない．そこで，以下は を求める．

まず， は定義より次のようになる．

そして， も とほぼ同様の漸化式を立てることが出来る．導出過程は省略し，結果を式 に示す．式 との違いは最終項の有無のみである．

ここで， の総和は実は問題文にその答えが書かれており，

である (もちろん普通に求めてもよい)．従って，更に式 の計算を進めることができ，

となる．これは以下のようにして について独立に解くことができる．

さて， の具体的な表示が得られたので式 に代入する．

この形の漸化式は両辺を で割ると解けて，

となる．式 より，求める答えは である．

ここで，

である．適切に計算すれば， は で求めることが出来る．

これだと道のりがかなり長く，あまり綺麗ではありません．そこで，クエリの解釈の仕方を変えてみます．

のとき， によって となるのは， のときです．一方， によって となるのは， のときです．そして，その他の場合では は変化しません ( のケースは都合のいいように解釈をしてもよいです)．ここで重要なのは， の値によらず， へと変化するのが 通りずつあり，何も変化しないのが 通りあるということです．

つまり， および をひとまとめにして考えると，これらは次の 2 つの操作に置き換えられます．

1. : へと更新する
2. : 何もしない

ここまで来れば， 回の操作後に となる場合の数 を一発で求められます．まず， が クエリの対象となるのは 通りです．また，クエリのパターン数は 通りだったので， クエリの対象とならないのは 通りということになります．

従って， 回の操作において一回も クエリの対象とならないのは 通りです．このとき，操作後の の値は です．

そして， 回の操作において一回以上 クエリの対象となるのは 通りです．このとき，操作後に となる場合の数は によりません．つまり， となる場合の数は 通りです．

以上より， は以下のように求められ，これは上で示した結果と一致しています．

そして，任意の 回の操作における クエリの出力の総和 に関する漸化式 :

に代入すると解ける形になるので，解いて を計算すれば AC が取れます (代入と漸化式の計算パートは折り畳み部分に書いています)．

実装 (Python)

提出リンク (AC)

P = 998244353

N, M, Q = map(int, input().split())

inv_2 = pow(2, -1, P)
C = (N + 1) * N * inv_2 % P
I = [(t + 1) * (N - t) % P for t in range(N)]
a = (2 * M + 1) * C % P
b = [M * I[t] % P for t in range(N)]

ans = 0
for t in range(N):
    v1 = I[t] * (M - 1) % P * inv_2 % P
    u1 = Q * pow(a, Q - 1, P) % P
    u2 = (pow(a - b[t], Q, P) - pow(a, Q, P)) * pow(b[t], -1, P) % P
    ans += v1 * (u1 + u2) % P
print(ans % P)

キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193)

F はすぐ解けたんだけど，E で詰まりに詰まった...

A - Discount

が答え．

B - Play Snuke

が答え．

1 行で書いてみた (Python)．

print(min(p for _, p, _ in L) if (L := [*filter(lambda t: t[0] < t[2], ([*map(int, input().split())] for _ in range(int(input()))))]) else -1)

C - Unexpressed

より， を満たす は高々 である．また， を固定すると， を満たす は高々 である．

従って，, , を満たす , の全探索は 時間で可能である．

注意しないといけないのは のような重複を除く必要があるという点で，これは既に現れた値を集合型で管理すれば可能である．

D - Poker

スコア計算式はハリボテで，その実は # の中身を全通り試して確率を計算する問題．実装が面倒．

既に確認されている 枚のカードを除いた 枚からランダムに残りの 枚を引くと考える． 枚のカードのうち， が書かれたカードの枚数を とすると，高橋君が ，青木君が を引く確率 は次のように表される．

引いた , を加味したスコアを計算し，高橋君の方が高ければ を答えに加算すればよい．

E - Oversleeping

時刻 に高橋君が降車に成功することと，次の 2 つが成り立つことは同値である．

制約をよく見るとそれぞれの区間長が小さいので，全探索ができる．つまり，, と決め打って以下のような連立合同式へと変換する．

連立合同式を満たす最小の非負整数は中国剰余定理を用いて求められる．

F - Zebraness

令和 ABC でフローが出題されたのは初めて？

二値変数がいくつかあって，その関係によって変化するコストを最小化する問題はグラフの最小カットに帰着できる場合がある (燃やす埋める)．

今回の問題では，下図のような辺の張り方をすればよい．ただし，u と v は隣接する ? マスである．

図: 辺の張り方

SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192)

43:47 + 0:00 全完で全体 46 位，日本人 39 位でした．賞金ワンチャンないかな...？

A - Star

コイン 100 枚で 1 up するアレかな？ が答え．

B - uNrEaDaBlE sTrInG

char[] s = sc.nextChars();
boolean y = true;
for (int i = 0; i < s.length; i += 2) {
    y &= Character.isLowerCase(s[i]);
}
for (int i = 1; i < s.length; i += 2) {
    y &= Character.isUpperCase(s[i]);
}
pw.println(y ? "Yes" : "No");

C - Kaprekar Number

やるだけなんだけど実装方針が決まらず迷子に．

long n = sc.nextInt();
int k = sc.nextInt();
long x = n;
for (int i = 0; i < k; i++) {
    if (x == 0) break;
    long _x = x;
    int p = 0;
    while (_x > 0) {
        _x /= 10;
        p += 1;
    }
    int[] c = new int[p];
    int q = 0;
    _x = x;
    while (_x > 0) {
        c[q++] = (int) (_x % 10);
        _x /= 10;
    }
    Arrays.sort(c);
    long g1 = 0, g2 = 0;
    for (int j = 0; j < p; j++) {
        g1 = g1 * 10 + c[j];
        g2 = g2 * 10 + c[p - j - 1];
    }
    x = g2 - g1;
}
pw.println(x);

D - Base n

順位表が真っ赤っか．雑にやるとオーバーフローするのと，桁数が 1 の時がコーナーケースになることが原因？

二分探索で毎回 以下になるかを調べればいい．制約は厳しくないので，BigInteger を使っても TL には間に合いそうということで投げると通る．

char[] _x = sc.nextChars();
int n = _x.length;
int[] x = new int[n];
for (int i = 0; i < n; i++) {
    x[i] = _x[i] - '0';
}
int d = IntArrays.max(x);
long m = sc.nextLong();
if (n == 1) {
    pw.println(x[0] <= m ? 1 : 0);
    return;
}
BigInteger bm = BigInteger.valueOf(m);
long l = d, r = m + 1;
Out: while (r - l > 1) {
    BigInteger t = BigInteger.valueOf((l + r) >> 1);
    BigInteger v = BigInteger.ZERO;
    for (int i = 0; i < n; i++) {
        v = v.multiply(t).add(BigInteger.valueOf(x[i]));
        if (v.compareTo(bm) > 0) {
            r = t.longValue();
            continue Out;
        }
    }
    l = t.longValue();
}
pw.println(l - d);

E - Train

Dijkstra をやる．ボトルネック部に剰余演算が追加されて重くなりそうだったので，隣接リストを配列で持って定数倍高速化をした．結果的に多分要らなかったんだけど，万が一の TLE を考えると払ってもいい対価だったと思う．

public static void solve(ExtendedScanner sc, FastPrintStream pw) {
    int n = sc.nextInt();
    int m = sc.nextInt();
    int x = sc.nextInt() - 1;
    int y = sc.nextInt() - 1;
    Edge[] edges = new Edge[m];
    int[] cnt = new int[n];
    for (int i = 0; i < m; i++) {
        int u = sc.nextInt() - 1;
        int v = sc.nextInt() - 1;
        long t = sc.nextLong();
        int k = sc.nextInt();
        
        edges[i] = new Edge(u, v, k, t);
        cnt[u]++;
        cnt[v]++;
    }
    Edge[][] g = new Edge[n][];
    for (int i = 0; i < n; i++) {
        g[i] = new Edge[cnt[i]];
    }
    for (var e : edges) {
        int u = e.u;
        int v = e.v;
        g[u][--cnt[u]] = e;
        g[v][--cnt[v]] = new Edge(v, u, e.k, e.t);
    }

    long[] d = new long[n];
    PriorityQueue<State> pq = new PriorityQueue<>();

    java.util.Arrays.fill(d, Const.LINF);
    d[x] = 0;
    pq.add(new State(x, 0L));
    while (pq.size() > 0) {
        State st = pq.poll();
        int u = st.v;
        if (st.d != d[u]) continue;
        for (var e : g[u]) {
            int v = e.v;
            int k = e.k;
            long c = e.t;
            long r = d[u] % k;
            long du = r == 0 ? d[u] : d[u] + k - r;
            if (du + c < d[v]) {
                d[v] = du + c;
                pq.add(new State(v, d[v]));
            }
        }
    }

    if (d[y] == Const.LINF) {
        pw.println(-1);
    } else {
        pw.println(d[y]);
    }
}

private static final class State implements Comparable<State> {
    final int v;
    final long d;
    State(int v, long d) {this.v = v; this.d = d;}
    public int compareTo(State s) {return d == s.d ? v - s.v : d > s.d ? 1 : -1;}
}

static class Edge {
    int u, v;
    int k;
    long t;
    Edge(int u, int v, int k, long t) {
        this.u = u;
        this.v = v;
        this.k = k;
        this.t = t;
    }
}

F - Potion

選んだ素材の集合を ， とする．

制約より が保証されているため， であることが丁度 となるための必要十分条件．このとき の時間が掛かる．

に対して，次の DP を考える．

この DP は以下のようにして計算でき， が を固定した場合の最適値である．

計算量は だが，適切に , の範囲を絞れば定数倍が 1 よりも小さくなり，余裕を持って通すことができる．

AtCoder Regular Contest 006 D - アルファベット探し

特に学び的なことはなかったけど，かなり面倒そうに見える問題が楽に解けたので．

問題は ↓ から．

atcoder.jp

解法

各 # マスから上下左右 + 斜め 4 方向の合計 8 方向に存在する # マスへ辺を張ったグラフを考えると，A, B, C はすべて連結であることに着目する．等倍の A, B, C に対応する連結成分の大きさはそれぞれ 12, 16, 11 で全て異なるので，これを使って判定することを考える．なお，制約より図形が重なることはないので 2 つ以上の文字が同じ連結成分に属することはない．

連結成分の大きさが のアルファベットを 倍拡大すると，拡大後の連結成分の大きさは となる．

従って，Union-Find や幅優先探索により各連結成分の大きさ を取得し，

を満たす , を決定する問題へと落とすことができた．

が持つ素因数 および の数に着目することで， および対応するアルファベットは次のように求められる．

1. のとき: 空マス．
2. が素因数 を奇数個持つとき: で，対応するアルファベットは C．
3. が素因数 を奇数個持つとき: で，対応するアルファベットは A．
4. 上記以外: で，対応するアルファベットは B．

以上より，幅優先探索を用いることにすれば全体 でこの問題を解くことが出来る．

重複数珠順列

ほぼ自分用のメモなので色々雑かも．

問題

問題文

円周上に 個の玉が等間隔で並んでおり，それぞれの玉に色を塗ることを考える．色は の 色があり，複数の玉を同じ色で塗ってもよいし，使われない色があってもよい．玉に色を塗る方法の数を で求めよ．ただし，回転や裏返しによって一致する塗り方は 通りとして数えるものとする．

制約

• 
• 

解法

コーシー・フロベニウスの定理 (バーンサイドの補題とも) が適用できる (バーンサイドの補題 - Wikipedia)．

以下，適当な玉を起点として反時計回りに玉 と名前を付ける．また，玉 に塗る色を とする．回転および裏返しに対応する群は二面体群 であり，いま は集合

に作用している．

円を反時計回りに 回転する作用素を とおく． に対して の作用前後で一致する条件を考えると，

が成り立つことが必要十分条件であると分かる．従って，

である．

続いて，円を玉 と円の中心を通る軸 で折り返す作用素を とおく． は， と を用いて次のように表示できる．

は，円の中心を中心として軸 を だけ回転した対称軸に対応する．

が奇数であれば，対称軸は必ずある頂点とその向かいの辺の中点を通る直線となるので，

である．

一方， が偶数であれば，対称軸が向かい合う二頂点を通るケースと向かい合う二辺の中点を通るケースが交互に現れる．従って，

である．

以上の結果から，問題の答えを するとこれは以下のように表せる．

しかし，このまま計算すると となってしまうので工夫する必要がある．

注目すべきは， の値が取り得る値は の約数に限られるという点である．そこで， の値ごとに をまとめて足し上げることを考える．つまり，

という式変形を行う．以下， とする ( より， は整数であることに注意)．

ここで， となるためには が必要であり，また， なので

である．ただし， はオイラーのトーシェント関数である．以上より，次が成り立つ．

あとは， を求めればよい． を の素因数全体の集合とすると

であり， は約数列挙の要領で で求められるので，結局 も で求められる．

の制約の下で の約数は最大でも 個なので，和の計算は十分高速に行うことができ，この問題を解くことが出来た．

結論

なお，裏返しを考慮しない場合の答え は，そのまま裏返し部分を消せばよく，次のように求められる．

AtCoder Beginner Contest 190

2 連続橙 perf で黄色復帰！！めでたい．

A - Very Very Primitive Game

• なら高橋君の勝ち
• なら青木君の勝ち
• なら のとき青木君， のとき高橋君の勝ち

int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
if (a > b) {
    pw.println("Takahashi");
} else if (b > a) {
    pw.println("Aoki");
} else {
    pw.println(c == 0 ? "Aoki" : "Takahashi");
}

B - Magic 3

かつ を満たす が存在すれば Yes, そうでなければ No．

int n = sc.nextInt();
long s = sc.nextLong();
long d = sc.nextLong();
boolean ok = false;
for (int i = 0; i < n; i++) {
    long x = sc.nextLong();
    long y = sc.nextLong();
    ok |= x < s && y > d;
}
pw.println(ok ? "Yes" : "No");

C - Bowls and Dishes

人の人がそれぞれ と のどちらに置くかの 通りを全探索し，幾つの条件が満たされているかを愚直に数えてその最大値を求めればよい．これは全体 で計算できる．

int n = sc.nextInt();
int m = sc.nextInt();
int[] a = new int[m];
int[] b = new int[m];
for (int i = 0; i < m; i++) {
    a[i] = sc.nextInt() - 1;
    b[i] = sc.nextInt() - 1;
}
int k = sc.nextInt();
int[][] cd = new int[k][2];
for (int i = 0; i < k; i++) {
    cd[i][0] = sc.nextInt() - 1;
    cd[i][1] = sc.nextInt() - 1;
}
int max = 0;
for (int s = 0; s < 1 << k; s++) {
    boolean[] put = new boolean[n];
    for (int i = 0; i < k; i++) {
        put[cd[i][(s >> i) & 1]] = true;
    }
    int cnt = 0;
    for (int i = 0; i < m; i++) {
        if (put[a[i]] && put[b[i]]) cnt++;
    }
    max = Math.max(max, cnt);
}
pw.println(max);

D - Staircase Sequences

初項 ，公差 ，項数 の等差数列の和は である．いま， で固定なので， を満たす整数 , の組の個数が求まればよい．ただし， は項数なので である．

両辺に を掛けてやると，条件式は と書き直せるので， の値としてあり得るのは の正の約数のみであることが分かる．

を の約数として， と置くと もまた整数であり， が成り立つ．これを について解くと， となるので， が偶数であれば は整数となり条件を満たす．( の範囲に関する制約は存在しない)

まで試し割りして約数を列挙すれば，全体 で解くことが出来る．

long n = sc.nextLong() * 2;
long cnt = 0;
for (long x : MathUtil.divisors(n)) {
    long y = n / x;
    cnt += 1 ^ ((y - x + 1) & 1);
}
pw.println(cnt);

E - Magical Ornament

少し隠されてはいるが，TSP を解けばよいことが分かる．

辺 を張ったグラフを作って各 に対して を始点に BFS を行うことで，任意の に対して を結ぶ最短経路長 が求まる．

あとは， に対して重み の辺を張ったグラフに対して TSP を解けば OK．答える列の長さは 経路長 +1 となるのでそこだけ注意する． 回の BFS と TSP を合わせると，全体の計算量は ．

実装量は少し多いが，すべて典型的な実装なのでさほど大変ではないと思う．

int n = sc.nextInt();
int m = sc.nextInt();
IntArrayList[] _g = new IntArrayList[n];
for (int i = 0; i < n; i++) {
    _g[i] = new IntArrayList();
}
for (int i = 0; i < m; i++) {
    int u = sc.nextInt() - 1;
    int v = sc.nextInt() - 1;
    _g[u].add(v);
    _g[v].add(u);
}
int[][] g = new int[n][];
for (int i = 0; i < n; i++) {
    g[i] = _g[i].toArray();
}
int k = sc.nextInt();
int[] c = sc.ints(k, e -> e - 1);

// BFS
int[][] ds = new int[k][n];
for (int i = 0; i < k; i++) {
    int[] d = ds[i];
    IntDeque dq = new IntDeque();
    Arrays.fill(d, -1);
    d[c[i]] = 0;
    dq.addLast(c[i]);
    while (dq.size() > 0) {
        int u = dq.removeFirst();
        for (int v : g[u]) {
            if (d[v] >= 0) continue;
            d[v] = d[u] + 1;
            dq.addLast(v);
        }
    }
}

// TSP
long[][] dp = new long[k][1 << k];
for (int i = 0; i < k; i++) {
    Arrays.fill(dp[i], Const.LINF);
    dp[i][1 << i] = 1;
}
int[][] bits = BitUtil.bits(k);
for (int s = 1; s < 1 << k; s++) {
    if (bits[s].length <= 1) continue;
    for (int v : bits[s]) {
        int p = s ^ (1 << v);
        for (int u : bits[p]) {
            if (ds[u][c[v]] < 0) continue;
            dp[v][s] = Math.min(dp[v][s], dp[u][p] + ds[u][c[v]]);
        }
    }
}
long ans = Const.LINF;
for (int i = 0; i < k; i++) {
    ans = Math.min(ans, dp[i][(1 << k) - 1]);
}
pw.println(ans >= Const.LINF ? -1 : ans);

F - Shift and Inversions

初めの一回は普通に転倒数を求める (これは有名かつ頻出なので理解した上でライブラリ化しておくとよさそう)．先頭の要素を末尾に移動したときの転倒数の差分が分かればよい．

移動する要素を として， より大きい要素は 個，小さい要素は 個存在するので，差分は である．あとは，この差分を足しこむ操作を 回繰り返しながら出力すればよい．

全体の計算量は，初回の転倒数を求める部分が で，他は線形時間で動作するので ．

注意点といえば，転倒数は最大で なので 32 bit 整数で計算するとオーバーフローする可能性があることくらい？

int n = sc.nextInt();
int[] a = sc.ints(n);
long inv = InversionNumber.solve(a);
pw.println(inv);
for (int i = 0; i < n - 1; i++) {
    inv += n - 1 - 2 * a[i];
    pw.println(inv);
}