2021-03-27

ABC197 E Traveler

内容

Atcoder Beginner contest E問題 Travelerをpython でAC
問題

atcoder.jp

考えたこと

各色ごとに、左端で終わるか、右端で終わるかのどちらかが最適。
色ごとに試すと、2の(色の数)常になって辛い。
- 前の色の(左端、右端)だけ見れればいいので、[色数][left or right]のDPにできる。

ポイント

最初と最後に番兵を入れると実装が楽
実装

from collections import defaultdict
N = int(input())

# (pos,color)
D = defaultdict(list)

# colors
Colors = set()
for _ in range(N):
    x, c = map(int, input().split())
    D[c].append(x)
    Colors.add(c)

# 0,max+1は番兵
Colors.add(0)
Colors.add(max(Colors)+1)
Colors = list(sorted(Colors))

# 色ごとの、左端と右端
pos_edge = dict()
# 番兵
pos_edge[0] = (0, 0)
pos_edge[max(Colors)] = (0, 0)
for c, vals in D.items():
    pos_edge[c] = (min(vals), max(vals))


DP = defaultdict(lambda: [float("inf"), float("inf")])
# DP[c][0]:cを見終わったときに　cの左端にいる
# DP[c][1]:cを見終わったときに　cの右端にいる

# スタートは、cost0
DP[0][0] = 0
DP[0][1] = 0

for i in range(1, len(Colors)):
    prev = Colors[i-1]
    cur = Colors[i]

    prev_left, prev_right = pos_edge[prev]
    cur_left, cur_right = pos_edge[cur]

    # (left,right)->left
    for key, p in zip([0, 1], [prev_left, prev_right]):
        # p->right->left
        cost = abs(cur_right-p)+(cur_right-cur_left)
        DP[cur][0] = min(DP[cur][0], DP[prev][key]+cost)

    # (left,right)=>right
    for key, p in zip([0, 1], [prev_left, prev_right]):
        # p->left->right
        cost = abs(cur_left-p)+(cur_right-cur_left)
        DP[cur][1] = min(DP[cur][1], DP[prev][key]+cost)

print(min(DP[Colors[-1]]))

終わりに

2021-03-16

第5回ドワンゴからの挑戦状予選 C - k-DMC

atcoder python 競プロ尺取り

内容

第5回ドワンゴからの挑戦状予選 C - k-DMCをpythonで解いた。
問題
atcoder.jp

考えたこと

クエリの数が少ないので、各クエリにO(N)くらいで答えればいいや。
区間の幅を固定して、スライドさせていくと解けそう。
- 尺取りだ!
  ポイント
区間の中の、Dの数、Mの数、DMのくみの数を記録しておく。
実装

N = int(input())
S = input()
Q=int(input())
Queries=list(map(int,input().split()))

for wid in Queries:
    ans=0

    d_cnt=0#[i,i+wid)に含まれる Dの数
    m_cnt=0#[i,i+wid)に含まれる Mの数
    dm_cnt=0#[i,i+wid)に含まれる [D,M]の組み合わせ数

    for i in range(wid):
        if S[i]=="D":
            d_cnt+=1
        elif S[i]=="M":
            m_cnt+=1
            dm_cnt+=d_cnt
        elif S[i]=="C":
            ans+=dm_cnt


    #尺取り
    for i in range(N-wid):
        remove=S[i]
        #removeする要素に応じて、各cntの値を更新する
        if remove=="D":
            d_cnt-=1
            #左端のDがなくなると、m_cntだけDMの組み合わせ数が減る
            dm_cnt-=m_cnt
        elif remove=="M":
            #左端のMがなくなっても、DMのくみの数は変わらない。(左端のMはDとペアを作れてないから)
            m_cnt-=1
        elif remove=="C":
            pass

        #addする要素に応じて、値を更新する
        new_add=S[i+wid]
        if new_add=="D":
            d_cnt+=1
        elif new_add=="M":
            #区間の右端のMが増えると、区間内のDの数だけ、DMの組み合わせが増える
            m_cnt+=1
            dm_cnt+=d_cnt
        elif new_add=="C":
            #左端にCが入ってくると、DMの組の数だけ、DMCができる
            ans+=dm_cnt

    print(ans)

終わりに

2021-02-13

DDPC B - DDPC特別ビュッフェⅡ

atcoder python 競プロ greedy 二分探索

内容

DDPC B問題 "DDPC 特別ビュッフェII"を、pythonで解いた。
にぶたんのメモ。

問題

atcoder.jp

考えたこと

条件を満たす最小時間を求めろ。
美味しさが高いものから食べていけばよさそう。
二分探索でいけるのでは ?と思い、二分探索

ポイント

制限時間があるのがややこしくなる。
- 時刻を逆から考えることにする
  - hoge分に食べれなくなる-> huga分に食べれるようになる。　に言い換えることで、heapqを使って実装できる。
  - e.g x分以内に食べ切るとき、Ti>xのものは、最初から食べれる。 Ti<=xのものは、x分間のシミュレーションの中で、x-Ti分以降に食べれるようになる。
    実装

from collections import defaultdict
import heapq

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

foods = [(t, a) for t, a in zip(T, A)]

# D[t]:時刻tに締め切りが来る食べ物の、美味しさのlist
D = defaultdict(list)
for t, a in zip(T, A):
    D[t].append(a)


