[PYTHON] Codeforces Round # 663 (Div. 2) Bacha Review (8/16)

This time's results

スクリーンショット 2020-08-16 18.31.43.png

Impressions of this time

Personally, I don't want to solve unrated times so much, but I did not notice it.

Problem A

I was also surprised by the gag problem. Does Kodfo have such a tendency ...?

$ a \ _x + a \ _y \ neq a \ _z $ should consist of any ($ x, y, z $). This is true if all the elements are in the same sequence. Therefore, you only need to output 1 for the given number of elements (although other numbers are fine).

A.py


for _ in range(int(input())):
    print(" ".join(map(str,[1]*int(input()))))

Problem B

I think I saw a similar problem with AtCoder, but I don't remember.

I thought about maximizing ** $ GCD (a, b) $ to minimize $ LCM (a, b) $. Also, since $ GCD (a, b) $ is a divisor of $ n $, select the largest divisor of $ N $ ($ X $) excluding $ n $ (✳︎1).

At this time, $ N = X \ times K $ ($ K $ is an integer of 2 or more). Also, if $ a = X \ times Y $ ($ Y $ is a positive integer less than $ K $), then $ b = X \ times (K-Y) $. Here, $ Y $ and $ K-Y $ are relatively prime from the condition of $ X $, so $ LCM (a, b) = X \ times Y \ times (K-Y) $. And since $ X $ and $ K $ have already been determined, $ Y $ is positive and $ LCM (a, b) $ is monotonically decreasing ** with respect to ** $ Y $, so $ Y = K-1 $ Is the minimum. Therefore, when $ a = X \ times (K-1), b = X $, $ LCM (a, b) $ outputs this at the minimum (✳︎2).

Also, (✳︎1) was not shown during the contest because of my guess, but it can be shown in reverse from (✳︎2).

B.py


for _ in range(int(input())):
    n,m=map(int,input().split())
    a=[input() for i in range(n)]
    ans=0
    for i in range(m-1):
        ans+=(a[n-1][i]=="D")
    for i in range(n-1):
        ans+=(a[i][m-1]=="R")
    print(ans)

C problem

I was fooled by the fact that the question text said that it was less than $ 10 ^ {18} $ times. In reality, there are only two times at the maximum.

First of all, I greedily changed the position of the number, so I experimented with sample 2. Then, it becomes as follows.

IMG_0553.PNG

In other words, from the above experiment, it can be said that ** there is no need to change the one that already corresponds to the position at the edge **, and ** if there is one that matches the position ** excluding the edge ** (sample As you can see) it looks like it will need to be replaced twice. Also, it is obvious that you cannot exchange it once, but you can also feel that you can exchange it twice. That is, the sequence $ a \ _1, a \ _2,…, a \ _n $ before the exchange is exchanged for the sequence $ b \ _1, a \ _2,…, a \ _n $, and finally the exchange is performed. It would be nice to show that it can be exchanged for $ 1,2,…, n $. At this time, $ b \ _i \ neq a \ _i $ and $ b \ _i \ neq i $ must hold for any $ i $. During the contest, I came to the conclusion that such $ b \ _i $ could be made by successfully exchanging sequences.

Also, the above proof seems to be possible, but it is not troublesome. ** I think I can show it because it is only necessary to have a perfect permutation relationship ** with each other. ** It is intuitive that if you can show a small pattern of $ n $, it will be possible with a larger $ n $ **.

Furthermore, if there is no one that matches the position except for the end, it is possible to replace it once, and if all the positions correspond from the beginning, it is not necessary to replace it, so it is possible to replace it 0 times. ..

C.py


for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    if a==[i+1 for i in range(n)]:
        print(0)
        continue
    #Excluding the edges
    for i in range(n):
        if a[i]!=i+1:
            break
    for j in range(n-1,-1,-1):
        if a[j]!=j+1:
            break
    #Index error
    for k in range(i,j+1):
        if a[k]==k+1:
            print(2)
            break
    else:
        print(1)

D problem

It was difficult to debug and the remaining time was short because I used a greedy method with a heavy implementation that was properly considered. ** Do not do greedy algorithms that cannot be shown to be valid **.

First, two numbers disappear each time, and one number disappears as a sum, so ** $ [\ frac {n} {2}] $ numbers disappear **. Therefore, consider making the sum of these numbers as small as possible. That said, the $ [\ frac {n} {2}] $ numbers ** don't seem to be arbitrary **, so I'll experiment. Then, it will be as shown in the figure below.

IMG_0554.JPG

From the above figure, you can see that when erasing $ [\ frac {n} {2}] $ numbers, ** the numbers next to each other cannot be erased **. Also, ** arrange the numbers so that they are not next to each other ** and $ a \ _1, a \ _3,…, a \ _ {n-2}, a \ _n, a \ _2, a \ _4,…, It becomes a \ _ {n-3}, a \ _ {n-1} $. If you select these consecutive $ [\ frac {n} {2}] $ numbers, any number will not be consecutive, and otherwise you may erase the numbers next to each other. You can find the maximum value of consecutive $ [\ frac {n} {2}] $ numbers ($ n $ streets) in a sequence while counting the difference.

IMG_5740966239E1-1.jpeg

D.py


import sys
input=sys.stdin.readline
n,m=map(int,input().split())
a=[[int(j) for j in input()[:-1]] for i in range(n)]
if n>=4 and m>=4:
    print(-1)
    exit()
if n==1 or m==1:
    print(0)
    exit()
