ARC174回答メモ

0.はじめに

　最近レートが急落しているので、ちょっと参加をためらいましたが
まぁ一回逃げると逃げ続けることになるなと思い参戦。
ABともに300点配点と簡単ですんなり解けて久しぶりのARCで2問ACでした。
いったん風呂に入ってからDに取り組みましたが時間切れ。
そのまま続けたら、23:15にはACになったので、まじめにやってれば
行けたな・・・と後悔しました。
レートは+21と大躍進し、901と900台に戻れました。

1.A - A Multiply

　300点問題らしく、そこまでの難易度ではない問題。
場合分けとその後の判断さえ間違えなければ行けそう。
と、取り掛かりましたが、最大区間和と最小区間和の
求め方が分からずググる。
カダンのアルゴリズムとして有名らしく拝借して使いました。
Cが0の時の挙動を適当にしてしまったために、1回目はWAが
出てしまいましたが、すぐに気づき修正してAC。

【考え方】
　(コンテスト時はもう少し分かれてましたが不要部分を削りました)
1.N、C、リストAを入力
2.Cが0より大きい時
　　-1.Aの最大部分配列の総和が0より小さい場合
　　-1.操作は不要なので、Aの総和を出力して終了
　　-2.Aの最大部分配列の総和が0以上の場合
　　-1.最大部分配列をC倍すれば総和が最大になるため
　　 Aの総和に最大部分配列の総和×（C-1）を足した値を出力して終了
3.Cが0以下の時
　　-1.Aの最小部分配列の総和が0より小さい場合
　　-1.マイナスになる最小部分配列を0にすれば総和は大きくなるため
　　 Aの総和から最小部分配列の総和をマイナスした値を出力して終了
　　-2.Aの最小部分配列の総和が0以上の場合
　　-1.操作は不要なので、Aの総和を出力して終了
　
　https://atcoder.jp/contests/arc174/submissions/51408271

2.B - Bought Review

　こちらも場合分け問題。
簡単すぎる気もしましたが素直に実装したらACとなりました。
【考え方】
　　・算出に必要なのは、1245の星の数と45の星のコスト
　　・平均3にするためには、星1の人数に-2、星2の人数に-1
　　星4の人数に1、星5の人数に2をそれぞれ掛けて
　集計した値（以下C）が0になればよい。
・ケースごとにCを求め、0以上なら操作不要
・負の時は星4か星5を手に入れないといけない。
　→Cが偶数の時
　-”星5の価値×(C//2)”と”星4の価値×C”のうち小さい方が答え
→Cが奇数の時
　-”星5の価値×(C//2+1)”と”星4の価値×C”と
　 星5の価値×(C//2)+星4の価値の3つのうち一番小さい数が答え

　https://atcoder.jp/contests/arc174/submissions/51394723

3.C - Catastrophic Roulette

　DPぽい上に確率の問題である苦手意識から完全するーしました・・・。
Dのほうが断然解きやすい気がしました。

4.D - Digit vs Square Root

　ぱっと見、ちょっと途方もない気がしつつ取り掛かりました。
まずは、条件を満たす数にどんなものがあるかをExcelで試算。
1000までだと、1、80、90～109の22個
10000までだと、9800、9900～10099の201個
とまぁここまでみて以下の感じとあたりをつけました。
1
80、90～109
9800、9900～10099
998000、999000～1000999
・・・
と、１０の２N乗付近で対象数がでてくることになります。
あとは、上記対象数のリストを最初に作り
ケース後に、リスト内で何番目にあたるかを算出する形でACとなりました。

　【実装】
　 ～対象リスト作成～
　対象リストL：(対象の開始,対象の終了)　1の場合は(1,1)を
　　　　　　　降順ソートした状態で保持
　1.初期化したLに(1,1)を追加
　2.以下、i=1～10まで回す(以下()内はi=2の例)
　-1.xに10のi×2乗をセット(10000)
　-2.Lに(x-(10のi乗)×2,x-(10のi乗)×2)を追加((9800,9800))
　-3.Lに(x-10のi乗,x+(10のi乗)-1)を追加(9900,10099)
3.Lを降順ソート
4.LLにLの長さをセット(19)
　 ～メイン処理(T回繰り返し)～
1.Nをインプット
2.ansに0をセット
3.以下LL回繰り返し(i＝0～18)
-1.L[i][0]がN以下の時
　-1.L[i][1]がN以下の時(そのリスト行分すべてがカウント対象)
　　→ansにL[i][1]-L[i][0]+1を加算
-2.L[i][1]がNより大きい時(そのリスト行の範囲内にNが存在)
　→ansにN-L[i][0]+1を加算
4.ansを出力して終了

　https://atcoder.jp/contests/arc174/submissions/51399678

以上