fal_rnd_log

fal_rnd

AtCoder Beginner Contest 070 /解説

ABCOnly回なので全完してこれを書いてるんですが、
「今回初めて全完できた!」という声を多く聞くと何かこっちも嬉しくなりますね(謎)

コンテストページ

abc071.contest.atcoder.jp (通常) https://beta.atcoder.jp/contests/abc070 (beta)

A - Palindromic Number

https://beta.atcoder.jp/contests/abc070/submissions/1504125

解説

“/10” やら “*10” やらで1桁づつひっくり返す
(追記:2017/08/16 16:45)どうやら数学的でもっとファビュラスな解法があるらしい

コード

import java.util.Scanner;
import java.util.stream.IntStream;
 
public class Main{
    static IntStream REPS(int v){return IntStream.range(0,v);}
    static IntStream REPS(int l,int r){return IntStream.rangeClosed(l,r);}
    static IntStream INS(int n) {return REPS(n).map(i->getInt());}
    static Scanner s=new Scanner(System.in);
    static int getInt(){return Integer.parseInt(s.next());}
    public static void main(String[]$){
        int n=getInt(),cn=n;
        int rn=0;
        while(cn!=0) {
            rn*=10;
            rn+=cn%10;
            cn/=10;
        }
        System.out.println(rn==n?"Yes":"No");
    }
}

B - Two Switches

https://beta.atcoder.jp/contests/abc070/submissions/1504604

解説

多分数字とifでゴニョるのが想定解なのでしょうが
めんdので累積和しました(は?

コード

import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.IntStream;
 
public class Main{
    static IntStream REPS(int v){return IntStream.range(0,v);}
    static IntStream REPS(int l,int r){return IntStream.rangeClosed(l,r);}
    static IntStream INS(int n) {return REPS(n).map(i->getInt());}
    static Scanner s=new Scanner(System.in);
    static int getInt(){return Integer.parseInt(s.next());}
    public static void main(String[]$){
        int[]a=new int[114];
        ++a[getInt()];
        --a[getInt()];
        ++a[getInt()];
        --a[getInt()];
        Arrays.parallelPrefix(a,Integer::sum);
        System.out.println(Arrays.stream(a).filter(i->i==2).count());
    }
}

C - Multiple Clocks

解説

Ratedな皆さんとしてはここからが勝負ですね
周期系なので最小公倍数

コード

https://beta.atcoder.jp/contests/abc070/tasks/abc070_c

import java.util.Scanner;
import java.util.stream.IntStream;
 
public class Main{
    static IntStream REPS(int v){return IntStream.range(0,v);}
    static IntStream REPS(int l,int r){return IntStream.rangeClosed(l,r);}
    static IntStream INS(int n) {return REPS(n).map(i->getInt());}
    static Scanner s=new Scanner(System.in);
    static int getInt(){return Integer.parseInt(s.next());}
    public static void main(String[]$){
        int n=getInt();
        long l=1;
        for(int i=0;i<n;++i) {
            l=lcm(l,s.nextLong());
        }
        System.out.println(l);
    }
    public static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    public static long lcm(long a, long b) {
        return a/gcd(a,b)*b;
    }
}

D - Transit Tree Path

https://beta.atcoder.jp/contests/abc070/tasks/abc070_d

解説

Kを始点にダイクストって距離を出す
(初めてダイクストラ書いたんですがどうにかなるもんですね(1WA))

(追記:2017/8/12 23:??)なんかdfsでいけるらしいっすよ(適当)

コード

dijkstra

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.stream.IntStream;
 
public class Main{
    static IntStream REPS(int v){return IntStream.range(0,v);}
    static IntStream REPS(int l,int r){return IntStream.rangeClosed(l,r);}
    static IntStream INS(int n) {return REPS(n).map(i->getInt());}
    static Scanner s=new Scanner(System.in);
    static int getInt(){return Integer.parseInt(s.next());}
    public static void main(String[]$){
        int n=getInt();
 
        ArrayList<ArrayList<Edge>>edges=new ArrayList<>();
        for(int i=0;i<n;++i)edges.add(new ArrayList<>());
        for(int i=0;i<n-1;++i){
            int a=getInt()-1,b=getInt()-1,c=getInt();
            edges.get(a).add(new Edge(a,b,c));
            edges.get(b).add(new Edge(b,a,c));
        }
        int q=getInt(),k=getInt()-1;
        long[]dist=new long[n];
        {
            PriorityQueue<Edge>p=new PriorityQueue<>(edges.get(k));
            Arrays.fill(dist,Integer.MAX_VALUE);
            dist[k]=0;
 
            int filled=1;
            while(filled!=n){
                Edge poll=p.poll();
                if(dist[poll.t]==Integer.MAX_VALUE) {
                    dist[poll.t]=dist[poll.f]+poll.c;
                    p.addAll(edges.get(poll.t));
                    ++filled;
                }
            }
        }
        for(int i=0;i<q;++i)
            System.out.println(dist[getInt()-1]+dist[getInt()-1]);
    }
    static class Edge implements Comparable<Edge>{
        int f,t;long c;
        public Edge(int from,int to,int cost){f=from;t=to;c=cost;}
        @Override
        public String toString(){return "("+f+","+t+")="+c;}
        @Override
        public int compareTo(Edge o){
            long v=c-o.c;
            return v==0?0:v>0?1:-1;
        }
        @Override
        public int hashCode(){
            final int prime=31;
            int result=prime+(int)(c^(c>>>32));
            result=prime*result+f;
            result=prime*result+t;
            return result;
        }
        @Override
        public boolean equals(Object obj){
            if(this==obj) return true;
            if(obj==null||getClass()!=obj.getClass()) return false;
            Edge other=(Edge)obj;
            if(c!=other.c||f!=other.f||t!=other.t) return false;
            return true;
        }
    }
}

dfs解

(追記:2017/08/13 17:48)やってみました

import java.util.*;
class Main{
    static Scanner s=new Scanner(System.in);
    static int getInt(){return Integer.parseInt(s.next());}
    public static void main(String[]$){
        int n=getInt();
        dist=new long[n];
        for(int i=0;i<n;++i)
            edges.add(new TreeMap<>());
        for(int i=0;i<n-1;++i){
            int a=getInt()-1,b=getInt()-1;
            long c=getInt();
            edges.get(a).put(b,c);
            edges.get(b).put(a,c);
        }
        int q=getInt();
        dfs(-1,getInt()-1,0);
        for(int i=0;i<q;++i)
            System.out.println(dist[getInt()-1]+dist[getInt()-1]);
    }
    static ArrayList<TreeMap<Integer,Long>>edges=new ArrayList<>();
    static long[]dist;
    static void dfs(int from,int to,long l){
        dist[to]=l;
        TreeMap<Integer,Long> m=edges.get(to);
        m.remove(from);
        m.forEach((k,v)->dfs(to,k,l+v));
    }
}

はえ~すっごいシンプル………

ほげ

直前の社長ラジオで"教育的良問"の話があって(問題見てないって言ってたけど)