# 5/10 競プロ講習会Cクラスバチャ解説

## ARC025-B チョコレート

### 問題概要

- $H \times W$マスのチョコレートがある
- 市松模様に白黒に塗られている
- 各マスには数字が書かれている
- 白のマスの数字の合計と、黒のマスの数字の合計が等しくなるように長方形を切り出すとき、マス目の個数の最大値は？
- $H,W \le 100$

### 所感
- 二次元累積和の練習問題 (逆に言えば知らないと無理かも)
- $A=B$ を $A-B=0$ として扱う典型テクも含まれている
- 下手したらABC-Cくらいでも普通に出てきそう
- ぜひ通しておきましょう！！

### 解説

- まず、問題の条件を簡単にしたい
→ 白と黒の合計値が同じを、簡単に言い換えられないか？
→ 黒の箇所に -1 を掛けてみる
→ すると「長方形領域の総和が0」であることが、白黒の合計が等しいことと同値になる

- あとは、「総和が0」の長方形領域のうち最大サイズのものを求める問題になる

- まず基本の全探索を考えてみよう
→ 探索すべき長方形の個数は左上と右下の箇所の組み合わせなので O($H^2 W^2$)
→ 長方形のサイズは O($HW$)
→ 合わせると O($H^3 W^3$) で、ざっくり $10^{12}$回くらい → 厳しそう(実際は $3 \times 10^{10}$回くらい)

- たくさんの長方形領域の和を高速に計算する方法がある！！
→ 二次元累積和
→ 具体的には前準備 $O(HW)$, クエリ $O(1)$
→ これを使うと、長方形内の和を計算するフェーズが高速化されて $O(H^2W^2)$になる

- 二次元累積和に関して
→ 検索するといっぱいあるので、調べてほしい
→ まず、 1-indexed で2次元配列に格納する
\
例:
0000
0132
0101
\
→ 縦に累積和する
0000
0132
0233
\
→ 横に累積和する
0000
0146
0258
→ここまでで前準備完了！！
\
右下4マスの総和を知りたいときは・・・
0 **0** 0 **0**
0 1 4 6
0 **2** 5 **8**
\
に注目して・・・
$右下-右上-左下+左上=8-0-2+0=6$ と計算すればOK

- 二次元累積和アルゴリズムの理解に関して
1. 前処理後の各マスが、どの値の和になっているかを考えると理解できそう
2. クエリの処理に関しては、包除原理に基づいている点を意識

---

## ABC001-C　Shorten Diameter

### 問題概要
- $N(\le 2000)$ 頂点の木がある
- 葉を削除していく
- 直径を $K$ 以下にするために必要な削除数の最小は？

### 所感
- 600点にしてはかなり簡単
- ABC-Dで出ても不思議ではない？
- やることさえ分かればDFS,BFSの練習問題
- 木の直径に関する知識・素養は必要かも
- ぜひ通しておきたい！！

### 木の直径に関して

- 木の直径の求め方 (今回の本質ではない)
1. なんでも良いので点$a$を持ってくる
2. 点$a$からDFSを行い、一番遠い点 $b$ を見つける
3. $b$ からDFSを行い、一番遠い点 $c$ を見つける
- 証明はネットを見てください…

- 直径は複数存在しうるが、直径の中心は1つしか存在しない(今回重要な定理)
- 証明: 直径中心が2つある場合、直径が伸びてしまう

### 解説

- 直径の中心を全探索することを考える
- 中心を決め打つと、そこからの距離が $K/2$ より大きい頂点を全部捨てればOK！
- 全ての辺の長さが1なので、直径の中心は以下の2種類しかありえない
1. 頂点
2. 辺の中間点
- よって、探索すべき中心の個数は $N+(N-1)$個
- 各探索は $O(N)$ なので、全体で $O(N^2)$

### 実装に関して
- 辺の中間点を中心にするとき、DFSが書きづらい・・・
- 辺の中間点にも頂点を足してあげると実装しやすいかも
- 個数を数えるとき、中間点を数えないよう注意！！
- 辺の長さが全部 0.5 になることに注意！！

---

## Mujin Programming Challenge 2017-B Row to Column

### 問題概要

- $N \times N (\le 500)$ のマス目
- 各マスは白黒どちらかに塗られている
- 以下の操作を繰り返して、全部黒にできるか？ 可能なら最小回数は？
- 好きな行をコピーして、好きな列にペーストする

### 所感

- まず、配点に面食らうこと間違いなし
- 出題された場合、問題を読むことすらなく終わってしまう人が多数なのでは？
- 高配点なのに、特殊な知識などは一切要求されない
- じゃあAGC特有の超天才ひらめき問題！　と見せかけて、理詰めで解ける
- 配点に惑わされるな！！

### 解説

- まず、全部白の場合当然不可能

- 一方で、黒があると必ず可能
- 手を動かしてみると、絶対可能そうだな、という気分になる

- 回数を求めるに際して、最後の操作を考えてみよう
- 最後の操作の直前、コピー元の行は当然全部黒
- すなわち、全部黒の行を1つ作るのは必須

- もう少し考えると、黒の行は早めに作る必要があることがわかる
- 全黒の行以外をペーストした列は、後に全黒をペーストする必要がある
- 全黒行を作る → 全黒ではない全ての列にペースト が必要な流れであることがわかる

