競プロ参戦記 #68 Max-Min Sums | ABC 151

AtCoder Beginner Contest 151 に参加したので、着手した問題の考察を書いていきます。結果はE完でした。

少し間が空きましたが、今年もよろしくお願いします。

• 前回: 競プロ参戦記 #67 All-you-can-eat | ABC 145
• 問題一覧: https://atcoder.jp/contests/abc151/tasks

A - Next Alphabet

問題概要: 'z' でない英小文字 c が与えられる。アルファベット順で次の英小文字を求めよ。

A: 考察

複数の方法があります。

1. a～y までの25通りの場合分けを行う。
2. 文字の配列 "abc...xyz" から文字 c の位置 i を探し、(i+1) 番目の文字を出力する。
3. c+1 を文字として出力する。

3番目は 'a' as u8 や 97 as char のように文字と数値の相互変換をやってみると分かります。英小文字の文字コードは連続しているので、実は 1 を足すだけで解けます。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc151/submissions/9448841

B - Achieve the Goal

問題概要: 整数 K が与えられる。N 個のテストがあり、そのうち N-1 個のテストの結果 A(i) が与えられる。テストの結果は 0 点以上 K 点以下である。平均点を M 点以上にしたい。最後のテストの後に平均点が M 以上になる可能性があるか判定せよ。可能性があるなら、平均点が M 以上になるような最後のテストの点数の最小値を求めよ。

B: 考察

最後のテストの点数を X とおくとき、平均点が M 以上になることは以下の条件で表せます。

    (A(1) + A(2) + ... + A(N-1) + X) / N ≥ M

X について変形すると:

    X ≥ M * N - (A(1) + A(2) + ... + A(N-1))

X が右辺に等しいとき、平均点がちょうど M になるので、右辺が答えになりそうです……が、右辺がテストの点数としてありえる値 (0 以上 K 以下) にならないケースに注意しましょう。

右辺が K より大きいとき、K 点を超える点数を取らないと平均点を M にできない、つまり不可能です。

右辺が 0 より小さいとき、X=0 でも条件が成り立ちます。0点をとっても平均点が M 以上になるわけです。このケースの答えは 0 です。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc151/submissions/9446955

C - Welcome to AtCoder

問題概要: N 個の問題と、M 個の提出が与えられる。i 番目の提出は p(i) 番目の問題への提出であり、結果は S(i) (AC または WA) である。AC を1回以上出した問題の数を正答数という。AC を1回以上出した問題において、初めて AC を出すまでに出した WA の数の総和をペナルティ数という。正当数とペナルティ数を求めよ。

C: 考察

名のあるアルゴリズムは特に知らなくてもよく、書かれている条件を満たすようにデータを持ちながら、ループを回せばいいです。これが難しい。

各問題に対して「AC したかどうか」「AC するまでのペナルティの個数」をそれぞれ配列に持つと解けます。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc151/submissions/9448397

D - Maze Master

問題概要: H列W行のグリッドが与えられる。各マスは道 (.) または壁 (#) であり、すべての道は連結である。高橋はグリッド上の相異なる2点をスタート・ゴールと定めて迷路を青木に渡し、青木はスタートからゴールへと最小の移動回数で移動する、というゲームをする。高橋が適切にスタート・ゴールを定めるとき、青木の移動回数の最大値を求めよ。

制約: H, W≤20

D: 考察

問題文が難しいです。数学っぽく言い換えると以下のようにシンプルになります。

• グリッド上の相異なる2つの道の組み合わせ S, T を考える。
• S から T への移動回数の最小値を M とする。
• M の最大値を求めよ。

仮にスタート・ゴールの適切な定め方が分かったとすると、M を求めるのはよくある問題で、幅優先探索をすればよいです。

制約から (HW)^2 ≤ 1.6×10^5 なので、実際にすべての S, T のペア (400通り) を列挙して、それぞれ BFS する (400ステップ) ような実装で間に合います。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc151/submissions/9460424

E - Max-Min Sums

問題概要: 整数からなる空でない集合 X に対して、f(X) = max(X) - min(X) とおく。長さ N の整数列 A と、1以上の整数 K が与えられる。A から K 個の要素を重複なく選び、選ばれた要素の集合を S とするとき、このような選び方は C(N, K) 通りある。そのようなすべての S について、f(S) の総和を求めよ。(mod 1000000007)

E: 考察

具体的に N=5, K=3, A=(1, 1, 2, 3, 5) で S を列挙してみると、以下の通りです。各行の左端が min, 右端が max になります。

1 1 2 3 5
---------
1 1 2
1 1   3
1 1     5
1   2 3
1   2   5
1     3 5
  1 2 3
  1 2   5
  1   3 5
    2 3 5

• max(X) に選ばれるのは 5 が6回、3が3回、2が1回。
• min(X) に選ばれるのは 1 (1個目) が6回、1 (2個目) が3回、2が1回。

A(5) = 5 が max(X) に選ばれる条件を考えると、残りの K-1 = 2 個がすべて左側にある N-2 = 3 個の要素から選ばれることです。そのため max(X) = 5 は C(3, 2) = 6 回出現することが分かり、上の例と符合します。

一般的に各 A(i) は max(X) に C(i, K-1) 回選ばれます (ただし i ≥ K-1)。同様に、A(i) は min(X) に C(N-i-1, K-1) 回選ばれます。

そのため、総和の式において A(i) の項全体の部分和は (C(i, K-1) - C(N-i-1, K-1)) * A(i) になります。

これを各 i について計算して足すと答えが求まります。全体としては O(N) 時間です。

なお、組み合わせの計算は逆元漸化式を使うと楽です。

参考: #組み合わせの計算

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc151/submissions/9465300