AtCoder Beginner Contest 160参加記(Python)

コンテスト参加記 AtCoder Python ABC160 heapq

AtCoder Beginner Contest 160(ABC160)に参加しました
atcoder.jp

目次



所感

f:id:algo_archit:20200329144445p:plain
今回の結果
ABCE問題の４完１ぺナで2552位でした（パフォーマンス1073）

C問題の問題に思ったよりも苦戦してしまい、回答時点で20分以上経過＋１ぺナで4000位程度と出遅れてしまいました

D問題もダイクストラ法で解こうと思っていたのですが、計算量的にTLEするのは目に見えていたので提出できず

そこであきらめてE問題に移動すると、問題文自体は簡単そう。。
前処理を工夫することで、優先度付きキューを使うことが出来そうだったので粘った結果ACできました

今までのコンテストでも感じてきましたがコンテスト中の負荷が膨大になっているのか、ジャッジが詰まっていたようです


公式のツイッターでもアナウンスがありましたが、同一APIでのコンテスト参加に制限がかけられるそうです
（大学のPCとかからアクセスしてる人が注意すればいい感じですかね？）


A問題：A - Coffee(100点)

問題文
atcoder.jp

coffeeという文字列と同じように、与えられた文字列が
「3番目と4番目の文字が等しく、5番目の文字と6番目の文字が等しい」か
を確認する問題です

pythonでの実装例

s = input()

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



B問題：Golden Coins(200点)

問題文
atcoder.jp

与えられたコインをできる限り500円玉に交換し、さらに余ったコインを５円玉に交換しようという問題です

pythonではAをBで割ったときの商をA//B,余りをA%Bで求めることができます

500円玉＞５円玉の順に交換を行えばOKです
その際にコインの総数を減らすのを忘れないようにしましょう

pythonでの実装例

n = int(input())

total = 0

total += (n//500)*1000#500円玉に交換する

n %= 500#合計枚数を減らす

total += (n//5)*5#5円玉に交換する

print(total)



C問題：Traveling Salesman around Lake(300点)

問題文
atcoder.jp

池の周囲に設定された家をどのように廻れば最短経路になるか、といった問題です

時計回りか、反時計回りに回るかは開始地点と終了地点とを入れ替えるだけなので問題を解くうえでは関係ないです
そこで時計回り固定で考えることにします

それぞれの家間の距離が最大になっている区間を把握し、池一周分の距離から最大区間の距離を引いたものが答えです

与えられるリストに、池の基準点をまたぐときの場合を考慮して

「リストの１番目の要素＋池の１周の距離」をN＋１番目の仮想の家として追加します（下の図参照）
f:id:algo_archit:20200329162238j:plain

pythonでの実装例

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

a += [a[0]+k]#aに要素を追加する

max_len = 0

for i in range(1,n+1):
    max_len = max(max_len,a[i]-a[i-1])

print(k-max_len)



D問題：Line++(400点)（本番中未解答問題）

問題文
atcoder.jp

問題文自体は難解なように見えますが、
「XとYの橋を使うか、使わないかで最短の距離を求める」
という風に言い換えることができます

N個の地点から２点を選択する _N C _2 = \frac{N(N-1)}{2}通りのパターンを探索し

・XYの橋を経由した場合
・XYの橋を経由しない場合

の２パターンを試し、最小値をその２点間の距離として格納します
(橋との距離には絶対値を取ります)

pythonでの実装例

n,x,y = map(int,input().split())

# 0スタートに合わせる
x -= 1
y -= 1

# 距離を格納するためのリスト
lengh_list = [0]*n

for i in range(n-1):
    for j in range(i+1,n):
        len_itoj = min(j-i,abs(x-i)+1+abs(y-j))
        lengh_list[len_itoj] += 1

for length in lengh_list[1:]:
    print(length)



E問題：Red and Green Apples(500点)

問題文
atcoder.jp

元からあった赤色のリンゴと緑色のリンゴに無色のリンゴを適時変色させることで、
全体のおいしさの価値を最大化しようという問題です

ここで、無色のリンゴを変色させるときには

「赤色と緑色のうち最も価値の低いリンゴと無色のうち最も価値の高いリンゴを交換できるだけ交換する」

という方法が価値を最大にするといえます

方針はわかってもこうしたリストにいちいちmin()関数を使って最低値を求めていたら計算時間が間にあいません
こうしたときに使えるのがheapq(優先度付きキュー)です

import heapq

li = [1,5,6,2,4]

heapq.heapify(li)# heapとして扱う

print(heapq.heappop(li))#1
print(heapq.heappop(li))#2
print(heapq.heappop(li))#4
print(heapq.heappop(li))#5
print(heapq.heappop(li))#6

heapq.heapify(list)の形でリストの先頭が常にリストの中の最低値を保持し続けます

heapq.heappush(追加したい要素)でリストに加え
heapq.heappop()で先頭の要素を排除します

heapqを使うと計算量を抑えながら問題を解くことができます

pythonでの実装例

import heapq

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(reverse = True)

#結局赤色上位x個,緑色上位y個だけ残せばよい
p = p[a-x:]
q = q[b-y:]

# heapqの形にする
heapq.heapify(p)
heapq.heapify(q)

#交換できる限り交換を行う
for i in r:
    if p[0] <= q[0]:
        if i > p[0]:
            heapq.heappop(p)
            heapq.heappush(p,i)
    else:
        if i > q[0]:
            heapq.heappop(q)
            heapq.heappush(q,i)

print(sum(p)+sum(q))

#追記：
よくよく考えたらリストをあらかじめソートしているのでheapq使う必要ないのでは。。。