No Caffeine, No Life

プログラミング(主にPython)

ABC 074 C:Sugar Water

問題:

C: Sugar Water - AtCoder Beginner Contest 074 | AtCoder

解説:

  • 時間制限が3秒
  • 全体的に数値が小さい

のを理由に、全探索することを考えた。つまり、操作1, 2, 3 ,4の回数をa, b, c, dとしたとき、

  • {\displaystyle 100A * a + 100B * b + C * c + D * d \leq F}
  • {\displaystyle C * c + D * d \leq E}

を満たすようなa, b, c, d を探し、該当する組に対し、濃度を計算し、保存(解答例中のmemo)。a,b,c,dは、与えられた不等式より、せいぜい

  • {\displaystyle 0 \leq a, b \leq 30}
  • {\displaystyle 0 \leq c, d \leq 100}

であることがわかる。(したがって、全探索する場合は31 x 31 x 101 x 101 ~ 1,000,000...基本的には大丈夫なはず、と検討がつく)

考え方はこれでよかったのだけれど、本番中は致命的な勘違いをしていてダメだった…のが痛い。速く正確に、というのはとても大事な要素だと思うけれど、これは練習でもちゃんと鍛えていかないといけないな、とは思う。

解答例: