- AtCoder Problems * Use Recommendations to solve past problems. Thanks to AtCoder and AtCoder Problems.

*AtCoder Beginner Contest D - Redistribution*
Difficulty: 830

This theme, dynamic programming

It is a problem of so-called typical dynamic programming.

- Previous article --Qiita *, * [AtCoder Beginner Contest E --Crested Ibis vs Monster](https://atcoder.jp/ In contests / abc153 / tasks / abc153_e) *, you have to take care even if you exceed the target value, but this time it's just fine, so it's a little easier. Ruby

`ruby.rb`

```
s = gets.to_i
dp = Array.new(s.next, 0)
dp[0] = 1
s.times do |i|
next if dp[i].zero?
3.upto(s) do |x|
if i + x <= s
dp[i + x] += dp[i]
dp[i + x] %= 1000000007
else
break
end
end
end
puts dp[s]
```

`ruby.rb`

```
if i + x <= s
dp[i + x] += dp[i]
dp[i + x] %= 1000000007
else
break
end
```

This time it's just fine, so add dp only for ʻi + x <= s`. Python

`python.py`

```
from sys import stdin
def main():
input = stdin.readline
s = int(input())
dp = [0] * (s + 1)
dp[0] = 1
for i in range(s):
if dp[i] == 0:
continue
for x in range(3, s + 1):
if i + x <= s:
dp[i + x] += dp[i]
dp[i + x] %= 1000000007
else:
break
print(dp[s])
main()
```

*** PyPy *** is really fast, isn't it?

Ruby | Python | PyPy | |
---|---|---|---|

Code length(Byte) | 244 | 405 | 405 |

Execution time(ms) | 284 | 509 | 70 |

memory(KB) | 14400 | 9060 | 64596 |

- Solved ABC 178 D
- Become familiar with Ruby
- Become familiar with Python

Referenced site

Recommended Posts