AtCoder Problems Training Easy(41~50)

#目次

[1~10](https://qiita.com/tnodino/private/fe81289a78c79c53e41e)
[11~20](https://qiita.com/tnodino/private/a2f1118ad8276de714e2)
[21~30](https://qiita.com/tnodino/private/bdce8619699fc9cb3110)
[31~40](https://qiita.com/tnodino/private/426ea11e1509bbe282d8)
41~50 ← 今ココ
[51~60](https://qiita.com/tnodino/private/62637218c5884b2af10d)
[61~70](https://qiita.com/tnodino/private/0997709fa992e538ed36)
[71~80](https://qiita.com/tnodino/private/1249d60df34c0fda8e6e)
[81~90](https://qiita.com/tnodino/private/83c4a61a0361b8995983)
[91~100](https://qiita.com/tnodino/private/88bacef44c037dc9fc89)

#41. [ABC152 C - Low Elements](https://atcoder.jp/contests/abc152/tasks/abc152_c)

**Difficulty:158**

条件をまとめると、前から単調減少になる数値だけ抜き出したときの個数が答えになる。
単調減少とは$\ P_1>P_2>\dots\ $のことであり、 例4 から抜き出した数値は$\ 5>4>2>1\ $ の 4 つになる。 

```Python
n = int(input())
p = list(map(int,input().split()))
ans = n
m = 2 * (10 ** 5)
for i in range(n):
    m = min(p[i],m)
    if p[i] > m:
        ans -= 1
print(ans)
```

#42. [ABC118 B - Foods Loved by Everyone](https://atcoder.jp/contests/abc118/tasks/abc118_b)

**Difficulty:124**

$\ M_i\ $番目の食べ物は、$\ K_j\ $が好きと答えなかった場合は候補から消しておく。
最終的に候補に残った数を答える。

```Python
n,m = map(int,input().split())
ans = ['Yes'] * m
for i in range(n):
    k = list(map(int,input().split()))
    k.pop(0)
    for i in range(m):
        if not i + 1 in k:
            ans[i] = 'No'
print(ans.count('Yes'))
```

#43. [ABC044 B - 美しい文字列](https://atcoder.jp/contests/abc044/tasks/abc044_b)

**Difficulty:119**

文字列$\ W\ $の重複をなくして、リスト$\ L\ $とする。
その後、$\ L_i\ $が$\ W\ $に偶数回出現するか判定する。

```Python
w = input()
x = list(set(w))
for i in range(len(x)):
    if w.count(x[i]) % 2 != 0:
        print('No')
        exit(0)
print('Yes')
```

#44. [ABC124 C - Coloring Colorfully](https://atcoder.jp/contests/abc124/tasks/abc124_c)

**Difficulty:128**

前から順番に交互になるように色を塗り替えていき、塗り替えた回数を数えておく。
ただし、$\ len(S)/2\ $回をを超える塗り替えは非効率なので、 先ほどと反対の色で塗り替えた回数を数える必要がある。
これは、$\ len(S)\ $から塗り替えた回数を引けば求まる。
例えば$\ 00101010\ $を塗り替える場合、前から順に判断すると$\ 01010101\ $で 7 回になるが、反対の色で塗り替えると$\ 10101010\ $になり、 1 回で済む。

```Python
s = list(input())
n = s[0]
ans = 0
for i in range(1,len(s)):
    if s[i] == n:
        ans += 1
        if s[i] == '0':
            s[i] = '1'
            n = '1'
        else:
            s[i] = '0'
            n = '0'
    else:
        n = s[i]
print(min(len(s) - ans,ans))
```

#45. [ABC090 B - Palindromic Numbers](https://atcoder.jp/contests/abc090/tasks/abc090_b)

**Difficulty:126**

$\ A \le i \le B\ $の間で、実際に$\ i\ $が回文かどうか調べる。

```Python
a,b = map(int,input().split())
ans = 0
for i in range(a,b+1):
    i = str(i)
    n = i[:2]
    m = i[:2:-1]
    if n == m:
        ans += 1
print(ans)
```

#46. [AGC024 A - Fairness](https://atcoder.jp/contests/agc024/tasks/agc024_a)

**Difficulty:162**

何度操作を行っても高橋君と中橋君の差の絶対値は変わらない。
そして、$\ 1 \le A,B,C \le 10^9\ $なので差の絶対値が$\ 10^{18}\ $以上になることもない。
$\ K\ $の回数が偶数なら$\ a-b\ $、奇数なら$\ b-a\ $を出力すればいい。
例えば$\ 1,4,5\ $の場合、$\ 1\ $回目の操作で$\ 9,6,5\ $、$\ 2\ $回目の操作で$\ 11,14,15\ $、$\ 3\ $回目の操作で$\ 29,26,25\ $となり、法則が合っていることが分かる。

```Python
a,b,c,k = map(int,input().split())
if k % 2 == 0:
    print(a-b)
else:
    print(b-a)
```

#47. [ABC079 B - Lucas Number](https://atcoder.jp/contests/abc079/tasks/abc079_b)

**Difficulty:127**

$\ L_{i-1}\ $を$\ A\ $、$\ L_{i-2}\ $を$\ B\ $とする。
最初、$\ A\ $は$\ 2\ $、$\ B\ $は$\ 1\ $である。
$\ A+B=C\ $とし、$\ A=B\ $、$\ B=C\ $と値を更新していくことで、$\ N\ $番目のリュカ数を求められる。
ただし、$\ N=1\ $の時に$\ 1\ $を出力するようにしておく必要がある。

```Python
n = int(input())
a = 2
b = 1
if n == 1:
    print(1)
else:
    for i in range(2,n+1):
        ans = a + b
        a = b
        b = ans
    print(ans)
```

#48. [ABC139 C - Lower](https://atcoder.jp/contests/abc139/tasks/abc139_c)

**Difficulty:129**

前から順番に$\ H_i \ge H_{i+1}\ $かどうかを調べる。
もし$\ H_i < H_{i+1}\ $なら、今までに移動した回数を最大回数と比較する。
例3 のように移動回数を数えるので、最初に降り立ったマスは含めず、 0 回の移動もあり得る点に注意する。

```Python
n = int(input())
h = list(map(int,input().split()))
m = 0
ans = 0
for i in range(n - 1):
    if h[i] >= h[i + 1]:
        m += 1
    else:
        ans = max(ans,m)
        m = 0
print(max(ans,m))
```

#49. [ABC062 B - Picture Frame](https://atcoder.jp/contests/abc062/tasks/abc062_b)

**Difficulty:135**

囲んで出力するだけとなる。
最初と最後に$\ W+2\ $ の長さの # を出力し、途中の画素$\ a\ $は行ごとに前と後ろに # を足すだけで実現できる。

```Python
h,w = map(int,input().split())
a = list(input() for i in range(h))
print('#' * (w + 2))
for i in range(h):
    print('#' + a[i] +'#')
print('#' * (w + 2))
```

#50. [ABC059 B - Comparison](https://atcoder.jp/contests/abc059/tasks/abc059_b)

**Difficulty:135**

そのまま$\ A\ $と$\ B\ $の大きさを比較する。
制約が$\ 1 \le A,B \le 10^{100}\ $となっているが、そのまま比較しても特に問題はない。

```Python
a = int(input())
b = int(input())
if a > b:
    print('GREATER')
elif a < b:
    print('LESS')
else:
    print('EQUAL')
```