ABC-only 回です。E 完でした。F は解けた気になりましたが WA/RE を出してしまって通りませんでした……

AtCoder Beginner Contest 132

この連載記事では、着手した問題の考察を自分なりに書いていきます。
- 前回: 競プロ参戦記 #53 Friendships | ABC 131
問題の詳細は問題一覧を参照してください。
- 問題一覧: https://atcoder.jp/contests/abc132/tasks

A - Fifty-Fifty

問題概要: 英大文字からなる長さ 4 の文字列 S が与えられる。S がちょうど2種類の文字からなり、かつ各種類の文字がちょうど2回ずつ出現するか、判定せよ。

A: 考察

条件を満たすパターンは以下の3通りなので、これを判定すればよいです。

AABB
ABAB
ABBA

文字列をアルファベットの配列にしてソートすれば、上記のパターンはすべて AABB 型になります。そのため、文字列をソートして AABB の形をしているかを判定した方が実装が楽です。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc132/submissions/6164615

Rust の文字列である String や str は、単純な文字の配列とはみなせないので、Vec<char> に変換しておくと実装しやすいです。

    // S: String とする

    let mut S = S.chars().collect::<Vec<_>>();

    S.sort();
    let ok = S[0] == S[1] && S[1] != S[2] && S[2] == S[3];
    println!("{}", if ok { "Yes" } else { "No" })

B - Ordinary Number

問題概要: 1 以上 N 以下の整数を並び替えた順列 P が与えられる。整数 i (1 < i < n) で、条件「p(i-1), p(i), p(i+1) のうち p(i) が2番目に小さい」を満たすものを数えよ。

B: 考察

「p(i-1), p(i), p(i+1) のうち p(i) が2番目に小さい」とは、要するに以下の2つの条件のどちらかが成り立つことです。

p(i-1) < p(i) < p(i+1)
p(i-1) > p(i) > p(i+1)

ループを回して条件を判定すればいいです。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc132/submissions/6163365

カウンタ変数 (y) の範囲に注意。

    // n: usize, p: Vec<i64>

    let mut count = 0;
    for y in 1..n - 1 {
        let x = y - 1;
        let z = y + 1;

        if (p[x] < p[y] && p[y] < p[z])
            || (p[x] > p[y] && p[y] > p[z]) {
            count += 1;
        }
    }

C - Divide the Problems

問題概要: 競技プログラミングの問題が N 個ある。i 番目の問題の難度は d(i) である。ある整数 K を決めたとき、難度 K 以上の問題を ARC 用に、K 未満を ABC 用にする。ARC 用と ABC 用の問題の数が同じになるような K の選び方を数えよ。

制約:

N: 偶数
d(i)≤10^5

C: 考察

d(i) の値が小さいので、工夫すれば K を全探索できます。

ABC 用の問題の個数と ARC 用の問題の個数を変数に持ちながら、K を 1 から 10^5 まで順繰りに大きくしていき、各 K について条件が成り立つか否かを判定すればいいです。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc132/submissions/6160796

D - Blue and Red Balls

問題概要: K 個の青いボールと、(N - K) 個の赤いボールがある。同色のボールは互いに区別できない。各 i (1≤i≤K) について、以下の操作を行うときに高橋くんの回収操作がちょうど i 回で完了するようなボールの並び方の総数を求めよ。(mod 10^9 + 7)

操作 1: これら N 個のボールを一列に並べる。
操作 2: 高橋くんが、連続して配置されている好きな個数の青いボールを回収する。この操作を繰り返す。ただし、高橋くんは操作回数が最小になるように行動する。

D: 考察

例えば N=8, K=5, i=2 としたとき、以下のような並びがあります。

    赤 青 青 青 赤 赤 青 青
       ^^^^^^

1回目の操作で ^^^ の部分の青玉が回収され、2回目の操作で残りが回収されると考えられます。回収する順番に関係なく、常に i=2 回の操作で青玉が回収されるので、この並びはカウント対象です。

要するに、青玉が連続して並んでいる区間がちょうど i 個あればいいです。

