AtCoder ABC128 解説

カイルダイアリー（テキトー）

AtCoder Beginer Constestの解説&反省です。
使用言語はpython。

#A - Apple Pie
やるだけ、解説略

```python
a,p=map(int,input().split())
print((a*3+p)//2)
```
#B - Guidebook
c++とかだとソートがやりずらいらしい？、~~でも簡単だよ、そうパイソーンならね。~~
速度面でc++には追い付かないので初心者さんはあまり鵜呑みにしないように、問題によって使い分けましょう。

```python
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をするで通ります。(内包表記だと二重になってめんどいかも？)




```python
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します。
これでこの問題を解くことができました。

```python
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日追記 リファクタリング版
コンテスト中は冗長なコード書いちゃうもんですよ、ええ。

```python
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が通らなかったのも一応供養しておく。

```python
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通らないやつ
```python
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は最小値しか取れないため+-を反転させることで最大値をとることができるが理屈がとてもややこしい。関数化して[ここ](https://qiita.com/ct158603292321/items/4e64249abfc151d8e82b)に置いておく。残りの考察部分は本家解説を参照してほしい。

```python
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)
```