【今日の精進】ABC203F - Weed

毎日格上の問題を倒すやつの35日目です。

問題リンク

atcoder.jp

問題概要

草が 本あって、 番目の草の高さは だよ。

高橋くんは、以下のようにして草を全部抜くよ。

• を残っている草の中で最も高い草の高さとして、 より高い高さの草を一斉に抜く

青木くんは、草をたかだか 本抜いて、高橋くんの操作回数を最小にしてあげようとしてるよ。

高橋くんの最小の操作回数と、それを達成するために青木くんが抜くべき草の最小の本数を求めてね。

解法

青木くんが抜く草の数でDPしようとすると、 となり明らかに間に合いません。

そこで、「何もしなくても高橋くんの操作回数は著しく少ない」ことに注目します。*1

これに注目すると、以下のようなDPをしたくなります。

• 高い方から 番目の草を高橋くんが 回で抜くときの、青木くんが抜くべき最初の本数

これは遷移を頑張ればちゃんとDP可能です。

提出コード

INF=pow(2,61)-1
N,K=map(int,input().split())
A=sorted(list(map(int,input().split())),reverse=True)
A.append(0)
cnt=0
pos=[-1 for i in range(N)]
for i in range(N):
    while A[cnt]>A[i]//2:
        cnt+=1
    pos[i]=cnt
dp=[[INF for i in range(40)] for i in range(N+1)]
dp[0][0]=0
for i in range(N):
    for j in range(39):
        dp[i+1][j]=min(dp[i][j]+1,dp[i+1][j])
        dp[pos[i]][j+1]=min(dp[i][j],dp[pos[i]][j+1])
for i in range(40):
    if dp[-1][i]<=K:
        print(i,dp[-1][i])
        break

Submission #46911332 - AtCoder Beginner Contest 203（Sponsored by Panasonic）

感想

ナップサックでも出てきた添字を変える典型、すぐに出るようにしたい…

*1:毎回最大の草の高さが半分になるからあっという間に小さくなります