今日はこの回をやりました。
A~Dの4完です
A: ソートしてmin(a[2],a[1]+a[0])+max(0,(a[0]+a[1]-a[2])/2)
— やまけー (@yamake_cpp) 2020年10月15日
B: かぶってるPINを1文字変えて他のかぶっていないPINにできないか、全通り試します
C: こういうのは√Nためせばいけます
D: UnionFindをします
Aから少しつまづいてしまいました
A問題は数字が大きい順にとします。
であれば答えは
です。
そうでなければ、と
の差分が1となるように
と
のペアを作ります。
次に残ったと
の小さい方の大きさ分だけペアを作れます。
こうすることによって、最後のと
の差が1の時以外は全て使い切ることができます。
A問題なので場合分けせずに早く通したいと思い、
cout<<min(a[2],a[1]+a[0])+max(0,(a[0]+a[1]-a[2])/2)<<endl;
（配列{a}は昇順ソート、2項目の右側でと
の差分が1の時切り捨てる処理をしています。）
を投げました。
B問題
nが10以下だったので、仮に全部同じPINだったとしても、それぞれ1文字ずつ変えるだけで大丈夫です。
あとはどこを変えるかと、何に変えるかを全探索して良いです。
C問題
こういうのはまで全探索したら大丈夫なんですね～～。という気持ちで
までを全探索したら通りました。
商とあまりの大小関係を考えると証明ができそうな気がしているのですが、まだ詰め切れていません......
D問題
これはaが入っている文字列、bが入っている文字列、...、zが入っている文字列と
それぞれの英小文字ごとにUnionFindをしていくとできて、計算量は（この記法あってますか...？）になります。
