LoginSignup
1

More than 3 years have passed since last update.

競プロ参戦記 #50 Sum Equals Xor | ABC 129

Last updated at Posted at 2019-06-09

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1