AtCoder ABC160

AtCoder ABC160解いた分だけまとめ。
今回はAB2完。Cは全探索でやったら爆死した。
レートは300から先がなかなか上がらなくて停滞中。
精進しよう...新型コロナウィルスで外出自粛だし...

目次

• A問題
• B問題
• C問題

A. Coffee

問題文

問題の通り、3,4番目、5,6番目の文字が一緒ならYes、そうでなければNoを出すだけ。

ACしたコード

#coding:utf-8
s = input()

if s[2] == s[3] and s[4] == s[5]:
    print('Yes')
else:
    print('No')

B. Golden Coins

問題文

超簡単な貪欲法。
最初にひたすら500円玉を使い、なくなったら5円玉を使う。

ACしたコード

#coding:utf-8
x = int(input())
happy = 0

happy = 1000 * (x // 500)
tmp = x % 500
happy += 5 * (tmp // 5)

print(happy)

C. Traveling Salesman around Lake

問題文

場合によっては、湖を反時計回りで移動した方が距離が短く済む場合がある。
a[0]→a[n-1]に移動する時とか。
それを考えないといけないので、湖の座標を直線にして、a[0]を反時計周りで考えた時に、
a[0]+湖の一周 という座標を追加。
各座標間の距離を求めて、最長のところを避けるようにすればOK。
湖の一周から、最長距離の区間を除けば良い。

ぶっちゃけ、距離だけほしいので、通る順番はどうでも良かった。

最初全探索して全移動パターンを出して、距離出して、最短距離...っていう
TLEを叩き出すムーブをやらかして大爆死。

解説AC

#coding:utf-8

k, n = map(int, input().split())
a = list(map(int, input().split()))
dist = []

#逆周りの方が距離が短く済むので、距離を2倍にして考える
#池の一周の長さ+a[0]を座標として追加
a.append(a[0] + k)

#距離が最大になる経路は通らないので除外する
for i in range(n):
    dist.append(a[i+1] - a[i])

#print(a, dist)
#池の一周の長さから、距離が最大になるところを除外したものが最短
print(k - max(dist))

TLEしたコード

#coding:utf-8
import itertools

k, n = map(int, input().split())
a = tuple(map(int, input().split()))
ans = 100000000000000000000

dist = []
pattern = sorted(list(itertools.permutations(a)))
#print(pattern)
#print(len(pattern))

for i in range(len(pattern)):
    tmp = 0
    for j in range(0,n-1):
        # 時計回りと反時計回りで距離を計算して、小さい方を加算しようとした図
        right = abs(pattern[i][j+1] - pattern[i][j])
        left = abs(k - pattern[i][j+1]) + pattern[i][j]
        #print(right, left)
        tmp += min(right, left)
    if tmp < ans:
        ans = tmp

#print(dist)
print(ans)