Help us understand the problem. What is going on with this article?

競プロ参戦記 #71 Many Many Paths | ABC 154

AtCoder Beginner Contest 154 に参加しました。考察を書いていきます。結果はぎりぎり滑りこんでの全完でした。

A - Remaining Balls

問題概要: 文字列 S の書かれたボールが A 個あり、文字列 T の書かれたボールが B 個ある。文字列 U が与えられる。文字列 U が書かれたボールを1つ捨てた。文字列 S, T の書かれたボールがそれぞれ何個残っているか求めよ。

制約:

  • S≠T
  • S=U または T=U

A: 考察

制約を見ると、S=T=U のケースは考えなくていいようです。

U=S なら A を1減らし、U=T なら B を1減らせばよいです。

筆者の提出 (Rust, AC): https://atcoder.jp/contests/abc154/submissions/9976949

B - I miss you...

問題概要: 英小文字からなる文字列 S が与えられる。S のすべての文字を x に置き換えたものを求めよ。

B: 考察

イテレータの map を使うと、「すべての文字を x に置き換える」を表現できます。

    S.chars().map(|_| 'x').collect::<String>()

筆者の提出 (Rust, AC): https://atcoder.jp/contests/abc154/submissions/9972413

C - Distinct or Not

問題概要: 整数列 A(1), ..., A(N) が与えられる。どの2つの要素も互いに異なるかどうか判定せよ。

制約: 2≤N≤200000

C: 考察

「どの2つの要素も互いに異なる」は「すべての i, j (1≤i < j≤N) について A(i) ≠ A(j)」と形式化できます。しかし実際に i, j を列挙するループを回すと O(N^2) 時間かかり、実行時間制限を超過します。

解決策は複数ありますが、楽なのは集合 (std::collections::HashSet または std::collections::BTreeSet) を使う方法です。

集合には同じ要素が1つまでしか入らないので、A(i) の値をすべて集合に入れてみて、すべての値が集合に入ったら (= 要素数が N だったら) 重複がないと分かります。集合への要素の挿入は十分高速で、HashSet なら償却 O(1)、BTreeSet なら O(log N) です。全体で O(N) 時間となり、時間制限に間に合います。

筆者の提出 (Rust, AC): https://atcoder.jp/contests/abc154/submissions/9971129

別解として、ソートする方法が考えられます。もし A に同じ要素が含まれているなら、ソートするとそれらの要素は必ず隣接します。そのため、ソート後に隣接している要素のペアを調べるだけで、重複の有無を判定できます。判定に O(N) 時間、ソートに O(N log N) 時間なので間に合います。

D - Dice in Line

問題概要: N 個のサイコロが一列に並んでいる。左から i 番目のサイコロは、振ると 1 以上 p(i) 以下の整数が等確率で1つ出る。隣接する K 個のサイコロを選んでそれぞれ独立に振る。出る目の合計の期待値の最大値を求めよ。

制約: N≤200000

D: 考察

サイコロは左右の区別がつくので 1, 2 と 2, 1 が区別される点に注意。

例として K=N=2, p=(2, 3) の全事象を書き下してみます。

1つ目 2つ目
1 1 2
1 2 3
1 3 4
2 1 3
2 2 4
2 3 5

それぞれ確率 1/6 で起こるので、期待値は (2+3+4+3+4+5)/6 = 21/6 = 3.5 です。

期待値は 線形性 を持つので、「出目の合計の期待値」は「出目の期待値の合計」に一致します。実際、

  • 1つ目のサイコロの出目の期待値は (1+2)/2 = 1.5
  • 2つ目のサイコロの出目の期待値は (1+2+3)/3 = 2

なので、出目の期待値の合計は 3.5 になり、上で計算した「出目の合計の期待値」と一致しています。

そこで、i 番目のサイコロの期待値を計算して合計すれば K=N での答えが出せます。

(i 番目のサイコロの出目の期待値)
= 1/p(i) + 2/p(i) + ... + p(i)/p(i)    (期待値の定義を使った)
= (1 + ... + p(i)) / p(i)              (分子をまとめた)
= (1/2・p(i)・(p(i) + 1)) / p(i)        (等比級数の公式を使った)
=  1/2・(p(i) + 1)                      (約分した)
= (p(i) + 1) / 2
(N 個のサイコロの出目の合計の期待値)
= (N 個のサイコロの出目の期待値の合計)
= (Σp(i) + N) / 2

次に K < N のケースも含めて考えます。幅 K の各区間について同様に和を計算すれば、最大値が求まります。しかし2重ループでこれをすると O(KN) 時間かかって TLE です。