- ここまでを踏まえた素朴な解答方針案
1. 全黒の行を1つ、最速で作成 (このときに全黒列の個数が変わると面倒だが…？)
2. 全黒ではない列全てにペーストする

- 上の解答方針に関する考察
- 1. において全黒列の数は減らない(既に全黒列の箇所を上書きするメリットがないため)
- 1. において全黒列の数は増えない(コピー元が全黒なわけがないので)
- つまり、全黒行を最速で1つ作成する際に、全黒列の個数は変わらない
- 以上のことから、2. の手数は最初の状態における、全黒ではない列の個数に等しい

- あとは、全黒行の最速作成方法を見つければOK!!
- 全探索を考える。 ( $i$行目は最短何手で全黒に？ )
- $(j,i)$ が黒のとき、$j$ 行目をコピーして貼り付けまくればいい
- そうでないとき、$i$列目に黒を持ってくるために追加で1手必要

---

## 第一回日本最強プログラマー学生選手権決勝-A　Equal Weight

### 問題概要

- $N (\le 2 \times 10^5)$ 個のシャリと、$M (\le 2 \times 10^5)$ 個のネタがある。同じ重さのスシを2個作ってください。
- シャリ、ネタの重さは $10^6$ 以下(重要)
- 同じ重さのシャリ・ネタは存在しない (優しい制約)

### 所感

- 300点とは思えない難問
- 多くのredcoderが本番落としていることからも、気が付かないと永久に解けないタイプの問題
- 点数に騙されるな！！ & 制約はちゃんと読もう！！
- かなり教育的な問題ではあると思う

### 解説
- 作れるスシの重さは $2 \times 10^6$ 通りしか無い
- 適当にスシを作っていると、比較的早く衝突する
- 同じ重さのシャリ・ネタがないため、衝突したならば、2つのスシの材料が異なる
- 終わりです

### 実装方針
- mapやdictに作ったスシの重さをkey、材料valueとして保存していく

---

## AGC009-B　Tournament

### 問題概要
- $N$ 人いて、1 vs 1の対戦をバラバラにする
- 負けた人は即退場
- 優勝者(No.1)以外について、誰に負けて退場したかの情報が与えられる
- トーナメント表の深さとして考えられる最小値は？

### 所感
- ABC-E,Fで出てきても違和感無いと思う
- 私が初めて解いた 700点以上の問題(だったはず)
- 典型よりなので解いておくことをおすすめします！！

### 解説
- 「部分優勝トーナメント表」という概念を導入しよう
- 人$v$に関する部分優勝トーナメント表は、$v$が勝ち抜いていて、なおかつ次の対戦で $v$ は負けなければならないようなトーナメント表

- 各人$v$に関して、その人の部分優勝トーナメント表の深さの最小値 ($dp_v$) を求めていけば良い

- 人$v$が、 $v_1,v_2,...,v_k$ の $k$ 人を倒さなくてはいけないとき…
- 当然、$dp_{v_i}$ が小さい方から貪欲に戦った方が良い

- あとは、木dpで解ける

---

## AGC040-C　Neither AB nor BA

### 問題概要
- `A,B,C` のみからなる長さ$N (\le 10^7)$の文字列のうち、以下の条件を満たす個数は？
- 連続した2文字を消す。ただし、`AB,BA` は禁止
- $N$ は偶数

### 所感
- 難しい！！
- 高度なひらめきが要求される
- ただ、本問題のメインアイデアは他の問題でも見るため、典型でもあると思う
- 解いておくと後々生きるかも？

### 解説
- 問題を簡単にする重要なメインアイデア
- 偶数文字目の `A`と`B` を反転する
- すると、 `AA,BB` が削除禁止になる

- AA,BBが削除禁止のとき、なるべく多く消す最適方針は？
- `AB,BA` > `CA,CB,AC,BC` > `CC` の優先度で消す

- 消すのが不可能な場合を考えてみる
- `A` か `B` が過半数だったら、自明に不可能
- そうでないとき、`A`,`B` のうちで多い方を消す手段があり、実行した際に `A`,`B` 共に過半数にはならない (以下雑な証明)

1. 証明: `A`が`B` 以上の個数のとき、`AB,AC,BA,CA` を消して`A`が過半数になることはない
- ギリギリの場合 = `A`がちょうど半数 を考える
- `A` , `A以外` が1ずつ減るので、操作後も `A` は半数となる
- ギリギリの場合でOKなので十分

2. 証明: `A`が`B` 以上の個数のとき、`AB,BA` を消して`B` が過半数になることはない
- 操作後の `B` の個数は `A` 以下なので自明

3. 証明: `A`が`B` 以上の個数のとき、`AC,CA` を消して`B` が過半数になることはない
- ギリギリの場合 = `B` がちょうど半数 → `A`の個数は`B`以上だから、そもそも `C` が無い
- `B`が半数未満の場合、文字列が2縮んでも過半数にはなりえない

- 証明できたので、あとは数え上げ
- `A` が過半数になる場合 が分かればOK
- `A` の個数を全探索すれば、`A`の位置を決め、あとは残りの位置に `B,C` を好きに入れればいい
- $O(N)$