競プロ初心者の復習用記事です。
ここで書く解は解説や他の人の提出を見ながら書いたものです。自分が実際に提出したものとは限りません。
A - Coffee
与えられた文字列の3文字目と4文字目が同じ、5文字目と6文字目が同じであるかを判定する問題です。
そのまま実装したのが以下のコードです。これでOK。
s = input()
if s[2] == s[3] and s[4] == s[5]:
print('Yes')
else: print('No')
B - Golden Coins
与えられた金額nを両替して、500円玉一枚につき1000, 5円玉一枚について5と換算すると最大値はいくつでしょう？という問題です。
500円玉の枚数はn//500、5円玉の枚数はn%500//5で求まります。
以下のように実装しました。
n = int(input())
print(n//500*1000 + n%500//5*5)
C - Traveling Salesman around Lake
湖の周りに存在する家の位置を与えられて、最短経路で全ての家を回る距離を考える問題です。
湖の北端の位置を0として、そこから時計回りに二周分、家の位置を配列に格納しました。1周目のどれかの家をスタート地点にして、全ての家を回るまでの距離を計算して最大値を求めました。
K, N = map(int, input().split())
A = list(map(int, input().split()))
A += [a+K for a in A]
minD = 1e6
for n in range(N):
minD = min(minD, A[n+N-1] - A[n])
print(minD)
解説では書き方が異なりました。湖は一部を除いてほとんど一周します。通らない一部とは、最も距離の遠い家の間です。
ちょっと書き換えました。このほうがきれいですね。
K, N = map(int, input().split())
A = list(map(int, input().split()))
A.append(A[0]+K)
maxD = 0
for n in range(N+1):
maxD = max(maxD, A[n+1] - A[n])
print(K-maxD)
追記:pythonはli[-1]みたいにマイナスのインデックスを取れるので、配列を増やす必要もないですね。
D - Line++
与えられたグラフから最短経路長の分布を出す問題です。
pythonでグラフ理論を扱うことのできるnetworkxというライブラリがあります。グラフの作成から各パラメータを取得することができるとても便利なライブラリです。これで分布を計算してみましょう。
import networkx as nx
N, X, Y = map(int, input().split())
X -= 1
Y -= 1
out = [0] * N
G = nx.Graph()
G.add_nodes_from(list(range(N)))
G.add_edges_from([(i, i+1) for i in range(N-1)] + [(X, Y)])
for i in range(N-1):
for j in range(i+1, N):
out[nx.shortest_path_length(G, i, j)] += 1
for i in range(1, N):
print(out[i])
まあatcoderではこのライブラリ使えないんですけど。
グラフの探索についてまるで勉強できていないので諦めて次の問題に行きました。
解説を見ました。この問題では実は難しい探索が全くいらないようです。A地点からB地点まで行くための距離はB-A(そのまま1個ずつ進んだ場合)、もしくはabs(A-X) + 1 + abs(B-Y)(X-Yのショートカットを通る場合)の二択しかありません。この二つのうち短いほうが最短経路。
というわけで、上記のコードから最短経路探索の方法だけ書き換えたのが以下のコードです。
N, X, Y = map(int, input().split())
X -= 1
Y -= 1
out = [0] * N
for i in range(N-1):
for j in range(i+1, N):
out[min(j-i, abs(i-X)+1+abs(j-Y))] += 1
for i in range(1, N):
print(out[i])
これで通りました。
E - Red and Green Apples
美味しさ$p_i$を持つ赤いリンゴと美味しさ$q_i$を持つ緑のリンゴ、美味しさ$r_i$を持つ無色のリンゴが与えられます。赤いリンゴをX個、緑のリンゴをY個食べるときの最大のおいしさを求める問題です。無色のリンゴをどう扱うかがカギ。
赤いリンゴから美味しい順にX個、緑のリンゴから美味しい順にY個取ります。あとはX+Y個のリンゴから美味しくないものを順次無色のリンゴに置き換えていくだけ。
X, Y, A, B, C = map(int, input().split())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
R = list(map(int, input().split()))
P.sort()
Q.sort()
R.sort()
out = P[-X:] + Q[-Y:]
out.sort()
for i in range(min(C, X+Y)):
if R[-i-1] > out[i]:
out[i] = R[-i-1]
else:
break
print(sum(out))
これで計算時間に余裕をもって解けました。
この記事はここまでとします。