AtCoder ABC 160

AtCoder

　3完でした。DはTLEでしたが、コンテスト終了後にPyPyを選択するとコードの書き換えなしでACでした。。。後の祭りですが、次回からはPythonだけでなく、PyPy試す事忘れずにいきたい。

（2020年4月1日　E問題追記）

A - Coffee

問題のリンク

概要

　文字列の3文字目と4文字目、及び5文字目と6文字目が等しいかどうか。

考察

　特になし

コード

S = input()

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



B - Golden Coins

問題のリンク

概要

　X円が与えられた時、以下の条件下で喜びを最大化させる。

  • 500円硬貨 1枚につき喜び+1000

  • 5円硬貨 1枚につき喜び+5

制約

  • 0 ≤ X ≤ 10^9

  • Xは整数

考察

  • 500円と5円以外は無価値。さらに1円当たりの効果率で言えば、5円玉より500円玉の方が良い。

コード

X = int(input())
n500 = X//500
mod = X%500
n5 = mod//5

print(n500*1000 + n5*5)



C - Traveling Salesman around Lake

問題のリンク

概要

　1週K メートルの湖の周りにN軒の家がある。全ての家を訪れる時の最短距離を求める。

制約

  • 2 ≤ X ≤ 10^6

  • 2 ≤ X ≤ 2×10^5

  • 0 ≤ A_1 \lt \cdots \lt A_N \lt K

  • 入力中のすべての値は整数である。

考察

  • N軒全ての家を訪れた時点で探索終了ということは、家々の間（家1と家2, 家2と家3, ...）でどれか一つは通らなくても良いということ。であればその中で最も距離が大きいところを除けば、より最短距離で目的が達成できる。

コード

K, N = map(int, input().split())
A = list(map(int, input().split()))

dist = [0] * (N)  # 家々間の距離を初期化
for i in range(N):
    if i != N-1:
        dist[i] = A[i+1] - A[i]  # 家々間の距離を更新
    else:
        dist[i] = K-A[i] + A[0]  # 最初の家とラストの家の間は単純な引き算ではない

print(sum(dist) - max(dist))



D - Line++

問題のリンク

概要

　典型的な最短路問題。制約が結構厳しい。range(N)でループ三回回すとN9超える。

制約

  • 3 ≤ N ≤ 2×10^3

  • 1 ≤ X, Y ≤ N

  • X + 1 \lt Y

  • 入力中のすべての値は整数である。

考察

　最初から最後までダイクストラ法でチャレンジ。

コード1

　Python3では通らず、PyPyでは通るくらい。工夫した点としては、以下の二つ。

  • 中継地点を1 ~ Nまで全て探索するのでなく、バイパスのみに絞る。

  • 上記の処理をするためにSの初期化を工夫（一律Nではない）

from itertools import combinations

N, X, Y = map(int, input().split())

# Sを単純に初期化するのではなく、[2, 1, 0, 1, 2, 3, ...]の様にソートされた状態で初期化
S = [list(reversed(list(range(1, i+1)))) + list(range(N-i)) for i in range(N)]

# バイパスの距離は1
S[X-1][Y-1] = 1
S[Y-1][X-1] = 1

for i in range(N):
    for j in range(N):
        x, y = X-1, Y-1

        # バイパス経由の方が近い場合、距離更新
        S[i][j] = min(S[i][j], S[i][x]+1+S[y][j])

dist = [0]*N
for i, j in combinations(list(range(N)), 2):
    d = S[i][j]
    dist[d] += 1

for i in range(1, len(dist)):
    print(dist[i])

コード2

　終了後に他の人のコードを見て、なるほどと思ったので貼っときます。（ちょっと改変してます）

N, X, Y = map(int, input().split())
ans = [0]*N

for i in range(1, N):
    for j in range(i+1, N+1):
        d = min(j-i, abs(X-i)+abs(Y-j)+1)
        ans[d] += 1

for i in ans[1:]:
    print(i)

　上手いと思ったのは、以下の点

  • S（二次元配列）を作ってない。そもそもバイパスが存在しなければ、iとjの距離はj-iが保証されているためこの手が使える。

  • 上記に伴って、一度のfor文でans[d] += 1まで処理できてる。自分のコードはS更新後にitertools.combinationsを使ってしまってるので、そこで更に処理時間がかかってしまっている。



E - Red and Green Apples

問題のリンク

コンテスト後にやってみたけど5分くらいで解けた。。。他の人も言っていたけどE問題にしては難易度高くなかったようです。こういうこともあるので、次回のコンテストからは先の問題も目を通していきたい。

概要

  • 赤いリンゴをX。緑のリンゴをY個食べる。
  • それぞれのリンゴには美味しさ（整数）がある。
  • 美味しさを最大化させるようにリンゴを食べた場合、その最大値を求めることが今回のタスク
  • 色がついてない無色のリンゴも存在し、赤と緑のどちらにも代用可能

制約

  • 1 ≤ X ≤ A ≤ 10^5

  • 1 ≤ Y ≤ B ≤ 10^5

  • 1 ≤ C ≤ 10^5

  • 1 ≤ p_i ≤ 10^9

  • 1 ≤ q_i ≤ 10^9

  • 1 ≤ r_i ≤ 10^9

考察

  1. 制約より、無色のリンゴが存在しないと仮定すると、赤いリンゴA個の中から大きい順にX個食べる & 緑のリンゴB個の中から大きい順にY個食べることで、美味しさを最大化することができる。

  2. 無色のリンゴはどちらの色にも代用可能であることから、上記でセレクトされたリンゴのうち美味しさの少ないものと無色のリンゴをチェンジしていけば良い。

コード

X, Y, A, B, C = map(int, input().split())
p = sorted(list(map(int, input().split())), reverse=True)
q = sorted(list(map(int, input().split())), reverse=True)
r = sorted(list(map(int, input().split())), reverse=True)

eat_p = p[:X]
eat_q = q[:Y]
eat = sorted(eat_p + eat_q)

for i in range(min(len(eat), len(r))):
    if eat[i] < r[i]:   # 元々のリンゴより無色のリンゴの方が美味しい場合
        eat[i] = r[i]
    else:
        break

print(sum(eat))