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

Les résultats de cette fois

Impressions de cette époque

Personnellement, je ne veux pas tellement résoudre des temps non évalués, mais je ne l'ai pas remarqué.

Problème A

J'ai également été surpris par le problème du bâillon. Kodfo a-t-il une telle tendance ...?

$ a \ _x + a \ _y \ neq a \ _z $ doit être composé de any ($ x, y, z $). Cela est vrai si tous les éléments sont dans la même séquence de nombres. Par conséquent, vous n'avez besoin de sortir que 1 pour le nombre d'éléments donné (bien que d'autres nombres conviennent).

A.py

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

Problème B

Je pense avoir vu un problème similaire avec AtCoder, mais je ne m'en souviens pas.

J'ai pensé à maximiser ** $ GCD (a, b) $ pour minimiser $ LCM (a, b) $. De plus, puisque $ GCD (a, b) $ est une fraction de $ n $, sélectionnez la plus grande fraction de $ N $ ($ X $) à l'exclusion de $ n $ (✳︎1).

À ce stade, $ N = X \ fois K $ ($ K $ est un entier de 2 ou plus). De plus, si $ a = X \ fois Y $ ($ Y $ est un entier positif inférieur à $ K $), alors $ b = X \ times (K-Y) $. Ici, $ Y $ et $ K-Y $ peuvent être considérés comme étant mutuellement exclusifs de la condition de $ X $, donc $ LCM (a, b) = X \ fois Y \ fois (K-Y) $. Et puisque $ X $ et $ K $ ont déjà été déterminés, $ Y $ est positif et $ LCM (a, b) $ est ** $ Y $ décroissant monotone **, donc $ Y = K-1 $ C'est le minimum. Par conséquent, quand $ a = X \ fois (K-1), b = X $, $ LCM (a, b) $ le produit au minimum (✳︎2).

De plus, (✳︎1) n'a pas été affiché pendant le concours à cause de ma supposition, mais il peut être affiché à l'inverse de (✳︎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)

Problème C

J'ai été trompé par le fait que c'était moins de 10 $ ^ {18} $ fois dans l'énoncé du problème. En réalité, il n'y en a que deux au maximum.

Tout d'abord, j'ai changé avidement la position du numéro, j'ai donc mené une expérience avec l'échantillon 2. Ensuite, cela devient comme suit.

En d'autres termes, à partir de l'expérience ci-dessus, on peut dire que ** il n'est pas nécessaire de changer celui qui correspond déjà à la position au bord **, et s'il y a ** qui a la même position ** à l'exclusion du bord ** (échantillon) Comme vous pouvez le voir, il semble qu'il devra être remplacé deux fois. De plus, il est évident que vous ne pouvez pas l'échanger une fois, mais vous pouvez aussi sentir qu'il peut être échangé deux fois. En d'autres termes, la colonne numérique $ a \ _1, a \ _2,…, a \ _n $ avant l'échange est échangée contre la séquence de nombres $ b \ _1, a \ _2,…, a \ _n $ Ce serait bien de montrer qu'il peut être échangé contre 1,2 $,…, n $. À ce stade, $ b \ _i \ neq a \ _i $ et $ b \ _i \ neq i $ doivent être valables pour tout $ i $. Pendant le concours, je suis arrivé à la conclusion qu'un tel $ b \ _i $ pouvait être fait en échangeant avec succès plusieurs lignes.

De plus, la preuve ci-dessus semble possible, mais elle n'est pas gênante. ** Je pense que je peux le montrer car il suffit d'avoir une relation [ordre parfait](https://ja.wikipedia.org/wiki/complete order) ** les uns avec les autres. ** Il est intuitif que si vous pouvez afficher un petit motif de $ n $, il sera possible de le faire avec un plus grand $ n $ **.

De plus, s'il n'y a personne qui correspond à la position sauf pour la fin, il est possible de le remplacer une fois, et si toutes les positions correspondent depuis le début, il n'est pas nécessaire de le remplacer, il est donc possible de le remplacer 0 fois. ..

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
    #Hors les bords
    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
    #Erreur d'index
    for k in range(i,j+1):
        if a[k]==k+1:
            print(2)
            break
    else:
        print(1)

Problème D

C'était difficile à déboguer et le temps restant était court car j'ai utilisé une méthode lourde et gourmande pour l'implémentation avec une considération appropriée. ** N'utilisez pas de méthodes gourmandes dont la validité ne peut pas être démontrée **.

Tout d'abord, deux nombres disparaissent à chaque fois, et un nombre disparaît en tant que total, donc ** $ [\ frac {n} {2}] $ nombres disparaissent **. Par conséquent, envisagez de réduire au maximum la somme de ces nombres. Cela dit, les nombres $ [\ frac {n} {2}] $ ne sont ** pas susceptibles d'être choisis arbitrairement **, donc je vais essayer. Ensuite, ce sera comme indiqué dans la figure ci-dessous.

À partir de la figure ci-dessus, vous pouvez voir que lors de l'effacement de $ [\ frac {n} {2}] $ nombres, ** les nombres les uns à côté des autres ne peuvent pas être effacés **. De plus, ** arrangez les nombres de façon à ce qu'ils ne soient pas côte à côte ** et $ a \ _1, a \ _3,…, a \ _ {n-2}, a \ _n, a \ _2, a \ _4,…, Cela devient un \ _ {n-3}, un \ _ {n-1} $. Si vous sélectionnez ces nombres $ [\ frac {n} {2}] $ consécutifs, aucun nombre ne sera contigu, sinon vous pouvez effacer les nombres les uns à côté des autres. Vous pouvez trouver la valeur maximale d'un nombre de nombres $ [\ frac {n} {2}] $ consécutifs ($ n $ rues) tout en comptant la différence.

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()

Après le problème E

Je vais sauter cette fois