【AtCoder】Beginner Contest 175 ABCD python 解法紹介

# 成績
初めての参加でした。
ABCを正解しましたが、D問題で挫折。
アルゴリズムは正しいようですが、バグが最後まで取れませんでした。
パフォーマンスは904です。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/218309/f8383058-b7d3-41d7-1484-39ccdf9c1362.png)

# 感想
色々解説を見てみましたが、問題をどうシンプルに解釈するのか（インデックスを0からに修正したり、負の座標を絶対値で正の座標に移したり）が大切だと思いました。
また解法も自動化にこだわらず、全列挙するような解き方もありなのだと知ることができました。
そして、次回はD問題解きたいです。

# [A問題](https://atcoder.jp/contests/abc175/tasks/abc175_a)
- 私の回答
Rの連続する回数を数えました

```A.py

input_str = input()
cnt = 0
max_cnt = 0
for tmp in input_str:
    if tmp == "R":
        cnt +=1
        max_cnt = max(cnt, max_cnt)
    else:
        cnt = 0
        
print(max_cnt)

```


- 全列挙
たかだか8通りなので、全列挙した方がデバッグに悩まされずいいですね。
参考：https://qiita.com/DaikiSuyama/items/c4ce6869cb897221bf8b

```A_.py
s=input()
if s=="RRR":
    print(3)
elif s=="RRS" or s=="SRR":
    print(2)
elif s=="SSS":
    print(0)
else:
    print(1)
```


- パターン
Rだけに着目して、連続のパターンごとに当てはまるか判定しているようです。
参考：https://qiita.com/u2dayo/items/ce1b420344e451560b42

``` A__.py
s = input()
ans = 0

for i in range(1, 4):
    p = "R" * i
    if p in s:
        ans = i

print(ans)
```


# [B問題](https://atcoder.jp/contests/abc175/tasks/abc175_b)

ポイントは以下だったと思います。
①複数のループで、内側のループの最小値は外側の現在値+1になるようにすること
②三角形の条件はわからないからググったこと


```B.py
N = int(input())
input_list = list(map(int, input().split()))
pair_list = []
def triangle_check(a,b,c):
    return all([a+b>c, b+c>a, c+a>b, a!=b, b!=c,c!=a])
 
if N < 3:
    print(0)
else:
    for i in range(N):
        for j in range(i+1,N):
            for k in range(j+1,N):
                if triangle_check(input_list[i],input_list[j],input_list[k]):
                    pair_list.append([input_list[i],input_list[j],input_list[k]])
    print(len(pair_list))

```

ちなみに、長さの組み合わせについてユニークな組のみカウントするという、より高度な問題だと勘違いしてしまい、時間をロスしました。
その場合は以下のコードを用いて実装していました。
参考：https://medium.com/@yamasaKit/2-python%E3%81%A7list%E3%81%AE%E4%B8%AD%E3%81%AElist%E3%82%92unique%E3%81%AB%E3%81%99%E3%82%8B%E6%96%B9%E6%B3%95-f38d20e6674f

```del_list_dup.py
duplicated_data = [tuple(d) for d in duplicated_data]
unique_data = set(duplicated_data)
unique_data = [list(d) for d in unique_data]
```

# [C問題](https://atcoder.jp/contests/abc175/tasks/abc175_c)

ポイントは以下だったと思います。

- 初期値Xを絶対値化すること
- 原点方向へ移動したときに、原点へ到達できるかどうかで分岐したこと
 - 原点に到達できない場合はできるだけ近づくように動く
 - 到達できる場合は、到達する直前まで動かして、残り何回移動できるか判別
- 偶数回原点まわりを反復する場合、移動は打ち消されるので元の場所と変わらなくなる。
    - 奇数回の場合は、上記の理由から最後の一回分だけの移動になる 


``` c.py
X, K, D = list(map(int, input().split()))
X = abs(X)
syo, amari = divmod(X, D)
if amari > (D-amari):
    syo = syo +1
if syo >= K:
    print(X - K*D)
else: 
    remain_num = K - syo
    position = abs(X - syo*D)
    if remain_num%2 == 1:
        position = abs(position-D)
    print(position)
```

# [D問題](https://atcoder.jp/contests/abc175/tasks/abc175_d)

（正解できていない回答です。REになるテストケースがあるので、テストケースが公開され次第バグを直します。）
ポイントは以下だったと思います。

- ループ検知
- ループごとに値が上がる場合と、下がる場合で分岐
    - ループごとに下がる場合はループを繰り返すと損なので一回目のループ内で最大値を探す
    - ループごとに上がる場合は最終ループよりも一つ前までのループの得点と、最終ループ一つ前＋最終ループの区間での最大値　を足し合わせる
        - 最終ループ一つ前も最大値探索の区間に入れる理由は、-1 -> -2 -> 100　のような得点でループする場合、最後のループがKの関係で-2終わるとすると、最後のループより一つ前の100で終えていた方がよいというようなことになるからです。
- インプットのインデックスは1から始まるが、プログラムの都合上0から始まるように修正

```d.py
import numpy as np
N,K = list(map(int, input().split()))
input_list = list(map(int, input().split()))
input_list = list(np.array(input_list)-1)
c_list = list(map(int, input().split()))
 
def roop_func(l, i, start, return_list=[]):
    return_list.append(l[i])
    if l[i] == start:
        return return_list 
    return roop_func(l, l[i],start, return_list)
 
total_best = -100000000000000000000
for start in range(N):
    p_list = roop_func(input_list, start, start,[])
    epoc = sum([c_list[i] for i in p_list])
    if epoc <= 0: # 回るごとに下がる場合
        best = c_list[p_list[0]]
        current_score = c_list[p_list[0]]
        for i in range(1, min(K, len(p_list))):
            current_score += c_list[p_list[i]]
            if best < current_score:
                best = current_score
    else: #回るごとに上がる場合
        syo,amari = divmod(K, len(p_list))
        base = (syo-1) * epoc
        tmp = p_list
        p_list.extend(p_list[:amari])
        tmp2 = p_list
        best = c_list[p_list[0]] + base
        current_score = c_list[p_list[0]] + base
        for i in range(1, len(p_list)):
            current_score += c_list[p_list[i]]
            if best < current_score:
                best = current_score
    if best > total_best:
        total_best = best
        
print(total_best)

```