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)); } }
はえ~すっごいシンプル………
ほげ
直前の社長ラジオで"教育的良問"の話があって(問題見てないって言ってたけど)