result

Impressions

In the D problem, I stuck to one policy. If I get stuck, I would like to train so that I can change to a different policy by reviewing the problem statement. I'm starting to see purple in Kodofo, so I'll do my best. I think AtCoder has a lot of losing habits, so I hope I can do my best to the extent that I don't get sick.

Problem A

Distribute $ n $ cards, including $ m $ jokers, to $ k $ people. Here, the person with the most jokers wins, and the score at that time is (the number of jokers that person has)-(the largest number of jokers that other people have). To maximize this score, first consider ** maximizing the number of jokers the winner has **, which is $ x = min (m, \ frac {n} {k}) $ I will. And consider ** minimizing the largest number of jokers that others have **. Therefore, distribute the remaining $ mx $ jokers to others ** as evenly as possible **, but the largest number of jokers that others have is $ y = ceil (\ frac { mx} {k-1}) $. Therefore, the answer is to ask for $ x-y $.

`A.py`


for _ in range(int(input())):
    n,m,k=map(int,input().split())
    x=min(m,n//k)
    y=-((x-m)//(k-1))
    print(max(0,x-y))

Problem B

Whether to turn one white tile of $ 1 \ times 1 $ into black at cost $ x $ or two white tiles of $ 1 \ times 2 $ in the same row at cost $ y $ There are two ways to pave tiles. Under these circumstances, the problem is to pave the tiles at the lowest cost.

Here, when $ y \ geqq 2 \ times x $, all white tiles should be changed only by the former method. On the other hand, when $ 2 \ times x> y $, ** it is best to change the tile color by the latter method , but it can only be done for 2 consecutive squares in the same row. Therefore, in this case, you can paint two consecutive squares in each line in order, and finally paint the unpainted squares by the former method. ( It is a common idea to perform troublesome operations first and adjust later! **)

`B.py`


for _ in range(int(input())):
    n,m,x,y=map(int,input().split())
    a=[[j for j in input()] for i in range(n)]
    ans=0
    if y>=2*x:
        for i in range(n):
            ans+=a[i].count(".")*x
    else:
        for i in range(n):
            for j in range(m-1):
                if a[i][j]=="." and a[i][j+1]==".":
                    a[i][j]="*"
                    a[i][j+1]="*"
                    ans+=y
        for i in range(n):
            ans+=a[i].count(".")*x
    print(ans)

C problem

I was trying to solve the problem without getting rid of the bug, but what I should be aware of when arriving at the correct answer this time is to ** clarify whether the consideration or the implementation is wrong **.

Now let's move on to the problem. First of all, I thought about what happens to the temperature change by adding water one cup at a time in the order of hot → cold → hot →… with a ** line graph **. It will be as follows.

As you can see from the graph, ** always $ \ frac {h + c} {2} $ at even times and gradually the water temperature at odd times $ \ frac {h + c} {2} $ You can see that it approaches **. Therefore, $ 2 $ times is best when the given $ t $ is less than or equal to $ \ frac {h + c} {2} $.

Here, consider the case where the given $ t $ is larger than $ \ frac {h + c} {2} $, but in this case, the odd number of times is always the answer (✳︎). Also, considering the ratio of the amount of hot water to cold water at odd times, the transition is $ 1: 0 \ rightarrow 2: 1 \ rightarrow 3: 2 \ rightarrow… $. Therefore, in the odd number of times, hot water is added $ x + 1 $ times, and cold water is added $ x $ times. Also, the water temperature at this time is $ \ frac {h \ times (x + 1) + c \ times x} {2 \ times x + 1} $, and consider $ x $ which is the closest to $ t $. I will.

Assuming that there exists $ x $ such that $ \ frac {h \ times (x + 1) + c \ times x} {2 \ times x + 1} = t $, $ x = \ frac {ht } {2 \ times t -hc} $ holds. In reality, $ x $ is an integer, so when the water temperature is closest to $ t $, $ x $ is $ floor (\ frac {ht} {2 \ times t -hc}) $ or $ ceil (\ frac {ht} {2 \ times t -hc}) $ (✳︎). Under this, the water temperature in each case is calculated by $ \ frac {h \ times (x + 1) + c \ times x} {2 \ times x + 1} $, which is closer to $ t $. Make a comparison.

Actually, this comparison is a decimal, so ** the accuracy is not enough if you calculate it as it is **. Here, it is necessary to improve the precision by using the Fraction module ** that expresses rational numbers. There is also a Decimal module as a way to improve accuracy, but this is not suitable because it is a module ** for accurately expressing decimal numbers **. In addition, ** Decimal modules may cause errors in division **.

Therefore, the above is implemented accurately and becomes as follows.

✳︎… The above (✳︎) requires proof, but it is omitted because it is easy to deviate from the essence.

`C.py`


from fractions import Fraction
for _ in range(int(input())):
    h,c,t=map(Fraction,input().split())
    if 2*t<=(h+c):
        print(2)
    else:
        x1=(h-t)//(2*t-h-c)
        x2=x1+1
        x1,x2=Fraction(x1),Fraction(x2)
        y1,y2=Fraction(h*(x1+1)+c*x1)/Fraction(2*x1+1),Fraction(h*(x2+1)+c*x2)/Fraction(2*x2+1)
        if abs(y1-t)<=abs(y2-t):
            print(2*x1+1)
        else:
            print(2*x2+1)

D problem

I wanted to find out about the interval, so I tried to solve it using the scale method, but it didn't work very well. ** The scale method does not work unless the section always meets the conditions **, and this is a policy that should be avoided in this problem. I should have switched policies here.

I thought that I could choose a better policy if I was aware of the following points.

① You have to think ** excluding the maximum value ** ② Maximum value is 61 ways at most (-30 ~ 30) ③ ** Subsequences and continuous sections are easy to think of transitions, so they are compatible with DP **

From the above three, it can be thought that it is better to consider a DP ** that has a ** maximum value as a state. That is, $ dp [i] [j]: = $ (the maximum value of a subsequence that includes the $ i $ th and has a maximum value of $ j $). When placed in this way, the transition will be as follows. Also, dp contains -INF as the initial value.

① When selecting only $ a_i $ dp[i][a[i]+30]=0

② When a subsequence has already been selected (under $ dp [i-1] [j]! =-INF $)

(1) When $ j \ leqq a [i] + 30 $ ** The maximum value of the subsequence is $ a [i] + 30 $ **, so $ dp [i] [a [i] +30] = max (dp [i] [a [i] +30] , dp [i-1] [j] + a [i]-(a [i] + 30-j)) $

(2) When $ j> a [i] + 30 $ ** The maximum value of the subsequence does not change **, so $ dp [i] [j] = dp [i-1] [j] + a [i] $

The answer can be found by implementing the above and finding the maximum value included in dp. Also note that ** the maximum is not less than 0 **.

`D.py`


#did it! !!
from itertools import groupby
n=int(input())
a=list(map(int,input().split()))
INF=100000000000000
dp=[[-INF]*61 for i in range(n)]
ans=-INF
for i in range(n):
    #+Don't forget 30
    #Hajime
    if i==0:
        dp[i][a[i]+30]=0
        continue
    #If you choose it first
    dp[i][a[i]+30]=0
    #If it is continuous
    for j in range(61):
        if dp[i-1][j]==-INF:
            continue
        if j<=a[i]+30:
            dp[i][a[i]+30]=max(dp[i][a[i]+30],dp[i-1][j]+a[i]-(a[i]+30-j))
        else:
            dp[i][j]=dp[i-1][j]+a[i]
    ans=max(ans,max(dp[i]))
print(max(ans,0))

After the E problem

I will not solve this time.

[PYTHON] Educational Codeforces Round 88 Bacha Review (8/4)