Atcoder 100問解く【中級者になるために】#1

<script type="text/javascript" async src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.7/MathJax.js?config=TeX-MML-AM_CHTML">
</script>
<script type="text/x-mathjax-config">
 MathJax.Hub.Config({
 tex2jax: {
 inlineMath: [['$', '$'] ],
 displayMath: [ ['$$','$$'], ["\\[","\\]"] ]
 }
 });
</script>

@e869120さんの以下の記事を参考に、アルゴリズムの基礎を学習した際の記録を残す。
全103問解く　

https://qiita.com/e869120/items/f1c6f98364d1443148b3#1-5-%E8%8C%B6%E8%89%B2%E3%82%B3%E3%83%BC%E3%83%80%E3%83%BC%E3%81%A7%E8%A6%81%E6%B1%82%E3%81%95%E3%82%8C%E3%82%8B-4-%E3%81%A4%E3%81%AE%E3%81%93%E3%81%A8

## [AtCoder Beginner Selection](https://atcoder.jp/contests/abs)
### [ABC085C](https://atcoder.jp/contests/abs/tasks/abc085_c)
10000円札$x$枚 , 5000円札$y$枚 , 1000円札$z$枚 とした時
$$x + y + z = N$$
$$ 10000\cdot x + 5000 \cdot y + 1000 \cdot z = Y$$ が成り立つことから,
$$x + y \leq N$$
$$9000x + 4000y = Y - 1000N $$
の条件を導ける。この条件を元に、`itertools` `product`から条件を満たす$x,y$の組み合わせを算出する。
**ポイント:a,b,cを全探索するのではなく、a,bのみ全探索する。**
```py:python
from itertools import product
N,Y = map(int,input().split())

for x, y in product(range(N + 1), repeat=2):
    if x + y <= N:
        if 9000*x + 4000*y == Y-1000*N:
            print(x,y,N-x-y)
            exit()
            
print('-1 -1 -1')
```

### [ABC049C](https://atcoder.jp/contests/abs/tasks/arc065_a)
ゴリ押しで解きました。
dequeに文字列を入れ、一文字ずつ確認しています。
`er`という文字列が`dreamerser`というときに邪魔な存在になってしまう部分を条件分岐で対処してます。
**公式の回答では：逆順に並べ比較してました。**
```py:python
from collections import deque

S = deque(input())
#print(S)
erase = 'rase'
dream = 'ream'
while S:
    s = S.popleft()
    #print(s)
    if s == 'e' and len(erase)<= len(S):
        for i in range(len(erase)):
            p = S.popleft()
            if p != erase[i]:
                print('NO')
                exit()
        if S:
            if S[0] == 'r':
                S.popleft()

    elif s == 'd' and len(dream)<= len(S):
        for j in range(len(dream)):
            q = S.popleft()
            if q != dream[j]:
                print('NO')
                exit()
        if S:
            if S[0] == 'e':
                S.popleft()
        if S:
            if S[0] == 'r':
                S.popleft()
        if S:
            if S[0] == 'a':
                S.appendleft('r')
                S.appendleft('e')
                
    else:
        print('NO')
        exit()
print('YES')
```

### [ABC086C](https://atcoder.jp/contests/abs/tasks/arc089_a)
$x$方向,$y$方向それぞれの正方向への移動$(p_x,p_y)$と負方向への進み$(m_x,m_y)$を考える。
それぞれの移動の回数の和が$(t_i-t_{i-1})$回であれば条件を満たした移動が行える。
```py:python
from itertools import product

def check(dist_X,dist_Y,dist_t):
    px = 0
    py = 0
    
    for px,py in product(range(0,dist_t+1),range(0,dist_t+1)):
        mx = dist_X -px
        my = dist_Y -py
        if px+py-mx-my == dist_t:
            #print(px,py)
            
            return True
            
    return False   
    

N = int(input())

start = [0,0]
t_be = 0
for _ in range(N):
    t,x,y = map(int,input().split())
    goal = [x,y]
    dist_t = t - t_be
    dist_X = goal[0]-start[0] 
    dist_Y =goal[1]-start[1]
    #print(dist_X,dist_Y,dist_t)
    if check(dist_X,dist_Y,dist_t) == False:
        print('No')
        exit()
    
    t_be = t
    start = goal
    
print('Yes')

```

あくまで私が実際に解いたコードです。
公式の回答↓↓↓

https://qiita.com/drken/items/fd4e5e3630d0f5859067#5-%E9%81%8E%E5%8E%BB%E5%95%8F%E7%B2%BE%E9%81%B8-10-%E5%95%8F