def check(x):
    """
    return True if x秒で　美味しさX食べれる
    """

    # 食べれる候補
    Q = []
    tmp = 0

    #　最初から食べれるもの
    for t, a in foods:
        if t > x:
            heapq.heappush(Q, -a)

    # 0~x 秒まで、何を食べるかシミュレート
    for i in range(x):
        # add
        for v in D[x-i]:
            heapq.heappush(Q, -v)

        if len(Q) == 0:
            continue
        #　現時点でもっとも美味しい物を食べる
        cur = -heapq.heappop(Q)
        tmp += cur

    # 美味しさの和が　X以上ならTrue
    return tmp >= X


low = 0
high = 10**5+1

while low <= high:
    mid = (low+high)//2
    if check(mid):
        high = mid-1
    else:
        low = mid+1

if check(low):
    print(low)
else:
    print(-1)

終わりに

2021-02-05

CODE FESTIVAL2015-D 壊れた電車

atcoder python 競プロ二分探索 greedy

内容

CODE FESTIVAL2015　予選A D問題「壊れた電車」をpythonで解いた。
二分探索をバグらせがちなので、メモとして。

問題

atcoder.jp

考えたこと

最小値を求める問題で、にぶんたんができそうなので、　にぶたんする。
ポイント
シミュレーションの時に、左の車両から優先して掃除するようにする。

実装

N,M = map(int,input().split())
POS=[int(input())-1 for _ in range(M)]

low=0
high=2*N

def check(x):
    """
    x-minuteで掃除できるか (True/False)
    """

    #掃除していない最右車両
    dirty_right=0 
    for pos in POS:
        if dirty_right<pos: #自分より左側に未掃除の領域がある
            to_left_move = pos-dirty_right #　必要な左移動の数
            if to_left_move>x: #　境界まで届かない
                return False
            else:
                # right-first (一旦右行ってから左に行く)
                right_first=pos+max(x-to_left_move*2,0)+1
                # left_first (一旦左に行ってから右に行く)
                left_first = pos+max((x-to_left_move)//2,0)+1

                dirty_right = max(right_first,left_first)
        else: #できるかぎり右まで綺麗にする
            dirty_right = max(dirty_right,pos+x+1)

    #N車両全部掃除できた?
    if dirty_right<N:
        return False
    return True

while low<=high:
    mid = (low+high)//2
    if check(mid):
        high=mid-1
    else:
        low=mid+1
print(low)

終わりに

WAの時に、check()が間違っているのか、二分探索の更新とか終了条件が間違っているのかわからずに、詰まった。
にぶたんの書き方を、テンプレ化して、にぶたんの部分のバグに悩まないで済むようにしたい。

2021-01-31

AOJ Matrix Chain Multiplication

atcoder python 競プロ AOJ 区間DP

内容

AOJ "Matrix Chain Multiplication"を pythonでといた。
下のやつの区間DP編 qiita.com

問題

複数の行列の積を計算するときに、どの順番で計算すると、scalarの乗算が少なくなるのか? http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_B&lang=ja
e.g. A:(1,2),B:(2,3),C:(3,4)の3つの二次元行列があった時に、
- (A*B)*Cだと 1*2*3+1*3*4=18
- A*(B*C)だと、2*3*4+1*2*4=32
この例では、(A*B)*Cの18が答えとなる。

考えたこと

DPする。
ポイント
pythonで再帰したくなので再起なしで書く。
- 区間の幅を小さい方から、計算していく。
  実装

N = int(input())
M = [list(map(int, input().split())) for _ in range(N)]


# DP[l][r]=>[l,r)について、答え
DP = [[float("inf")]*(N+1) for _ in range(N)]

for i in range(N):
    DP[i][i] = 0  # 区間じゃない
    DP[i][i+1] = 0  # 要素が一つなので、掛け算にならない->0

for wid in range(2, N+1):  # 区間の幅
    for l in range(N):  # 区間の左端
        r = l+wid  # 右端(区間に含まれない)
        if r > N:  # はみ出てる
            continue

        if wid == 2:
            DP[l][r] = min(DP[l][r], DP[l][r-1]+M[l][0]*M[l][1]*M[l+1][1])
        else:
            for mid in range(l, r):  # [l,r)のなかで、どこを真ん中にするか
                DP[l][r] = min(DP[l][r], DP[l][mid]+DP[mid]
                               [r]+M[l][0]*M[mid][0]*M[r-1][1])
print(DP[0][-1])  # [0,N+1)が答え

pythonで青くなるブログ

主に競プロのについての記事(日記的な)を書きます。現在atcoder水色,こどふぉ青色。python3使って、やってます。atcoder青くなりたい

ABC197 E Traveler

内容

問題

考えたこと

ポイント

実装

終わりに

第5回ドワンゴからの挑戦状予選 C - k-DMC

内容

問題

考えたこと

ポイント

実装

終わりに

DDPC B - DDPC特別ビュッフェⅡ

内容

問題

考えたこと

ポイント

実装

終わりに

CODE FESTIVAL2015-D 壊れた電車

内容

問題

考えたこと

ポイント

実装

終わりに

AOJ Matrix Chain Multiplication

内容

問題

考えたこと

ポイント

実装

終わりに