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

AtCoder Beginner Contest 070 過去問復習

以前に解いたことのある過去問、二回目

所要時間

スクリーンショット 2019-12-24 12.51.02.png

A問題

最初と最後が同じかどうか判定すればいい(文字列でそのまま扱う)

answerA.py
n=input()
if n[0]==n[-1]:
    print("Yes")
else:
    print("No")

B問題

aとcのmaxからbとdのminの間にあるのが共通部分(二人が押していた時間)なので、それが存在するかどうかで場合分けして存在する場合はその時間を求めれば良い。

answerB.py
a,b,c,d=map(int,input().split())
k,l=max(a,c),min(b,d)

if k>=l:
    print(0)
else:
    print(l-k)

C問題

二秒でわかる最小公倍数の問題、前回解いたときはPythonで解いたけど、今回はC++で解いた。Pythonはgcd関数を使ってlcm出せばいいだけだが、C++はそういうわけにはいかなった。(一応、gcdもlcmもC++で実装してライブラリ化してる)
まず、問題の制約でintに収まりきらないのでlong longを使わなければならない(long longはいつもllにしてる)。さらに、lcmのところでlong longの範囲を超える可能性のある掛け算をしていたので、先に割り算を行ってから掛け算をした。

answerC.cc
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;

//whileで小さくしてく
ll gcd(ll x,ll y){
  if(x<y) swap(x,y);
  //xの方が常に大きい
  while(y>0){
    ll r=x%y;
    x=y;
    y=r;
  }
  return x;
}

ll lcm(ll x,ll y){
  //かけるで大きくなりすぎる
  return ll(x/gcd(x,y))*y;
  //元はll(x*y/gcd(x,y));にしていた
}

int main(){
  ll n;cin >> n;
  ll ans=1;
  for(int i=0;i<n;i++){
    //cout << ans << endl;
    ll t;cin >> t;
    ans=lcm(ans,t);
  }
  cout << ans << endl;
}
answerC.py
import fractions
n=int(input())
t=[int(input()) for i in range(n)]

if n==1:
    print(t[0])
else:
    x=t[0]*t[1]//fractions.gcd(t[0],t[1])
    for i in range(1,n-1):
        x=x*t[i+1]//fractions.gcd(x,t[i+1])
    print(x)

D問題

木構造はC++でやると決めている(計算量の見積もりがわかりにくくPythonだとうまくできない事が多いので)。
一つ目のコードは以前解いた時のコードで、二つ目のコードは今回解いた時のコードです。一回目に解いた時は、工夫をしようと考えすぎて時間を食ったが、結局距離を知りたいのが明らかなので木であることを考慮すると普通に深さ優先探索や幅優先探索をすればいいとわかる。(木構造での探索問題の抽象化に失敗する事が多いなといつも思う。)
ここでは深さ優先探索を選んだ(理由はない)、それぞれのNodeから伸びる辺の情報を保持するtree、kからの最短経路を保持するtree_len、visitしたかどうかを保持するcheckの三つを用意すれば、普通の深さ優先探索をする事でkからの最短経路がそれぞれ求められる。求めたらそれぞれの質問クエリでk→xでの最短経路の長さとk→yでの最短経路の長さを足し合わせれば答えになる。(深さ優先探索のコードはライブラリ化せずに速攻書けるようにしたい。ポイントは、今いるNodeの情報を書き換えるというのを徹底するということと、そこから繋がるNodeを再帰で呼び出すときに訪問済みかどうか確認するコードを書き忘れないこと。)
また、この問題でもintでオーバーフローするのでlong longにする必要がある。さらに、木なのでn-1本しか辺がないのにn本だと思って入力を受け取ろうとし入力待機状態になるミスもした。

answerD.cc
#include<iostream>
#include<vector>
#include<utility>
using namespace std;

class Node{
public:
  vector< pair<int,int> > v;
  long long dist;
  bool check=false;
};

void depth_search(vector<Node>& V,int k,long long d){
  V[k].dist=d;
  V[k].check=true;
  int l=V[k].v.size();
  for(int i=0;i<l;i++){
    if(V[V[k].v[i].first].check==false){
      depth_search(V,V[k].v[i].first,V[k].v[i].second+d);
    }
  }
}

int main(){
  int n;cin >> n;
  vector<Node> V(n);
  for(int i=0;i<n-1;i++){
    int a,b,c;cin >> a >> b >> c;
    V[a-1].v.push_back(make_pair(b-1,c));
    V[b-1].v.push_back(make_pair(a-1,c));
  }
  int q,k;cin >> q >> k;k-=1;
  depth_search(V,k,0);
  vector<long long> Q(q);
  int x,y;
  for(int i=0;i<q;i++){
    cin >> x >> y;
    Q[i]=V[x-1].dist+V[y-1].dist;
  }
  for(int i=0;i<q;i++){
    cout << Q[i] << endl;
  }
}

answerD.cc
#include<iostream>
#include<vector>
#include<utility>
using namespace std;
typedef long long ll;
typedef vector< vector< pair<long long,long long> > > vvp;

//Nodeクラス作らない方がスマート、これ早く書けるように
void dfs(vvp& tree,vector<ll>& tree_len,vector<bool>& check,ll dep,ll now){
  tree_len[now]=dep;
  check[now]=true;
  ll l=tree[now].size();
  for(int i=0;i<l;i++){
    if(check[tree[now][i].first]==false) dfs(tree,tree_len,check,dep+tree[now][i].second,tree[now][i].first);
  }
}

int main(){
  ll n;cin >> n;
  vvp tree(n);//Nodeから伸びる辺の情報
  vector<ll> tree_len(n,0);//最短経路保持
  vector<bool> check(n,false);//辿ったかどうか
  //nにして入力終わらねえってなった
  for(int i=0;i<n-1;i++){
    ll a,b,c;cin >> a >> b >> c;
    tree[a-1].push_back(make_pair(b-1,c));
    tree[b-1].push_back(make_pair(a-1,c));
  }
  ll q,k;cin >> q >> k;
  dfs(tree,tree_len,check,0,k-1);
  for(int i=0;i<q;i++){
    ll x,y;cin >> x >> y;
    cout << tree_len[x-1]+tree_len[y-1] << endl;
  }
}
DaikiSuyama
PythonとC++で競技プログラミングをしています(highest:AtCoder:1334,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
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  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
ユーザーは見つかりませんでした