【競プロ精進日記】AtCoder ABC159

2020.03.23
競プロ

1. はじめに
2. A
3. B
4. C
5. D
6. E
7. F

はじめに

当ブログは問題の解説がメインではなく、筆者の解法やアイデアの保存がメインです。
したがって、読者の期待に沿えないことがあると思いますがご了承ください。

A

A – The Number of Even Pairs
今回の問題セットはC＜A＜Bって感じでした。
A問題開いたときに組み合わせと偶奇が出てきてこれ本当にA問か？と疑いました。
組み合わせのライブラリを用意してなかったので少し焦りましたが、2つを選ぶ組み合わせなので$\frac{n(n-1)}{2}$を計算すればよいです。
偶数と奇数で和が和が偶数になるのは偶＋偶のときと奇＋奇のときだけなので、下記を計算すればよいです。
$$ \frac{N(N-1)}{2} + \frac{M(M-1)}{2} $$
https://atcoder.jp/contests/abc159/submissions/11083947

B

B – String Palindrome
面倒ですね。
回文判定はreverseして同じかどうかで判定。
string.substrの仕様を忘れて調べたせいで遅くなりました。
適切に3回部分文字列に切り出してそれぞれ回文判定すればよいです。
https://atcoder.jp/contests/abc159/submissions/11090249

C

C – Maximum Volume
等分した時が最大になるはずなのでそのままAC。
数弱ですが適当に証明します。
縦、横、高さのうちの２つを$a,b$とすると、体積は$ab(L-a-b)$となりこれを最大化します。
$a,b$それぞれで偏微分すると,
$$bL-2ab-b^2=0$$
$$aL-a^2-2ab=0$$
となるので下式より$b=\frac{L-a}{2}$を上式に代入して
$$ 3a^2-4aL+L^2=0 $$
これを満たす$a$は曲線の頂点なので$a$で微分すると、
$$ 6a-4L+2L=0 $$
よって、$a=\frac{L}{3}$、同様に$b=\frac{L}{3}$、残りの変数$L-a-b=\frac{L}{3}$より、$L$を等分したときが体積が最大になることが証明できました。
https://atcoder.jp/contests/abc159/submissions/11091713

D

D – Banned K
ぱっと見難しそうです。
$k$番目を除いた都度に組み合わせを数えていては$O(N^2)$で間に合わないので、$N$個の組み合わせを計算して1つを取り除いた差分を考えればよいです。
まず、数$A_i$の出現回数を$C_{A_i}$とします。
何も除いていない$N$個の組み合わせは$\sum \frac{C_i(C_i – 1)}{2}$となります。
そして、$A_i$一つを取り除いたときを考えると、すでに足されている$\frac{C_{A_i}(C_{A_i} – 1)}{2}$を引いて$\frac{(C_{A_i}-1)(C_{A_i} – 2)}{2}$を足せばよいです。
これをすべての$A_i$で計算し出力すると$O(N)$で解決できました。
https://atcoder.jp/contests/abc159/submissions/11099943

E

E – Dividing Chocolate
終了40分前に解法がわかり取り組むも実装難で間に合いませんでした…
順位表の人数を見て300人くらいだと、どう考えても今の自分には解けないだろうと諦めてしまうのでダメですね。
終了時には1000人以上解かれていることが分かって、実装が難しいだけだなぁと思います。
改めてコーディングしなおすとそこまで実装難ではないような気もします。
普段から時間計って問題解いたり、バチャしないのでそれが結果に出たんだと思います。

ここから解説

分割する順番は全く関係ないので一瞬dpかと思いましたが、直線iを分割した時の情報の持ち方が思いつかなかったので違うんだと思い諦めましたが、
$H\leq 10$なので縦の分割は$2^9-1$通りすべて試すことができます。
縦の分割さえ確定すれば、横の分割は貪欲に決めることができます。
ホワイトチョコの個数がギリギリKマス以下になるように分割すればよいですね（まだ余分にチョコを詰めれるのに分割する必要がないですからね）。
問題はここからで、どのように実装するかです。
改めて解くと、縦に分割した線を越えたらカウントする配列の添え字を進めるという感じで書くと簡単に書けました。
縦に分割した線を越えない間、同じ配列の要素（分割された区画）にカウントしていくことになります。
区画ごとにカウントしますが、ひとつでもKを越えたら分割しなければなりません。
さらに、縦の分割を決めた後に、どのように横の分割をしてもKマス以下にならないことがあるので、その場合は縦の分割が誤っており、条件を満たしません。
以上のことを丁寧にコードに載せたらACしました。
よかったら提出コードを見てみてください。
それにしてもこの問題を数分とかでACする人どういう頭になってるんでしょう。
考察が早いのは頭がいいのだろうとわかりますが、考えをコードに早く載せるは一生できる気がしません。
https://atcoder.jp/contests/abc159/submissions/11159665