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
以上