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


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

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

- 前回: [競プロ参戦記 #67 All-you-can-eat | ABC 145](https://qiita.com/vain0x/items/e44fc83151dd1411f82f)
- 問題一覧: 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) 時間です。

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

参考: [#組み合わせの計算](https://qiita.com/vain0x/items/87f227f867749600b5ee#%E7%B5%84%E3%81%BF%E5%90%88%E3%82%8F%E3%81%9B%E3%81%AE%E8%A8%88%E7%AE%97)

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