おはようございます。しほみんです。
火曜日に引き続いてABC174の解説をします。
最新出社していて体力は奪われてつらいですね....出社してもしなくてもやること変わらんのに....
ということでまあ、やっていきます。
D問題
祭壇に、左から1列に石が並べられています。
それぞれ石は赤か白です。
以下の動作が自分はできます。
・白と赤の石の位置を交換できる。
・白か赤の石を選択して、逆の色（白なら赤、赤なら白）の石に置き換える。
赤石の左に白石があると不幸を招きます。そのような白石がなくなるために上記の動作を最低何回行う必要がありますか？
赤石の左に白石がおかれないためには、左から赤石を置き、そのあと白石を置くようにすればよいってことです。あとはそのような動作を行うために、あらかじめ、石を数えておいて、あとは左から赤の石を並べて、白の石を並べればよくなります。
解説だと、その赤と白の区切りの位置をそれぞれ設定して求めているのですが、実は、最初に数えた赤と白の石の数にところに区切りを置けば、解答は通ります（通りました）。
多分理由で考えられるのは、白と赤の個数の増減と、白と赤の位置の入れ替えは等価作業なので、明らかに最初の数より不一致なものの場合、余計に色の個数を変えないとならないので、回数が最小にならないって感じかと思います。
ということで、
1. まず、赤の数（a個）と白の数（b個）を数える。
2. 左からa個赤、b個白を並べると決め打ちする。
3. 左からa個は白の数（x個）、そのあとは赤の数（y個）を数える
4. min(x,y)+abs(x-y)が答え（普通にmax(x,y)だった）
となります。
まあ解説通り、赤と白の区切りの位置はN個考えられるので、それを素直に求める方がよいです（もしかしたらこれしなくても解けたからdiffが低いのかもしれない）。
この場合、石の色と増減を考えるので実装は少しめんどそうです。
E問題
N本の丸太があり、それぞれ長さはA1,A2,A3,...,Anです。
今、K回切れます。1回切ると1つの長さTの丸太を、t, T-tとできます。
このとき、できるだけどの丸太も小さくしたとき、その丸太のうちの最大を求めなさい。
ちょっとわからず椅子を温めていた問題です。
まあ、普通にKは10の9乗までが制限なので、普通に切る方法を考えてもどうあがいてもできません。そこで止まってしまいました。
しかし、逆に考えれば、いいのです。すなわち答えをすでに決まっているとき、この答えにするには丸太は何回切る必要があるか？を考えます。
答は小さくすればするほど、丸太を小さく切らないとならないので、回数は増えます。よって、単調増加で、数が増えていくことが分かります。
単調増加のものを、解答に出す...ということで二分探索の登場です。
ということで、二分探索をしておしまいです。
二分探索で注意することは、
・初期値はmin = 0, max = 1000000000として、maxの方を答えにします。
→maxが1まで答えにするので、minは0にします。
・丸太の切る回数を求めた後、k以下ならmax,kより多ければminにします。
→kより小さければもっと小さくできるのでmaxにして、もっと小さい値を探し、kより大きいと、k回では不可能なのでminにして、もっと大きい値を探します。
あと、丸太をX以下にするなら、(Ai/X)を切り上げた数等分する必要があるので、それを求めれば丸太を切る数を求められます。
ということで、o(NlogA)で求められます。
最後に....
E問題の二分探索はかなり典型的な問題ですね....二分探索便利なのでちゃんと使い方をつかんでいきたいです。なおD問題は運良く解けた気がしないでもないので要復習ですかね....
ではでは。
