カイルダイアリー（テキトー）
AtCoder Beginer Constestの解説&反省です。
使用言語はpython。
A - Apple Pie
やるだけ、解説略
a,p=map(int,input().split())
print((a*3+p)//2)
B - Guidebook
c++とかだとソートがやりずらいらしい？、でも簡単だよ、そうパイソーンならね。
速度面でc++には追い付かないので初心者さんはあまり鵜呑みにしないように、問題によって使い分けましょう。
n=int(input())
q=[input().split()+[i]for i in range(n)]
for i in range(n):
q[i][1]=int(q[i][1])
p=sorted(sorted( q ,key=lambda x:x[1],reverse=1),key=lambda x:x[0])
for s,t,r in p:
print(r+1)
C - Switches
ここで会ったが100年目、bit全探索！
ABC119 Synthetic Kadomatsuの悪夢にようやく打ち勝つことができた。
最初この問題から見て意味が分からなくて発狂していたが、制約と雰囲気でなんとなくbit全探索だと分かった。
まず1～nのランプを付いてる付いてないで列挙する([t>>s&1 for s in range(n)]の部分)
そしてLに突っ込んだ、何番のスイッチと対応しているのかというのを受け取り、numpyのファンシーインデックスで何番がついているかどうかを受け取って合計し、それらを2で割った余りの配列をpと比較して同じならans+=1をするで通ります。(内包表記だと二重になってめんどいかも？)
from numpy import*
n,m=map(int,input().split())
l=[]
for i in range(m):
*a,=map(int,input().split())
l.append(a[1:])
*p,=map(int,input().split())
ans=0
for t in range(2**n):
tmp=array([t>>s&1 for s in range(n)])
if p==[sum(tmp[array(i)-1])%2for i in l]:
ans+=1
print(ans)
D - equeue
まずK<nのとき、端からとれる長さfor i range(1～k)の配列を列挙します。vの後ろにvをつけることでこれは簡単に実現できます。そしてk-i回、取得した配列から最小値を捨てることができます。
(ここで手持ちがなくなっても捨てまくっていたのでREを出しまくっていました。)
一回捨てるごとにansのlistに合計を突っ込んでいきます。
次にk>=nのとき、vの配列すべてを一度に取得することができ、k-n回最小値を捨てることができます。
(ここで引っ掛かったのは捨てない状態の合計をansに突っ込んでいなかったのでコーナーケースに引っかかっていました。)
同様に一回捨てるごとにansに合計を突っ込んで最後にmaxします。
これでこの問題を解くことができました。
from heapq import*
n,k=map(int,input().split())
*v,=map(int,input().split())
motimono=[]
ans=[]
if k>=n:
k-=n
heapify(v)
ans.append(sum(v))
for i in range(k):
if len(v)>0:
heappop(v)
ans.append(sum(v))
print(max(ans))
else:
v*=2
for j in range(1,k+1):
for i in range(n-j,n+1):
motimono=v[i:i+j]
ans.append(sum(motimono))
heapify(motimono)
for i in range(k-j):
if len(motimono)>0:
heappop(motimono)
ans.append(sum(motimono))
print(max(ans))
5/30日追記 リファクタリング版
コンテスト中は冗長なコード書いちゃうもんですよ、ええ。
n,k,*v=map(int,open(0).read().split())
motimono=[]
ans=[]
v*=2
for j in range(1,min(n,k)+1):
for i in range(n-j,n+1):
motimono=v[i:i+j]
ans.append(sum(motimono))
motimono.sort()
for i in range(min(k-j,j)):
del motimono[0]
ans.append(sum(motimono))
print(max(ans))
E - Roadwork
解説AC、と見せかけて自前で書いたのはrandom_denseがまったく通らなかったので写経AC。写経版の頭のいいところはクエリもイベントに入れるところ、二分探索する時間を短縮できる。あとは本家解説で理解できると思われ、denseが通らなかったのも一応供養しておく。
import sys;input=sys.stdin.readline
n,q=map(int, input().split())
event=[]
for _ in range(n):
s,t,x=map(int,input().split())
event.append((s-x-0.5,1,x))
event.append((t-x-0.5,-1,x))
for i in range(q):
event.append((int(input()),0,i))
event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
if e > 0:
stop.add(x)
if x<minstop:
minstop=x
is_stop=True
elif e<0:
stop.remove(x)
if minstop==x:
is_stop=False
elif len(stop)>0:
if not is_stop:
minstop=min(stop)
is_stop=True
ans[x]=minstop
print('\n'.join(map(str, ans)))
dense通らないやつ
from bisect import*
import sys;input=sys.stdin.readline
def doevent(lis):
global stop
a,b=lis
if b>=0:
if stop=={-1}:
stop=set()
stop.add(b)
else:
if -b in stop:
stop.remove(-b)
if stop==set():
stop={-1}
return min(stop)
n,q=map(int,input().split())
event=[]
stop=set([-1])
def main():
for i in range(n):
s,t,x=map(int,input().split())
event.append((s-x,x))
event.append((t-x,-x))
event.sort(key=lambda x:x[0])
minlist=[doevent(i)for i in event] #時間をindexとしたminlist
for i in range(q):
print(minlist[bisect_right(event,(int(input()),10**9))-1])
if __name__ == '__main__':
main()
F - Absolute Minima
解説見て最短ACコードを解析してやっとAC。
中央値を中央値より小さい値と大きい値の合計を求めつつかつ高速に求めなければいけない。
その手法は、まず1が来た時のaの値を保管するリストL,Rを作成する。Lを中央値より小さいやつ、Rを大きいやつとする。
そして1が来た時の回数が奇数回ならaをRに入れてからRの最小値をheappopしLにいれる、また偶数回ならLに入れてからLの最大値をheappopしRに入れる。こうすると-L[0]が中央値であり続ける。
これがheappopは最小値しか取れないため+-を反転させることで最大値をとることができるが理屈がとてもややこしい。関数化してここに置いておく。残りの考察部分は本家解説を参照してほしい。
from heapq import*
L,R=[],[]
n=int(input())
B=0
cnt=0
l,r=0,0
for i in range(n):
I=input()
if I[0]=="1":
a,b,c=map(int,I.split())
B+=c
cnt+=1
if cnt%2:
x=heappushpop(R,b)
r+=b-x
heappush(L,-x)
l+=-x
else:
x=heappushpop(L,-b)
l+=-b-x
heappush(R,-x)
r+=-x
else:
med=-L[0]
print(med,cnt%2*med+B+l+r)