和の計算を省略することを考えます。a+b+c+d+e の和が分かっているとき、b+c+d+e+f は (a+b+c+d+e)+f-a に変形すればたった2回の計算 (+f, -a) で計算可能です。

    a+b+c+d+e
      b+c+d+e+f

はじめに K 個の各サイコロの期待値の和を計算しておけば、残りの N-K 通りの区間における期待値の和は、期待値の足し引きにより O(1) で求まります。全体として O(N) 時間であり、間に合います。

筆者の提出 (Rust, AC): https://atcoder.jp/contests/abc154/submissions/9986685

E - Almost Everywhere Zero

問題概要: 正の整数 N が与えられる。1 以上 N 以下の整数で、10進数で表したときに0でない桁がちょうど K 個あるようなものを数えよ。

制約: N≤10^100, 1≤K≤3

E: 考察

問題のタイトル「ほとんど至るところゼロ」がヒントになっていて、最大で 100 桁もある整数のうち最大 K 桁しか 0 でないということは、逆にいうと、ほとんどの桁がゼロであるような整数を数えるということです。あーそういうことね。桁DPで解けそうです。

制約をよく見ると K が 1, 2, 3 の3通りしかありません。これは「桁 DP を書いても解けるけど、実は、手で場合分けしたら短いし O(1) でエレガント」というやつなのかな、と思って場合分けしてみました。

まず K=1 のときは、

  • 一番上の桁が N と一致するケース (これを =00 と書きます)
    • 1通り
  • 一番上の桁が N より小さく、0でないケース (これを *00 と書きます)
    • N の一番上の桁を d とすると d-1 通り
  • 一番上の桁が 0 のケース (090/009)
    • N を h 桁とすると h-1 個のどこかに 1-9 のどれかを配置すればいいので 9(h-1) 通り。

次に K=2 のときは、

  • 一番上の桁が N と一致するケース
    • 上から2桁目が 0 でないケース
      • 上から2桁目も一致するケース (==00)
        • 1通り
      • 上から2桁目が N より小さく、0 でないケース (=*00)
        • 上から2桁目を d2 とすると d2-1 通り
      • 上から2桁目が 0 のケース
        • (h-2) 桁のどこかに 1-9 なので 9(h-2) 通り。
  • ...

このあたりでやめておけばよかったんですが……。完全に方針ミスなので反省しています。

結局、次の典型的な桁 DP で解けます。

  • dp 表 dp[i][k][eq]
  • 状態
    • 上から i 桁は決定済み
    • 上から i 桁のうち 0 でない数字は k 個
    • 上から i 桁が N と一致するとき eq=1、そうでなければ eq=0
  • 遷移
    • 実装を参照

筆者の提出 (Rust, AC): https://atcoder.jp/contests/abc154/submissions/10004596

F - Many Many Paths

問題概要: 2次元平面上の点 (0, 0) から x または y 方向に 1 進む操作の繰り返しで点 (r, c) に至るまでの経路の個数を f(r, c) とおく。整数 r1, r2, c1, c2 が与えられる。f(r, c) (r1≤r≤r2, c1≤c≤c2) の総和を mod 10^9+7 で求めよ。

F: 考察

x 方向の移動を →、y 方向の移動を ↑ で表すと、(0, 0) から (r, c) への経路は r 個の → と c 個の ↑ の順列で表せます。(どこか見たことがありました。)

f(r, c) は (r+c) 個の矢印のうちどの r 個が → なのかを選ぶ場合の数なので、C(r+c, r) です。その総和を書いてみます。

Σ_r Σ_c (r+c)! / (r!・c!)
= Σ_r 1/(r!)・(Σ_c ((r+c)!/c!))      (1/(r!) を外側に移動した)
= ...?

内側のシグマをなんとかして高速に計算できたら間に合いますが、E問題で時間を溶かしたせいで考察する余裕がありません。無念。

ところで、Wolfram Alpha という便利なウェブサイトがあります。問題の数式を入力してボタンを押します。

sum (i + j)! / j! (j=c..d) - Wolfram|Alpha

出力:

$\sum_{j=c}^{d} \frac{(i + j)!}{j!}= \frac{\frac{(d + 1) \cdot (d + i + 1)!}{(d + 1)!} - \frac{c \cdot (c + i)!}{c!}}{i + 1}$

解けました!

筆者の提出 (Rust, AC): https://atcoder.jp/contests/abc154/submissions/10010458

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした