おはようございます。しほみんです。
引き続きABC173をやっていきます。E問題も普通にバグりそうですがなんとか通したので両方解説していきます（ちょっと変な裏技の話もします）。
問題解けるとやっぱうれしいですね。
D問題ほぼ考察がメインで分かってしまえばかなり楽です。
E問題は正負の特徴を本当にちゃんとつかまないと実装がめっちゃ大変になるやつです。
D問題
N人の人がいてそれぞれフレンドリーさがAi(i = 1- N)となります。
あるチャットの輪があってそこに、N人入っていきます。
そのある人が入るとき、輪のどこにでも入ってよいです。入ったとき、右隣と左隣のうち小さい方のフレンドリーさだけ加わります。これを心地よさとします。
最初に入る人は心地よさは0です。
このとき、全員入ったとき、心地よさの最大はいくつでしょうか？
こればっかりは慣れなんでしょうが、考えることは以下の二つです。
・どういう順に入れていくべきか？
・入っていったときにどこに配置すべきか？
まず、心地よさを最大にするってことはすでに輪の中に入っている人の数は大きい方が望ましいです。
よって、なんとなく大きい順に入れていくことが重要そうです。もし途中に小さいものを入れてしまうと、その小さいものの隣に入れないとならないケースが生じて
→こういうふうにあたりはつける。
あとは、入れたときの位置です。その中で最大になるところに入れればいいことになります。これについては具体的に考えてみるとよいです。
できればテストケース以外が望ましいです。テストケースだと考え方次第では一致してしまうことが多々あります。（これがテストケースだけしか通らずACできない理由の一つです。）
例えば、1,2,3,4,5,6のフレンドリーさを入れてみます。
・1番目に入る人は2番目にできるだけ心地よさを大きく獲得したいので6を入れます。
・2番目に入るのは5です。このとき心地よさは6獲得できます。
・3番目に入る人は必然と5が隣になるので、心地よさは5足して11です。入るのは4です。
・4番目に入る人は6-4-5と円環になりますが、6－5の間が最大なので、その間に3を入れます。心地よさは5足して、16です。
・5,6番目に入る人は6-4-5-3となるので、4を両隣に入れてしまえば、実は心地よさは最大です。よって、心地よさは16+4+4=24となります。
よって、これが最大になります。
最初1回しか反映しないから小さい数がいいのかと思いますが、小さい数にひきづられるので一番大きい数は1回しか使えないです。（もしほかの数が隣にあれば、その小さい数になるので、絶対最初です）
ここから、最初の1つ目は1回だけカウント、それ以外は大きい順に両端の2つが使えるってことが分かります。よって、ソートして、大きい順に、一番大きいのは1回、それ以外は2回ずつカウントしてN-1回分行えばよいです。
実はテストケースだけだと、一番小さいもの以外を足し合わせるってことでも成立しますが、上記のようにもっと大きい数を活用できる以上、この考えは間違いになります。
（テストケース1) 3+2+2 = 7で、上と結果的に一致する。
（テストケース2)1しかないので、1+1+1+1+1=5で上の結果と一致する。
D問題までくるとこういう罠があるので注意深く観測したほうが無難です。
E問題
N個の数があります。このうちK個選びます。この席の最大はいくつでしょうか？
10の9乗+7で割ったあまりを求めなさい。
N個の数は-10の9乗から10の9乗の間です。
マイナスが入っていますね...マイナスが入ると物事が一気に厄介になります。
最初は普通に正、0、負の数を数えてそこから場合分けしましたが何かしら破綻したので、もっと単純に考えることにしました。大枠のケースを考えて、例外を部分的に処理していく方法です。
（大枠のケース）
マイナスを無視できれば、基本的に頭から絶対値の大きい数をK個採用すればよいです。これがプラスならもう答は確定です。
（例外ケース）
・答えが確実にマイナスになるケース
・N=Kのとき
・絶対値を大きい順に選んだ時マイナスになっちゃうケース
上記のようにして、例外ケースを丁寧に追います。
・答えが確実にマイナスになるケース
これはKが奇数かつ、全部マイナスになる場合です。このときは絶対値が小さい順にK個選べばよいです。
・N=Kのとき
黙って全部選べばよいです。
・絶対値を大きい順に選んだ時マイナスになっちゃうケース
これが一番厄介です。まず、マイナスの数の判定はC#では自前で絶対値と負かそうでないかで2変数格納すればよいです。
そして、マイナスの数を判定します。
このとき、マイナスの数が奇数になります。
となると行うべきことは以下の2つのどちらかです。
・選ばれている絶対値が最小の負の数を省いて、選ばれていないうちで最大の正または0の数を選ぶ（省く数をA1,選ぶ数をB1とする）。
・選ばれている最小の正または0の数を省いて、選ばれていないうちで絶対値が最大の負の数を選ぶ（省く数をB2,選ぶ数をA2とする）。
で、上記の頭からとったものの積をPとすると、
|P/A1*B1|, |P/B2*A2|です。このとき、大きい方を選べばよいです。
|P/A1*B1|> |P/B2*A2|のとき、すなわち、B1*B2 > A1*A2のとき、前者になります。
|P/A1*B1|< |P/B2*A2|のとき、すなわち、B1*B2 < A1*A2のとき、後者になります。
この選択さえできれば、最大のときの正の数と負の数が決まるので、あとは、ソートして数を踏まえて、かけていけばよいです。
ちなみに、ソートした場合、両方存在すれば、A1とA2、B1とB2は必ず隣合います。
存在しないケースもあるのでその時に注意して丁寧に処理します
まとめると、
1. まずは数列を読み込む。
2. 普通にソートした数列aと、絶対値を正負情報残してソートしたものnumを用意する。
3. 例外処理を先に行う。n=kのときはaの全部の要素をかけて出力。
全部負かつkが奇数のときは数列aの絶対値の小さい順k個取り出す。
4. numで頭からK個取り出して、マイナスの数を数える。マイナスの数が偶数ならそのまま答えを出力。
5. マイナスの数が奇数のときは、上記の2条件のどっちにすべきか考える。A1,A2,B1,B2が存在するかを確認して、存在しないケースとするケースで分岐して処理する。あとはプラスの数とマイナスの数は決まるので、それに応じて答え出力。
となります。
なぜか書いたら2つケースが通らなくて困りましたが、以下のことをして解決しました。
・分岐条件で等号を追加した
・配列にダミーを追加した
上記はとっさにどーしても解けないときに有効な手段です。試す価値はあります。ただ、たまたま通っただけでなんかよくないもの含んでいる気がしたのであんまり、仕事上では使わない方がよいでしょう。
最後に....
E問題みたいなのが、しっかり設計したうえでコード書ければもうプログラマーとしては十分な気がします。数学的なことより、実装力の大切さもあったと思います。
ではでは。
