先週末は ABC 2連発！ この記事は土曜の回です。
E/F ともに見当がつかなくて、D 完でした。
AtCoder Beginner Contest 127
- この連載記事では、着手した問題の考察を自分なりに書いていきます。
- 問題の詳細は問題一覧を参照してください。
A - Ferris Wheel
問題概要: A 歳の人が以下の料金体系の観覧車に乗るときの料金を求めよ。
- 13歳以上が乗るには B 円かかる
- 6歳以上12歳以下が乗るには B/2 円かかる
- 5歳以下の人は無料で乗ることができる
制約
- B: 偶数
考察
条件分岐をすればいいです。
余談ですが、Rust の if は式なので、計算結果を生成することが可能です。
println!(
"{}",
if A <= 5 {
0
} else if A <= 12 {
B / 2
} else {
B
}
)
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc127/submissions/5590342
B - Algae
問題概要: 藻類 (algae) の西暦 y 年における重さ x(y) が以下の漸化式で定まるとき、x(2001) から x(2010) を求めよ。
- 漸化式: x(y + 1) = r * x(y) - D
考察
ループを回せばいいです。
x は配列ではなく1個の変数で持つことも可能です。西暦 y についてループを回すとき、ループの開始時点では x = x(y - 1) が成り立ち、終了時点では x = x(y) が成り立つようにしておけば、順繰りに計算できます。
let mut x = X; // = x(2000)
for y in 2001..2011 { // y=2001 から y=2010 までループを回す
// ここでは x == x(y - 1)
x = r * x - D;
// ここでは x == x(y)
println!("{}", x)
}
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc127/submissions/5589395
C - Prison
問題概要: N 枚のカードと M 個のゲートがある。j 番目のゲートは L(j) 番目から R(j) 番目のカードのどれかを持っていれば通過できる。1枚だけですべてのゲートを通過できる ID カードの枚数を求めよ。
考察
カードとゲートの組み合わせをすべて試すと間に合わない (TLE になる) ので、工夫が必要です。
入力例2の図を書くと以下のようになります。すべてのゲートを通れるカードは 6 だけです。
カード
1 2 3 4 5 6 7 8 9 10
ゲート
1 . . o o o o . . . .
2 . . . . o o o . . .
3 . . . . . o o o o .
カード i ですべてのゲートを通れるための条件は、すべてのゲート j をカード i で通過できること、つまり ∀j. L(j) ≤ i ≤ R(j) です。これは max L(j) ≤ i ≤ min R(j) と同値になります。
したがって、L = max L(j) と R = min R(j) を計算して、L 以上 R 以下のカードの枚数 (R - min(R, L) + 1) を答えればいいです。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc127/submissions/5586994
ちなみに R - min(R, L) は「R から L を引くが、0 より小さくならない」という計算です。符号あり整数を使うときは max(0, R - L) の方がシンプル。
D - Integer Cards
問題概要: N 枚のカードが与えられる。i 番目のカードには整数 A(i) が書かれている。以下の操作を M 回行って、カードに書かれた整数の総和を最大にするとき、その最大値を求めよ。
- 操作 (j 番目): カードを最大 B(j) 枚まで選び、整数を C(j) に書き換える
考察: 最適手順
各操作の最適手順は明らかに以下です。
- 手順 (j 番目): C(j) 以下の整数がかかれたカードのうち、小さい順に最大 B(j) 枚を選んで、C(j) に書き換える
これは実際にシミュレートできます。
操作の後で同じ整数が書かれたカードが大量に発生するので、カード1枚1枚を配列に入れるのでは非効率です。代わりに、「ある整数のカード」が「何枚あるか」という形のペアを持つことにします。(これをランレングス圧縮というらしい？)
カードは常に小さい順に整列させておきたいです。こういうときはヒープ (優先度つきキュー) を使います。
ヒープに与えられたカードを挿入し、以下の操作を繰り返します:
- 手順 (j 番目):
- C(j) 未満の整数が書かれたカードをヒープのトップから取り出していく (最大 B(j) 枚まで取り出す)
- B(j) 枚以上を取り出してしまった場合は、残りをヒープに戻す
- 取り出したカードの数だけ C(j) をヒープに入れる
考察: 計算量
全体としては O((N + M) log (N + M)) 時間です。これはヒープにペア (a, n) (整数 a が n 枚あることを表す) をプッシュする操作を2通りに分類すると分かります。
- ヒープに新しくプッシュ
- 最初に N 回、各操作の後に最大1回
- ヒープからポップされて、数を減らして再プッシュ
- 各操作の後に最大1回
したがって、ヒープの要素数と操作回数は O(N + M) で収まります。
考察: 実装
Rust には標準ライブラリにヒープの実装の1つである二項ヒープ (BinaryHeap) があります。デフォルトでは降順に並んでしまいますが、値の順序を逆転するラッパーを使うと昇順にできます。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc127/submissions/5599583
想定解「ソートして足すだけだよ」
E - Cell Distance
問題概要: N×M の盤面に K 個のコマを置くとき、コマのペアのマンハッタン距離の総和を求めよ。
制約
- 2 ≤ N×M ≤ 2×10^5
- 2 ≤ K ≤ N×M
考察 (1次元)
数3の時間です。解説PDFを読んでも理解できなかったので、以下の記事を読みました:
参考: competitive: ABC 127 E - Cell Distance
1次元で考えるとよいらしいです。(このように変数を1つ潰すのは定石ですが、私は K=2 ばかり考えてしまった。)
N=1 のケースでは盤面は直線とみなすことができます。線上に K 個のコマを置いて、各ペアの X 座標の距離の総和を計算するという問題です。
N=1, M=5, K=3 だと以下の10通り。
###.. ##.#. ##..#
#.##. #.#.# #..##
.###. .##.# .#.##
..###
これら10通りにペアが3つずつあるので、合計30個の距離の総和を取るわけですが、重複がたくさんあります。例えば |0 - 1| は ##??? の形をした3つの状態から出現するので重複度は 3。? が3箇所あって、そこに1個のコマを置くからですね。他のペアについても同様です。
一般的にいうと距離 |a - b| は M 個のマスから a, b を除いた M-2 個に残りの K-2 個のコマを置く場合の数だけ重複するので、重複度は C(M - 2, K - 2) となります。
つまりコマのペアを列挙して「距離×重複度」の総和を計算すればよさそうですが、制約からコマのペアの全列挙はできないことに気づきます。
そこで ##??? と ?##?? と ??##? と ???## のように、コマ間の距離が同じであるようなペアについては同様の計算が成り立つことに注目します。1次元では、距離 d のコマのペアは M-d 個あるので、d を 1 から M-1 まで回して d(M - d) の総和を計算すればいいです。
結局 $_{M-2}C_{K-2} \sum_{d=1}^{M-1} d(M-d)$ が1次元 (N=1) での答えです。
考察 (2次元)
これを2次元に一般化します。
コマのペア a, b を決めたときの X 方向の距離 |a_x - b_x| は、前述のように残りのマス数 NM - 2 から残りのコマ数 K-2 を選ぶ組み合わせです。
X 方向の距離が d であるコマのペアの重複度は、X 座標は1次元と同様に M-d 通りの組み合わせですが、Y 座標がそれぞれ自由に選べて N 通りずつあるので、全体では N^2 (M - d) 通りです。
##... #.... #....
..... .#... .....
..... ..... .#... etc.
Y 方向の距離についても同様に求まります。
そういうわけで、以下の式が解になります。(Σn や Σn^2 の公式を使うと閉じた式にできますが、全体の計算量が落ちないので省略。)
$_{NM-2}C_{K-2} (N^2 \sum_{d=1}^{M-1} d(M-d) + M^2 \sum_{d=1}^{N-1} d(N-d))$
組み合わせの計算
組み合わせの場合の数の計算は、漸化式 (パスカルの三角形) を使った DP では O((NM)^2) 時間かかって TLE します。間に合わせる方法には、フェルマーの小定理や逆元 DP などがあります。
以下のコードでは逆元 DP を使っています。P を n で割ることで出現する等式
P = floor(P / n) * n + (P % n)
を変形して
1/n ≡ -floor(P / n) / (P % n) (mod P)
という漸化式を得ることにより 1/n を DP で求めるという手法です。
階乗 n! と階乗の逆元 1/(n!) を DP で求めて C(n, r) = n! / ((n - r)! r!) とすれば O(NM) 時間の事前計算で、O(1) 時間の関数 C(n, r) を構成できます。
- 参考: 1~nまでの逆元をO(n)で求める方法 - takapt0226's diary
- 参考: よくやる二項係数 (nCk mod. p)、逆元 (a^-1 mod. p) の求め方 - けんちょんの競プロ精進記録
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc127/submissions/5666123