ABC-only 回です。E完でした。
AtCoder Beginner Contest 129
- この連載記事では、着手した問題の考察を自分なりに書いていきます。
- 問題の詳細は問題一覧を参照してください。
A - Airplane
問題概要: 空港 A, B, C がある。どの空港の間にも双方向に飛行機が運航している。AB間の飛行時間をP、BC間をQ、CA間をRとする。ある空港から別の空港へ飛行機で移動し、さらに別の空港に飛行機で移動するとき、飛行時間の総和の最小値を求めよ。
A: 考察
例えば A → B → C と移動するとき、飛行時間は AB 間と BC 間の飛行時間の和で、P + Q です。
経路の向きの違い (例えば A → B → C と C → B → A) は飛行時間と関係ありません。そのため、 移動方法を選ぶ代わりに、どの空港間を通るかだけ考えればよい です。
したがって、飛行時間の総和としてありうるのは P+Q, P+R, Q+R の3通りです。これらの最小値が解となります。
最小値の計算には std::cmp::min 関数を使うと便利です。
min(P + Q, min(P + R, Q + R))
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc129/submissions/5843638
B - Balance
問題概要: N 個の重りがある。i 番目の重りの重さは W(i) である。T 番目 (1≤T<N) までの重りの重さの和を S(1)、他の重りの重さの和を S(2) とおくとき、|S(1) - S(2)| の最小値を求めよ。
B: 考察
N が小さいので、すべての T について S(1), S(2) を計算して、最小値を求めればよいです。
イテレータの総和を計算する関数 sum はだいたい型引数 (::<>) が必要なので注意しましょう。
// 単純な実装例
let mut min_diff = std::i64::MAX;
for T in 1..N {
let S1 = W.iter().take(T).sum::<i64>(); // 前から T 個の重さの総和
let S2 = W.iter().skip(T).sum::<i64>(); // 前から T 個を除いた重さ
min_diff = min(min_diff, (S1 - S2).abs()); // 最小値を更新
}
println!("{}", min_diff)
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc129/submissions/5841430
B: 高性能な解法
上のコードは実質2重ループなので O(N^2) 時間かかりますが、もっと性能のいい解法があります。
S1, S2 をそれぞれ S(1), S(2) の値を持つ変数とします。はじめ、T=0 における S1, S2 を計算しておきます。そして、ループの中で T を 1 ずつ増やす際に、S1, S2 も新しい T の値に合わせて適切に更新します。
こうすれば T に対して総和 S(1), S(2) が常に求まった状態になるので、ループの内側が O(1) 時間になり、全体として O(N) 時間になります。
let mut T = 0;
let mut S1 = 0; // 前から T 個の重さの総和
let mut S2 = W.iter().sum::<i64>(); // 前から T 個以外の重さの総和
let mut min_diff = std::i64::MAX;
while T < N {
// T を1増やす
S1 += W[T]; // 「前から T 個」の重りが1つ増えるので重さの和に加算する
S2 -= W[T]; // 「前から T 個以外」の重りが1つ減る
T += 1;
min_diff = min(min_diff, (S1 - S2).abs());
}
println!("{}", min_diff)
筆者の提出 (Rust, AC): https://atcoder.jp/contests/abc129/submissions/5860655
C - Typical Stairs
問題概要: N 段の階段がある。A(i) 段目には乗れない状態になっている。上り口 (0段目) から始めて、1段か2段ずつ上るとき、最上段までの上り方を数えよ。
C: 考察
i 段目に上る経路の数を考えます。
i = 0 は特殊で、はじめから0段目にいるので、経路の数は 1 とみなします。(空の経路が存在するため。)
i 段目が乗れない状態なら、そこに上る経路は存在しないので、0 通りです。(これは A(i) を集合に入れておけば高速に判定できます。)
i 段目に乗れるとしたら、1段前から1段上るケースと、2段前から2段上るケースがあるので、それらの経路数の和を求めればよいです。
注意点として、i = 1 のとき「2段前」が存在しませんが、「2段上って1段目に行く経路」なるものは存在しないので、そこは 0 通りです。
結局、「2段前に上る経路の数」と「1段前に上る経路の数」を変数として持ちながら「いまの段 (i 段目) に上る経路の数」を i=N まで順繰りに計算していくことで解けます。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc129/submissions/5839434
D - Lamp
問題概要: H×W のグリッドがあり、いくつかのマスに障害物が配置されている。あるマスにランプを置くと、そのマスから上下左右方向に、障害物までの範囲が照らされる。障害物のない1つのマスにランプを1個置くとき、照らされるマスの個数の最大値を求めよ。
D: 考察
はじめに全探索を考えましたが、H, W ≤ 2000 なので、「各マスにつき、そのマスにランプを置いたときに照らされるマスの数を数える」ような O(H^2 W^2) 時間のアルゴリズムは間に合いません。
極端なケース、例えば H=1 のケースを考えます。
H=1, W=7
1234567
1 ....#..
これを見ると、ランプを左の4マスのどこに置いても照らされるマスの数は4つです。障害物を挟んだ右側についても、ランプの位置によらず2マスが照らされます。
このグリッドに他の行があったとしても、「あるマスにランプを置いたときに照らされる 同じ行の マスの個数」(= row(y)(x)) は同じです。
したがって、row(y)(x) を各マスについて 事前に求めておくことが可能 です。
同様に、「あるマスにランプを置いたときに照らされる同じ 列 のマスの個数」(= column(y)(x)) も同様に計算しておくとします。
そうすると、各マス (y, x) につき、同じ行・列について照らされるマスの個数が row(y)(x) + column(y)(x) - 1 と計算できます。全体として O(HW) 時間です。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc129/submissions/5845770
E - Sum Equals Xor
問題概要: 整数 L が与えられる。以下の条件を満たす、非負整数のペア (a, b) を数えよ。
条件: a + b = a xor b ≤ L
E: 考察
条件 a + b = a xor b の方を考えます。もし各桁の組み合わせが以下のように「繰り上がり」が生じなければ、(+) と xor は一致します。
逆にどこかで繰り上がりが生じるなら、一致しません。繰り上がりが起こる桁の、一つ上の桁が合わないからです。
a = 101
b = 001
^ 繰り上がりが起こる桁
v ここが合わない
xor 100
(+) 110
そういうわけで、(a, b) の各桁に (0, 0), (0, 1), (1, 0) のどれかを割り当てる場合の数を数える問題に帰着しました。
a + b ≤ L の条件を維持しながら (a, b) の上位桁から順番に決めていく DP (桁DP) によって解けます。
DP テーブルの設計はこうです:
- dp(i)(eq) = n ⇔
- (a, b) の上から i 桁の決め方の場合の数が n に等しい
- eq = 1 ⇔ (a, b) の上から i 桁の和が、L の上から i 桁と一致する
- dp(0)(1) = 1
- 上から 0 桁の決め方は「なし」一択なので 1 通り
- (a, b) の上から 0 桁の和は 0 で、L の上から 0 桁の和 (当然 0) と一致するため、eq = 1
遷移を考えます。
簡単なのは eq = 0 からの遷移で、このときは常に (0, 0), (0, 1), (1, 0) の3通りがあります。
- dp(i + 1, 0) ← dp(i)(0) * 3
eq = 1 からの遷移は L(i) の値で場合分けが必要です。
- L(i) = 0 のとき
- (a, b) の i 桁目の和が 1 になると a + b が L を超えてしまうのでダメ
- (a, b) の i 桁目は (0, 0) の一択
- dp(i + 1)(1) ← dp(i)(1)
- L(i) = 1 のとき
- (a, b) の i 桁目を (0, 0) にすると、上から (i + 1) 桁が一致しなくなる (a + b の方が小さくなる) ので、遷移先は eq = 0
- dp(i + 1)(0) ← dp(i)(1)
- (0, 1), (1, 0) のどちらかにすると、上から (i + 1) 桁が一致するので eq = 1 に遷移
- dp(i + 1)(1) ← dp(i)(1) * 2
結局、比較的シンプルな桁DPで解けます。教育的。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc129/submissions/5848461
なお回答で使っている ModInt 型は、簡単にいうと整数の「P で割った余り」を表す型です。加算などの演算子をオーバーロードしていて、自動で余りを取るようになっています。
F - Takahashi's Basics in Education and Learning
問題概要: 初項 A, 公差 B, 長さ L の等差数列 S が与えられる。S(n) = A + n B である。この数列の各要素を10進展開して、文字列連結したものを10進数として読んだ数を X とする。X を M で割った余りを求めよ。
F: 考察
本番では考察の半ばまでは合っていましたが、行列に持ち込むことを思いつかなかったので、等比級数を展開できずに解けませんでした。
一般に x, y の10進数展開の連結は、y の桁数を d とするとき x * 10^d + y という和・積で書けます。例:
x=31, y=415
31415
= 31000 + 415
= 31 * 10^3 + 415
y の桁数 d が定数だったら 、S が等差数列であることから、式は等比級数に変形できそうな形になります。例えば S = (11, 22, 33) を10進数で繋いだ式は以下です。
112233
= 1122 * 10^2 + 33
= ((11 * 10^2) + 22) * 10^2 + 33
= 11 * 10^4 + 22 * 10^2 + 33
= Σ 10^(2n) 11 (3-n) (n=0,1,2)
これは罠で、このシグマを計算するのは大変だと思います。代わりに、解説 PDF に書かれている通り、行列累乗 によって解決できます。
そういうわけで考察を進めていくと、手順としては以下のようになります。
- 等差数列を桁数が同じ範囲で分割する (二分探索)
- X=0 から始めて、桁数 d が一定の要素を X にすべて連結する (d = 1, 2, .., 18 で繰り返す)
例えば、
A=2, B=40, L=5
S = 3, 42, 82, 122, 162
~~ ~~~~~~~~ ~~~~~~~~
1桁 2桁 3桁
X = 0 (初期条件)
→ 3 (1桁の要素を連結)
→ 34282 (2桁の要素を連結)
→ 34282122162 (3桁の要素を連結)
「数列の桁数が同じ範囲」は、言い換えると「桁数 d に対して 10^(d-1) 以上 10^d 未満の範囲」です。
「n 未満の要素の個数」を求める二分探索を2回行なって、「10^d 未満の要素の個数から、10^(d-1) 未満の要素の個数を引く」ことで範囲の幅が求まります。(等差数列だから要素の値は計算で出せるので、幅だけ求めれば十分。)
次に数列の要素を連結した整数 X の計算を考えます。
再帰的に考えて、ある要素まで連結した整数 X が求まったと仮定します。はじめは X=0 です。数列の次の要素が s で、その桁数が d のとき、遷移は以下のように書けます。
X' = X * 10^d + s
s' = s + B
これは行列の積を使って以下のように書けます。(見づらいですが、「縦ベクトル＝行列×縦ベクトル」という式のつもり。)
[ X' ] [ 10^d 1 0 ] [ X ]
[ s' ] = [ 0 1 B ] [ s ]
[ 1 ] [ 0 0 1 ] [ 1 ]
この掛け算を繰り返すとき、桁数 d が一定である範囲が n 個連続する部分は、行列の n 乗をかけることで省略できます。d を定数だと思えば、この行列も定数だからです。繰り返し二乗法を使うと O(log L) 時間です。
数列の「桁数が d である範囲」を処理した後の X, s を各 d について次々に求めていくことで X が求まります。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc129/submissions/5913838