成績
初めての参加でした。
ABCを正解しましたが、D問題で挫折。
アルゴリズムは正しいようですが、バグが最後まで取れませんでした。
パフォーマンスは904です。
感想
色々解説を見てみましたが、問題をどうシンプルに解釈するのか（インデックスを0からに修正したり、負の座標を絶対値で正の座標に移したり）が大切だと思いました。
また解法も自動化にこだわらず、全列挙するような解き方もありなのだと知ることができました。
そして、次回はD問題解きたいです。
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問題
ポイントは以下だったと思います。
①複数のループで、内側のループの最小値は外側の現在値+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問題
ポイントは以下だったと思います。
- 初期値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問題
（正解できていない回答です。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)