AOJ1001とか
解法思いついたけど提出してみたらWA…と思ったらバグがあっただけでした。
久しぶりに閃いたのでとりあえず書いただけ。
ちなみにこの問題、閃いたのはこの顔文字のおかげ→('ω')
import java.io.IOException; import java.io.StringReader; import java.util.Scanner; public class Main { static final Scanner s = new Scanner(System.in); public static void main(String[] args) { while(s.hasNextLine()) { String[] str = s.nextLine().split(" "); if(str[0].charAt(0)=='i') System.out.println(BinaryTree.intersection(BinaryTree.parse(str[1]), BinaryTree.parse(str[2]))); else if(str[0].charAt(0)=='u') System.out.println(BinaryTree.union(BinaryTree.parse(str[1]), BinaryTree.parse(str[2]))); } } } class BinaryTree { public static Node parse(String str) { try { StringReader r = new StringReader(str); r.read(); Node root = new Node(); Node current = root; while(true) { int ch = r.read(); if(ch==-1) break; if(ch=='(') { current = current.setLeft(new Node()); } else if(ch==')') { current = current.parent; } else if(ch==',') { int next = r.read(); if(next=='(') { current = current.setRight(new Node()); } else if(next==')') { current = current.parent; } else throw new IllegalArgumentException(); } else throw new IllegalArgumentException(); } return root; } catch(IOException e) { throw new InternalError(); } } public static Node copy(Node a) { Node copy = new Node(); copy0(a, copy); return copy; } private static void copy0(Node a, Node current) { if(a.left!=null) copy0(a.left, current.setLeft(new Node())); if(a.right!=null) copy0(a.right, current.setRight(new Node())); } public static Node intersection(Node a, Node b) { Node intersection = new Node(); intersection0(a, b, intersection); return intersection; } private static void intersection0(Node a, Node b, Node current) { if(a.left!=null && b.left!=null) intersection0(a.left, b.left, current.setLeft(new Node())); if(a.right!=null && b.right!=null) intersection0(a.right, b.right, current.setRight(new Node())); } public static Node union(Node a, Node b) { Node union = new Node(); union0(a, b, union); return union; } private static void union0(Node a, Node b, Node current) { if(a.left!=null && b.left!=null) union0(a.left, b.left, current.setLeft(new Node())); else if(a.left!=null) current.left = copy(a.left); else if(b.left!=null) current.left = copy(b.left); if(a.right!=null && b.right!=null) union0(a.right, b.right, current.setRight(new Node())); else if(a.right!=null) current.right = copy(a.right); else if(b.right!=null) current.right = copy(b.right); } public static class Node { private Node parent, left, right; public Node setLeft(Node left) { this.left = left; left.parent = this; return left; } public Node setRight(Node right) { this.right = right; right.parent = this; return right; } @Override public String toString() { return '(' + (left==null ? "" : left.toString()) + ',' + (right==null ? "" : right.toString()) + ')'; } } }
オブジェクト指向なんてなかったよ
無駄が多すぎるけどまぁ仕方ない