青玉の区間を分割する隙間に、少なくとも1つずつ赤玉が挟まっている必要がありますが、何個挟まっているかは独立なので、掛け算で数えられます。

    赤* 青+ 赤+ 青+ 赤*

青玉をちょうど i 個の区間に分割する場合の数を考えます。

i 個の区間には少なくとも1つずつの青玉が必要ですが、「はじめに i 個の青玉を脇において、残りの K-i 個の青玉の並びを決めた後に各区間に1個ずつ配る」と考えればいいです。(条件 K≥i に注意)

青玉 (K-i) 個をちょうど i 個の区間に分割します。これは典型的な重複組み合わせの問題です。区間の間の「仕切り (/)」を (i-1) 個用意して、青玉と混ぜて並び替えることを考えればいいです。

    青 青 / 青

この順列の決め方は、((K-i) + (i-1)) 個のうちどの (i-1) 個が仕切りであるかを選ぶことと同じです。そのため、場合の数は組み合わせにより計算できます。

    ((K-i) + (i-1))! / ((K-i)! * (i-1)!)

以上で青玉の並びの場合の数は分かりました。

赤玉についても、まず (N-K) 個のうち (i-1) 個は青玉を分断するのに必要なので脇におきます。(条件 N-K ≥ i-1 に注意)

赤玉を列の両端 (2箇所) か青玉の間 (i-1 箇所) のどこかに分配する場合の数を求めればいいわけですから、これは重複組み合わせで、青玉と同様の計算になります。

いつもどおり、階乗はDPで、逆元は繰り返し2乗法とフェルマーの小定理で求まります。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc132/submissions/6173463

E - Hopscotch Addict

問題概要: 有向グラフ G が与えられる。頂点 S から始めて、ちょうど3つの辺を辿って別の頂点に移動する操作を繰り返すことを考える。頂点 T に到達できるか判定し、到達できるなら最小の操作回数を求めよ。(3つの辺を辿る途中で頂点 T を通っても「到達した」とはみなさない。)

制約: N, M≤10^5

E: 考察

単一頂点対最短経路問題の亜種です。普通の最短経路問題 (1辺ずつ移動する) は幅優先探索 (BFS) で解けます。

一見、以下の手順で BFS に帰着できそうにみえました。「ある頂点 u から v まで、ちょうど3本の辺を通って移動できる」ときに辺 u → v が存在するような別のグラフ G' を考えると、グラフ G' の上で幅優先探索をするだけで解が求まりそうです。しかしこれは罠で、G' の辺が極めて多くなる (10^15 程度ある) ので TLE するはずです。

ちょうど3つの辺を辿って移動することの繰り返しで到達できるというのは、普通の BFS の視点からいえば「3の倍数の距離 で頂点に到達できる頂点には到達できる」と言いかえられます。

普通の BFS では一度踏んだ頂点には踏み込みませんが、いま考えている BFS では踏み込む必要があります。入力例にも見られる通り、同じ頂点を何度か通ることで、距離を3の倍数に調整して終点 T に到達できるケースがあるからです。

逆にいうと 3で割った余りが同じ距離 で同じ頂点に2回踏み込む意味はありません。2回目に同じ頂点を同じ (距離 % 3) で踏んでから、終点 T に行けるのであれば、1回目に踏んだ後に同じルートで終点 T に到達できるからです。最短経路は後者なので、前者は無視できます。

したがって、始点 S から始めて幅優先探索の順番でグラフを探索し、(頂点, 距離 % 3) が等しい状態に遷移したら探索を打ち切る、という手順で解けます。

最も時間がかかるのは到達できないケースですが、各頂点を3回ずつ踏めば停止するので、計算量は O(N + M) です。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc132/submissions/6176220

簡潔にまとめれば、以下のグラフ G' の上で BFS をするともいえます。

G' の頂点は (v, d) (ただし v は G の任意の頂点、d は 0, 1, 2)
G' の辺は (u, d) → (v, (d+1) % 3) (ただし u→v は G の任意の辺)