[PYTHON] AtCoder Past Question Review (12/5)

I will keep a record of the problems that I made a mistake in the past questions of AtCoder and the problems that left an impression on me.

ABC106-C(To infinity) 3WA First, when I repeated 5000 trillion times, I tried to calculate all the numbers from the front. (** It is clear that it will not be in time considering the amount of calculation ) ( Think about what will happen in the end if there are too many **) Next, I forgot to consider the case where 1s are followed by several at the beginning.

s=list(map(int,list(input())))
k=int(input())
for i in range(len(s)):
    if s[i]!=1:
        if i>=k:
            print(1)
        else:
            print(s[i])
        break
else:
    print(1)

ABC105-C(Base -2 Number)

2WA saw the answer

First, I tried to find it in order from the upper digit, but the judgment conditions were more difficult than I expected. (There was no change in the way of thinking that you should ask in order from the last digit here ) I forgot to classify when n is 0. ( Make sure you're doing everything (think extreme cases) **)

n=int(input())
s=""

i=0
while n!=0:
    if abs(n)%2==0:
        s="0"+s
        n=n//2
    else:
        if i%2==0:
            n=(n-1)//2
        else:
            n=(n+1)//2
        s="1"+s
    i+=1
if s="":
    print("0")
else:
    print(s)

ABC138-D(Ki)

I saw the answer over 10WA

I'm not good at wood structure, I really want to overcome it. I didn't know until I saw the answer, and I couldn't write it well in Python. Python seems to be incompatible with recursion, so I'll write recursion in C ++. See comment out for a code description.

C++Answer

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<utility>

using namespace std;

int main(){
  int n,q;cin >> n >> q;
  //u stores the vertices connected to the vertices corresponding to the index.(I don't know which one is the parent at the time of input)
  vector< vector<int> > u(n);
  for(int i=0;i<n-1;i++){
    int a,b;cin >> a >> b;
    //Push twice_Note that you need to back
    u[a-1].push_back(b-1);
    u[b-1].push_back(a-1);
  }
  //c holds the value of the counter at each vertex
  vector<int> c(n,0);
  for(int i=0;i<q;i++){
    //Hold the initial value of the counter once and propagate it to the children in order from the one closest to the root.
    int p,x;cin >> p >> x;
　　c[p-1]+=x;
  }
  //Enter the information of the Node you want to see next in breadth-first search
  //At this time, not only the information of the vertex but also the information of the previous vertex is required.(Prevent backpropagation)
  //Vector is fine, but delete is slow, so use queue
  queue< pair<int,int> > k;k.push(make_pair(-1,0));

  //Breadth-first search(Depth-first search is also OK)
  while(k.size()!=0){//End when there are no more searchable vertices
    int l1=k.size();
    for(int i=0;i<l1;i++){
      pair<int,int> a=k.front();
      int l2=u[a.second].size();
      //Examine the vertices that extend from each vertex
      for(int j=0;j<l2;j++){
        //If the apex extending from that apex is not visited(If the search is proceeding in the direction of the child), Add the value of the counter to that vertex
        if(u[a.second][j]!=a.first){
          c[u[a.second][j]]+=c[a.second];
          #Continue searching to the next vertex
          k.push(make_pair(a.second,u[a.second][j]));
        }
      }
      #Delete it because it is obsolete
      k.pop();
    }
  }

  for(int i=0;i<n;i++){
    cout << c[i];
    if(i==n-1) cout << endl;
    else cout << " ";
  }
}