inf=10000000000000
if n==2 or m==2:
    bitcheck=[[0]*4 for i in range(4)]
    for j in range(4):
        for k in range(4):
            for i in range(1):
                if (((j>>i)&1)+((k>>i)&1)+((j>>(i+1))&1)+((k>>(i+1))&1))%2==0:
                    bitcheck[j][k]=False
                    break
            else:
                bitcheck[j][k]=True
    bitcalc=[[0]*4 for i in range(4)]
    for j in range(4):
        for k in range(4):
            for i in range(2):
                if ((j>>i)&1)^((k>>i)&1):
                    bitcalc[j][k]+=1
    if n==2:
        n,m=m,n
        b=[list(x) for x in zip(*a)]
    else:
        b=[i for i in a]
    dp=[[inf]*4 for i in range(n)]
    for i in range(n):
        if i!=0:
            for j in range(4):
                for k in range(4):
                    if bitcheck[j][k]:
                        dp[i][k]=min(dp[i][k],dp[i-1][j]+bitcalc[b[i][0]+b[i][1]*2][k])
        else:
            for k in range(4):
                dp[i][k]=bitcalc[b[i][0]+b[i][1]*2][k]
    print(min(dp[n-1]))
    exit()
if n==3 or m==3:
    bitcheck=[[0]*8 for i in range(8)]
    for j in range(8):
        for k in range(8):
            for i in range(2):
                if (((j>>i)&1)+((k>>i)&1)+((j>>(i+1))&1)+((k>>(i+1))&1))%2==0:
                    bitcheck[j][k]=False
                    break
            else:
                bitcheck[j][k]=True
    bitcalc=[[0]*8 for i in range(8)]
    for j in range(8):
        for k in range(8):
            for i in range(3):
                if ((j>>i)&1)^((k>>i)&1):
                    bitcalc[j][k]+=1
    if n==3:
        n,m=m,n
        b=[list(x) for x in zip(*a)]
    else:
        b=[i for i in a]
    dp=[[inf]*8 for i in range(n)]
    for i in range(n):
        if i!=0:
            for j in range(8):
                for k in range(8):
                    if bitcheck[j][k]:
                        dp[i][k]=min(dp[i][k],dp[i-1][j]+bitcalc[b[i][0]+b[i][1]*2+b[i][2]*4][k])
        else:
            for k in range(8):
                dp[i][k]=bitcalc[b[i][0]+b[i][1]*2+b[i][2]*4][k]
    print(min(dp[n-1]))
    exit()

After the E problem

I will skip this time

Recommended Posts

Codeforces Round # 654 (Div. 2) Bacha Review (8/18)
Codeforces Round # 594 (Div. 2) Bacha Review (10/29)
Codeforces Round # 609 (Div. 2) Bacha Review (10/8)
Codeforces Round # 597 (Div. 2) Bacha Review (10/27)
Codeforces Round # 666 (Div. 2) Bacha Review (9/2)
Codeforces Round # 651 (Div. 2) Bacha Review (8/20)
Codeforces Round # 659 (Div. 2) Bacha Review (8/5)
Codeforces Round # 610 (Div. 2) Bacha Review (10/5)
Codeforces Round # 603 (Div. 2) Bacha Review (10/15)
Codeforces Round # 600 (Div. 2) Bacha Review (10/21)
Codeforces Round # 481 (Div. 3) Bacha Review (9/24)
Codeforces Round # 612 (Div. 2) Bacha Review (10/2)
Codeforces Round # 521 (Div. 3) Bacha Review (10/9)
Codeforces Round # 652 (Div. 2) Bacha Review (8/24)
Codeforces Round # 673 (Div. 2) Bacha Review (10/22)
Codeforces Round # 613 (Div. 2) Bacha Review (10/1)
Codeforces Round # 662 (Div. 2) Bacha Review (8/8)
Codeforces Round # 618 (Div. 2) Bacha Review (9/26)
Codeforces Round # 648 (Div. 2) Bacha Review (9/5)
Codeforces Round # 676 (Div. 2) Bacha Review (10/31)
Codeforces Round # 675 (Div. 2) Bacha Review (10/30)
Codeforces Round # 486 (Div. 3) Bacha Review (9/23)
Codeforces Round # 671 (Div. 2) Bacha Review (9/22)
Codeforces Round # 672 (Div. 2) Bacha Review (10/16)
Codeforces Round # 638 (Div. 2) Bacha Review (9/16)
Codeforces Round # 663 (Div. 2) Bacha Review (8/13)
Codeforces Round # 668 (Div. 2) Bacha Review (9/7)
Codeforces Round # 663 (Div. 2) Bacha Review (8/16)
Codeforces Round # 609 (Div. 2) Bacha Review (10/6)
Codeforces Round # 645 (Div. 2) Bacha Review (9/10)
Codeforces Round # 664 (Div. 2) Bacha Review (8/13)
Codeforces Round # 660 (Div. 2) Bacha Review (8/4)
Codeforces Round # 643 (Div. 2) Review
Codeforces Round # 679 (Div. 2) Review (10/25)
Codeforces Round # 657 (Div. 2) Review
Educational Codeforces Round 93 Bacha Review (8/17)
Educational Codeforces Round 94 Bacha Review (9/3)
Educational Codeforces Round 91 Bacha Review (7/28)
Educational Codeforces Round 88 Bacha Review (8/4)
Educational Codeforces Round 86 Bacha Review (9/17)
Educational Codeforces Round 89 Bacha Review (9/8)
Educational Codeforces Round 90 Bacha Review (8/19)
Codeforces Round # 609 (Div. 2) (up to B)
Educational Codeforces Round 87
Codeforces Beta Round # 13
Codeforces Beta Round # 1
Codeforces Beta Round # 2
DP100 Question Bacha Review 1 ~ 10 (8 / 26,27)