ABC153参加 - jj1gujのブログ

ABC153に参加しました.
久しぶりに5完しました！
やったね!
コンテスト成績はこちら
今回はFortranで3完, Pythonで1完, C++で1完でした.

A問題

FortranでACしました.
$H/A$ して, 小数点以下を切り上げて終わりでした.

B問題

FortranでACしました.
$A_{i}$ の総和が $H$ より大きいかどうか見て終わりでした.

C問題

FortranでACしました.
モンスター全員の体力の総和から, 大きい順に $K$ 匹分のHPを引いて終わりでした.

D問題

Python3でACしました.
モンスター全員の体力を $X$ から $\lfloor X/2 \rfloor$ にする操作を1回としてカウントすることにします.
条件から, 1回の操作でモンスターの数が2倍に増えること, そして最初のモンスターは1匹だけであることから $i$ 回目の操作におけるモンスターの数は $2^{i-1}$ となります.
よってモンスター全員を倒すためには $H$ を2で割ることのできる回数(商が0より大きくなる回数)を $N$ として $\sum ^{N} _{i=1} 2^ {i}$ となることがわかります.
以上から $H$ を2で何回割れるか数えて $\sum ^{N} _ {i=1} 2^ {i}$ を求めれば終わりになります.

E問題

C++でACしました.
サンプルケースから規則性が見られず, あとはなんか $A _ {i}$ が報酬で $B _ {i}$ がコストっぽく見えたので直感的にDPかな?って思ってみてました.
その後, 制約を見ると $HN$ が $10 ^ {7}$ だったのでここでDPだと確信して紙DPをして遷移式を考えました.
$N$ 行 $H$ 列のdpテーブルを考えたときの遷移式は以下の通りです.

$$ dp[i][j]= \begin{cases} \lceil B[i]/j \rceil \hspace{10pt} (i=1)\\ \min (dp[i-1][j],B[i]) \hspace{10pt} (j \leq A[i])\\ \min (dp[i-1][j],dp[i][j-A[i]]+B[i]) \hspace{10pt} (others) \end{cases} $$

久しぶりの水パフォでHighest更新です！！
やったね！！！ 3月末までに緑色がだいぶ射程圏内に入りましたね.
今回のセットは全体を通して統一感と言うかストーリーというかがあってとても楽しかったです.
多分次回は冷えると思いますが極力冷えないようにがんばります.