ABC-only 回です。E 完でした。F は解けた気になりましたが WA/RE を出してしまって通りませんでした……
AtCoder Beginner Contest 132
- この連載記事では、着手した問題の考察を自分なりに書いていきます。
- 問題の詳細は問題一覧を参照してください。
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 の任意の辺)