いつも頭に問題を

競技プログラミング中心で思ったことを書いてく

AtCoder Regular Contest075(ARC075)

AtCoder Regular Contest 075 - AtCoder Regular Contest 075 | AtCoder
出ました、毎回悔しかったですとか言うてる気がするけど悔しかったです

C.Bugged
n個の整数が入力されるので合計点を求めたいんだけど、合計が10の倍数だと0になっちゃうからうまく選んで最大値を求めてねって感じ
ちょっと迷ったけど冷静に考えたらすぐわかった
合計を求めて合計が10の倍数でなければそのまま出力して終わり
合計が10の倍数の場合はソートをして、小さい物から10の倍数かどうか見ていく
10の倍数でなければ合計からそれを引いたものを出力して終わり
やや遅くなったが何とかAC

D.Widespread
魔物がn体いてそれぞれHPがある
魔法が使える
1体選んでAダメージ、ほかのすべてにBダメージ与える
全部倒すまでの魔法の最小使用回数を答える
愚直にソートして一番大きいものにAダメージを繰り返しシミュレーションしようとした
毎回ソートするのがかなりあほらしいなあと思う
工夫しようと思って全体から引くよりBダメージを毎回保持して最大HPから保持した値を引けば抜けるか決めれるようにした
案の定テストケースが終わる気配がなかった

次にpriority_queueを使えば自動でソートしてくれるじゃんって思って実装した
ここで制約を読み直してどうあがいてもシミュレーションやってると10^9ループが逃れられないのでダメだと気付いた
むろん実装後の話

一旦E問題を覗きに行くことにした
しばらく部屋を闊歩したのち二分探索じゃないかと思ってしばらく考え込んだ後実装を始めた
実装できたと思ったがあちこちでWAが出る
細かいところでミスしてるんだろうなぁと思いつつ、気になったところを修正して試していたらタイムアップ

その後10分もしないうちに大なりイコールに変更、少数を考慮していない部分を修正、long long intに変更してACしてしまった
時間あれば解けたなぁと思うけど、以前の私なら解けなかったので成長はしてると実感できた
Submission #1328812 - AtCoder Regular Contest 075 | AtCoder


E.Meaningful Mean
途中でチラ見して制約がやばそうで逃げた
具体的には整数がn個与えられるのでそれらの組み合わせの平均がk以上となるものがいくつあるか調べる
メモ化再帰とか使ってDFSでも書けばいいやと思ってたけどそんなまさかこの制約で出来るわけがねえって思って逃げた
いい判断だった
解説も聞いてないのでまたリベンジしたい


レート
f:id:ratetion:20170603235634p:plain