[PYTHON] AtCoder Beginner Contest 066 Revoir les questions précédentes

Temps requis

スクリーンショット 2020-01-15 13.38.16.png

Problème A

Choisissez simplement les deux plus petits.

answerA.py


a,b,c=map(int,input().split())
x=[a,b,c]
print(sum(x)-max(x))

Problème B

Effacez simplement la fin dans l'ordre et pensez-y.

answerB.py


s=input()
l=len(s)
for i in range(1,l//2):
    k=(l-i*2)
    if s[:k//2]==s[k//2:k]:
        print(k)
        break

Problème C

Si vous pensez à ** comment vous poussez réellement **, vous pouvez voir que l'arrangement est différent pour les poussées impaires et paires (voir exemple), donc si vous implémentez cet arrangement avec obéissance, ce sera comme suit. .. (Il est également nécessaire de noter qu'il existe des cas dus à la régularité de n.)

answerC.py


n=int(input())
a=[i for i in input().split()]

b=[]
c=[]
if n%2==0:
    for i in range(n):
        if i%2==0:
            b.append(a[i])
        else:
            c.append(a[i])
else:
    for i in range(n):
        if i%2==0:
            c.append(a[i])
        else:
            b.append(a[i])
c=c[::-1]
print(" ".join(c)+" "+" ".join(b))

Problème D

La politique a été établie normalement, mais la mise en œuvre n'a pas pu être achevée. (** La capacité de montage ** est également l'un des problèmes, mais il semble qu'il n'y ait pas d'autre choix que de gérer le montant ...) On a découvert quelques heures plus tard que je n'étais pas au courant des erreurs de base dans les bases.

Les restes négatifs se comportent involontairement! !!

Comme vous pouvez le voir en vous référant à cet article, il semble qu'il existe plusieurs définitions pour le reste, et chaque langue se comporte différemment. Il semble. Pour éviter cela, vous pouvez changer le nombre négatif en un nombre positif tel qu'écrit dans le code. (Je pense que c'est basique, mais je ne connaissais pas le C ++ parce que je n'en savais pas grand chose. Je devrais étudier le C ++ plus correctement ...)

En ce qui concerne la politique, si vous comptez la sous-colonne de longueur k à partir du tout, y compris la duplication, ce sera $ _ {n + 1} C _k $, donc ** Expérimentez pour déterminer s'il peut y avoir duplication ** Faire. Selon l'expérience, soit x le nombre qui existe dans deux, et lorsque x est dans l'indice i, j (0 <= i, j <= N), lorsque les deux sont inclus dans la sous-colonne, ils peuvent se chevaucher. Vous pouvez également voir qu'il n'y a pas de doublons lorsqu'ils n'existent pas et qu'aucun des deux n'est inclus dans la sous-colonne. Considérez maintenant ** lorsque vous souhaitez inclure un seul x dans une sous-colonne **. Compte tenu du fait que le nombre de parties i + 1 à j-1 est inclus, le nombre est situé sur le côté droit pour x dans i et le nombre est situé sur le côté gauche pour x dans j, donc les différentes parties Vous pouvez voir qu'il est divisé en colonne. Par conséquent, les nombres dans ** 0 ~ i-1, j + 1 ~ N et les sous-colonnes sélectionnées parmi x sont des doublons **, et $ _ {i + (nj)} C _ {k -1} $ est le nombre de sous-chaînes dupliquées pour les sous-colonnes de longueur k. Par conséquent, vous pouvez trouver $ _ {n + 1} C k- {i + (nj)} C _ {k-1} $, mais comme je l'ai écrit plus tôt, ne générez pas de reste négatif. Dans le cas d'un nombre négatif, vous pouvez le réduire à un surplus positif en ajoutant des MOD.

De plus, le calcul du regroupement est emprunté à M. Kencho. Pour plus de détails, veuillez consulter cet article.

answerD.cc


#include<iostream>
#include<vector>
#include<utility>
using namespace std;

const int MAX = 1000000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

//Prétraitement pour faire une table
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

//Calcul du coefficient binaire
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(){
  //Prétraitement
  COMinit();
  int n;cin >> n;
  vector<int> a(n+1);for(int i=0;i<n+1;i++){cin >> a[i];a[i]-=1;}
  vector<bool> b(n,true);
  for(int i=0;i<n+1;i++){b[a[i]]=!b[a[i]];}
  pair<int,int> p=make_pair(-1,-1);
  for(int i=0;i<n+1;i++){
    if(b[a[i]]){
      if(p.first==-1){p.first=i;}
      else{p.second=i;break;}
    }
  }
  //Au début, c était sorti dans la partie suivante, mais c<Puisqu'il y a une possibilité de 0, il n'y a pas exactement le reste du MOD
  for(int i=1;i<=n+1;i++){
    int c=COM(n+1,i)-COM(p.first+(n-p.second),i-1);
    while(c<0){
      c+=MOD;
    }
    cout << c%MOD << endl;
  }
}

Recommended Posts

AtCoder Beginner Contest 066 Revoir les questions précédentes
AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 085 Revue des questions précédentes
AtCoder Beginner Contest 062 Revue des questions précédentes
AtCoder Beginner Contest 113 Revue des questions précédentes
AtCoder Beginner Contest 074 Revue des questions précédentes
AtCoder Beginner Contest 051 Revue des questions précédentes
AtCoder Beginner Contest 119 Revue des questions précédentes
AtCoder Beginner Contest 151 Revue des questions précédentes
AtCoder Beginner Contest 075 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 110 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 070 Revue des questions précédentes
AtCoder Beginner Contest 105 Revue des questions précédentes
AtCoder Beginner Contest 112 Revue des questions précédentes
AtCoder Beginner Contest 076 Revue des questions précédentes
AtCoder Beginner Contest 089 Revue des questions précédentes
AtCoder Beginner Contest 069 Revue des questions précédentes
AtCoder Beginner Contest 079 Revue des questions précédentes
AtCoder Beginner Contest 056 Revue des questions précédentes
AtCoder Beginner Contest 087 Revue des questions précédentes
AtCoder Beginner Contest 093 Revue des questions précédentes
AtCoder Beginner Contest 046 Revue des questions précédentes
AtCoder Beginner Contest 123 Revue des questions précédentes
AtCoder Beginner Contest 049 Revue des questions précédentes
AtCoder Beginner Contest 078 Revue des questions précédentes
AtCoder Beginner Contest 047 Revue des questions précédentes
AtCoder Beginner Contest 104 Revue des questions précédentes
AtCoder Beginner Contest 057 Revue des questions précédentes
AtCoder Beginner Contest 121 Revue des questions précédentes
AtCoder Beginner Contest 090 Revue des questions précédentes
AtCoder Beginner Contest 103 Revue des questions précédentes
AtCoder Beginner Contest 061 Revue des questions précédentes
AtCoder Beginner Contest 083 Revue des questions précédentes
AtCoder Beginner Contest 124 Revue des questions précédentes
AtCoder Beginner Contest 116 Revue des questions précédentes
AtCoder Beginner Contest 097 Revue des questions précédentes
AtCoder Beginner Contest 092 Revue des questions précédentes
AtCoder Beginner Contest 099 Revue des questions précédentes
AtCoder Beginner Contest 065 Revue des questions précédentes
AtCoder Beginner Contest 053 Revue des questions précédentes
AtCoder Beginner Contest 094 Revue des questions précédentes
AtCoder Beginner Contest 063 Revue des questions précédentes
AtCoder Beginner Contest 107 Revue des questions précédentes
AtCoder Beginner Contest 071 Revue des questions précédentes
AtCoder Beginner Contest 064 Revue des questions précédentes
AtCoder Beginner Contest 082 Revue des questions précédentes
AtCoder Beginner Contest 084 Revue des questions précédentes
AtCoder Beginner Contest 058 Revue des questions précédentes
AtCoder Beginner Contest 043 Revue des questions précédentes
AtCoder Beginner Contest 098 Revue des questions précédentes
AtCoder Beginner Contest 114 Revue des questions précédentes
AtCoder Beginner Contest 045 Revue des questions précédentes
AtCoder Beginner Contest 120 Revue des questions précédentes
AtCoder Beginner Contest 108 Revue des questions précédentes
AtCoder Beginner Contest 106 Revue des questions précédentes
AtCoder Beginner Contest 122 Revue des questions précédentes
AtCoder Beginner Contest 125 Revue des questions précédentes
AtCoder Beginner Contest 109 Revue des questions précédentes
AtCoder Beginner Contest 118 Revue des questions précédentes