[PYTHON] AtCoder Beginner Contest 067 Rückblick auf frühere Fragen

Die zweite Frage, die ich bereits gelöst habe

Benötigte Zeit

Problem A

Fälle, die ein Vielfaches von 3 sind

answerA.py

a,b=map(int,input().split())
if a%3==0 or b%3==0 or (a+b)%3==0:
    print("Possible")
else:
    print("Impossible")

B-Problem

Holen Sie sich k von der größeren

answerB.py

n,k=map(int,input().split())
l=[int(i) for i in input().split()]
l.sort(reverse=True)
print(sum(l[:k]))

C-Problem

Schauen Sie es sich einfach von vorne an und aktualisieren Sie mi

answerC.py

n=int(input())
a=[int(i) for i in input().split()]
s=sum(a)
c=0
b=[]
for i in range(n-1):
    c+=a[i]
    b.append(c)
mi=abs(s-2*b[0])
for i in range(n-1):
    mi=min(mi,abs(s-2*b[i]))
print(mi)

answerC2.py

n=int(input())
a=[int(i) for i in input().split()]
s=sum(a)
c=a[0]
mi=abs(s-2*c)
for i in range(1,n):
    c+=a[i]
    mi=min(mi,abs(s-2*c))
print(mi)

D Problem

Unter der Bedingung, dass wir in der Reihenfolge vom nächstgelegenen Ort aus malen, ** dachte ich, dass derjenige, der näher an den Knoten 1 und N liegt, schwarz und weiß sein würde ** (Es ist ein wenig gewachsen, seit ich in der Lage war, diese Idee zu verwirklichen. ), Aber ich konnte mir nicht vorstellen, dass 1 und N den gleichen Abstand vom Knoten haben. Eigentlich habe ich es nicht bemerkt, als ich es gelöst habe, aber ich konnte die Bedeutung von "optimal handeln" nicht verstehen. Wenn eine Route ** 1 und N verbindet, werden die Farben in der Reihenfolge vom Knoten auf dieser Route gezeichnet, und wenn mehrere Routen vorhanden sind, wird die Farbe in der Reihenfolge von der Route mit mehr Farben auf der anderen Seite gezeichnet. ** ist das, was es bedeutet. Stellen Sie sich vor, wenn Sie diesen Pfad malen (siehe Abbildung in Erläuterung), ist die Ableitung "schwarz im ersten Knoten". Wenn man dies zusammen betrachtet, ist der Abstand zwischen dem i-ten und dem j-ten Knoten d (i, j) und ** d (1, i) <= d (N, i) ist schwarz, wenn er auf diesem Pfad bleibt * Sie können sehen, dass es * wird. Für Knoten, die sich nicht auf diesem Pfad befinden, wird die Farbe eindeutig aus der auf diesem Pfad gemalten Farbe bestimmt, und es ist klar, dass d (1, i) <= d (N, i) gilt (wenn es schwarz ist). ist. Wenn Sie wie oben darüber nachdenken können, lautet der Code wie folgt, da Sie BFS oder DFS schreiben können. (Es ist in DFS geschrieben.) (Am Ende lautet der Punkt ** Ich möchte die Entfernung vom Knoten wissen, weil er von einem nahe gelegenen Ort aus gemalt ist **, ** Ich möchte die Position des Gegners mehr untergraben, weil ich optimal agiere ** ,.)

answerD.cc

#include<iostream>
#include<vector>

using namespace std;
typedef vector< vector<int> > vv;
#define INF 10000000

void dfs(int now,vv& tree,vector<int>& dep,int d,vector<bool>& check){
  dep[now]=d;
  check[now]=true;
  int l=tree[now].size();
  for(int i=0;i<l;i++){
    if(check[tree[now][i]]==false){dfs(tree[now][i],tree,dep,d+1,check);}
  }
}

int main(){
  int n;cin >> n;
  vv tree(n);
  for(int i=0;i<n-1;i++){
    int a,b;cin >> a >> b;
    tree[a-1].push_back(b-1);
    tree[b-1].push_back(a-1);
  }
  vector<int> dep1(n,INF);
  vector<bool> check1(n,false);
  vector<int> dep2(n,INF);
  vector<bool> check2(n,false);
  dfs(0,tree,dep1,0,check1);
  dfs(n-1,tree,dep2,0,check2);
  int c1=0;int c2=0;
  for(int i=0;i<n;i++){
    if(dep1[i]<=dep2[i]){
      c1+=1;
    }else{
      c2+=1;
    }
  }
  if(c1>c2){
    cout << "Fennec" << endl;
  }else{
    cout << "Snuke" << endl;
  }
}