ABC-only 回です。E完でした。

AtCoder Beginner Contest 129

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

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