ABC160 復習

ABC AtCoder Python

A問題

文字列操作の初歩的な部分について問うてる問題ですね。
N文字目へのアクセスを知っていれば何とかなります。

#3文字目と4文字目の比較
s[2] == s[3]

B問題

四則演算をプログラムできれば解けます。

ans = 0
ans += (x // 500) * 1000
ans += (x % 500) // 5 * 5

今回解けたのはここまで。レーティングは無事下がりました・・。

C問題

円周上の各点をすべて回る場合の最短距離を求める問題でした。
コンテスト終了後に解説でわかったのですが、「どこを通るか」ではなく、「どこを通らないか」が重要なんですね。
各点間の距離はO(N)で求まるので、その合計から最長距離を引けばOK・・ということらしいです。
と、いうわけでコンテスト後に解いてみました。コードは以下。

#通らない区間は高々1区間のみなので、区間の合計から最長距離を除いた距離が最短距離となる
k, n = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
#各座標間の距離の合計
total = 0
#各座標間の距離
dist = []

#各座標間の距離を求めつつ、合計を算出
for i in range(n):
    if i == n - 1:
        #座標0をまたいだ場合を考慮する
        temp = (k - a[i]) + a[0]
    else:
        temp = a[i + 1] - a[i]
    total += temp
    dist.append(temp)

#最終的に距離の合計から最長区間距離を除けばそれが答えとなる
ans = total - max(dist)
print(ans)

うーん、解説を読んでみると、そりゃそうだよね・・というくらいに単純な問題でしたねぇ・・。
こういった、「少し考え方を変えると解ける」問題って、すごく苦手です。

D問題

グラフ問題ですね。
解けなかったので、ひとまず解説PDFを参考に解いてみました。

正直、解説PDFのminをとる部分、3つ目の式がわからなかったのですが、抜いても普通にACしました。
x - yのルートを使う場合と使わない場合に分けてそれぞれ考えればよいです。

  1. 使わない場合
    使わない場合は地点iと地点jの差分がそのまま距離となりますので、j-iをすれば距離が定まります。
  2. 使う場合
    使う場合は、地点iからXまでの距離と、地点jから地点Yまでの距離を足して、そこにx-yの距離である1を足します。
    ので、abs(i - x) + 1 + abs(j - y)となります。（下記のコードのminを取っている部分ですね。）
n, x, y = map(int, input().split())

ans = [0] * (n)
#グラフを0-indexで使用するため、デクリメントする
x -= 1
y -= 1

for i in range(n - 1):
    for j in range(i + 1, n):
        #最短距離を求める
        dist = min(j - i, abs(x - i) + 1 + abs(j - y))
        ans[dist] += 1

for x in range(1, len(ans)):
    print(ans[x])

幅優先探索でも解けるようですが、そこはまた次回勉強しようと思います。

E問題

解説PDFを見たらすぐにわかりました。
E問題以降は解説を見ても何もわからないことがほとんどなのですが、今回のは比較的簡単な問題だったのでしょうか。
（コンテスト中に解けてない私が言うのもなんですが・・。）

x, y, a, b, c = map(int, input().split())
red = list(map(int, input().split()))
green = list(map(int, input().split()))
colorless = list(map(int, input().split()))

red.sort(reverse=True)
green.sort(reverse=True)
colorless.sort(reverse=True)

red = red[:x]
green = green[:y]

l = red + green + colorless
l.sort(reverse=True)
ans = sum(l[:x + y])
print(ans)

今回はここまで。