Help us understand the problem. What is going on with this article?

AtCoder過去問復習 (12/5)

AtCoderの過去問精進の際に間違えた問題や印象に残った問題の記録を復習がてら残していきます。

ABC106-C(To infinity)

3WA

まず、5000兆回繰り返した時に前からどの数字がいくつあるのか全て計算しようとした。(計算量考えれば間に合わないことが明らか)(あまりにも多い場合は最終的にどうなりそうかを考える)
次に、1がはじめにいくつか続く場合を考慮し忘れた。

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 解答を見た

まず、上の桁から順に求めていこうとしたが、判定条件が思った以上に難しかった。(ここで下の桁から順に求めていけば良いという発想の転換がなかった)
nが0の場合分けを忘れてしまっていた。(全ての場合を尽くせているかを確認する(極端な場合を考える))

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)

10WA以上 解答を見た

木構造が苦手すぎる、本当に克服したい。
答えをみるまでわからず、Pythonではうまく書けなかった。
Pythonは再帰と相性が悪いようなので、C++で再帰は書こうと思う。
コードの説明はコメントアウトを参照。

C++の解答
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<utility>

using namespace std;

int main(){
  int n,q;cin >> n >> q;
  //uにはインデックスに対応した頂点と繋がっている頂点を保存している(入力の時点ではどちらが親かわからないので)
  vector< vector<int> > u(n);
  for(int i=0;i<n-1;i++){
    int a,b;cin >> a >> b;
    //二回push_backする必要があることに注意
    u[a-1].push_back(b-1);
    u[b-1].push_back(a-1);
  }
  //cはそれぞれの頂点のカウンタの値を保持する
  vector<int> c(n,0);
  for(int i=0;i<q;i++){
    //一旦カウンタの初期値を保持しておいて根に近いとこから順に子へと伝播させていく 
    int p,x;cin >> p >> x;
  c[p-1]+=x;
  }
  //幅優先探索で次に見たいNodeの情報を入れておく
  //この際に、その頂点の情報だけでなく一つ前の頂点の情報も必要になる(逆伝播を防ぐ)
  //vectorでもいいが削除などが遅いのでqueueを使う
  queue< pair<int,int> > k;k.push(make_pair(-1,0));

  //幅優先探索(深さ優先探索でもOK)
  while(k.size()!=0){//探索できる頂点がなくなったら終了
    int l1=k.size();
    for(int i=0;i<l1;i++){
      pair<int,int> a=k.front();
      int l2=u[a.second].size();
      //それぞれの頂点から伸びる頂点を調べていく
      for(int j=0;j<l2;j++){
        //その頂点から伸びる頂点が訪問していないものであれば(子の方向に探索が進んでいれば)、その頂点へとカウンタの値を足す
        if(u[a.second][j]!=a.first){
          c[u[a.second][j]]+=c[a.second];
          #次の頂点へと探索を続ける
          k.push(make_pair(a.second,u[a.second][j]));
        }
      }
      #用済みなので削除する
      k.pop();
    }
  }

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


DaikiSuyama
PythonとC++で競技プログラミングをしています(highest:AtCoder:1413,Codeforces:1672)。 機械学習も少し勉強しています。 FXや株の自動売買、音楽の自動生成に興味があります。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away