AOJ1221 Numoeba

問題リンク Numoeba

• 概要

ヌメーバと呼ばれる、細胞が木構造の生物がいる。木の根になっている細胞をリーダーと呼ぶ。
木は単位時間毎に構造を変え、リーダーもそれに合わせて変わる。
ヌメーバの各細胞はnumbosomeと呼ばれる奇数の整数値(1〜12345677)を持つ。単位時間で、nだったnumbosomeは3n+1の最大の奇数の約数になる。その結果が12345677を超えていた場合、12345678を引く。
全ての細胞について、次のnumbosomeを計算した後、次のようにして木構造が変化する。

1. 葉細胞であり、新たなnumbosomeの値が直前の値より真に大きい場合その細胞をcandidate leafと呼ぶ。
numbosomeが1になった細胞は死ぬ。リーダーが死んだ場合、ヌメーバが死ぬ。リーダーで無い場合、この細胞のsub tree全体が死ぬ。ただ、1つだけ例外があり、この細胞がリーダーでなく、子供がただ1つだった場合、sub treeが死ぬことは無く、この細胞の親細胞に直接子供細胞を繋げる。この処理は木の親から子へsequentialに処理されるものとする。

2. candidate leafが生き残った場合、leaf bonusが発生する。leaf bonusは、candedate leafから子供細胞が1つ生成される。その細胞の値は、candidate leafの値nの(n+1)/2以上の最小の奇数である。

3. 新しい木構造のリーダーを選択する。リーダーはnumbosomeが最大でユニークな細胞になる。この細胞が新たなリーダーになり、木の根となる（新たなリーダーと前のリーダーは同じになるかもしれない）。親と子の関係がひっくり返る細胞があるならばひっくり返す。このリーダーはleader bonusが発生する。リーダーに新たな子細胞を追加する。細胞の値は、リーダーの値nの(n+1)/2以下の最大の奇数である。
numbosomeが最大のものが複数あった場合、リーダーは変化せず、leader bonusも発生しない。

時刻0のとき、値がKのただ1つの細胞からなるヌメーバがいる。このヌメーバが死滅するまでいくらかかるか調べよ。更に、ヌメーバの細胞数が最大でいくつになるかも調べよ。
入力で与えられたヌメーバは、時刻500までに死ぬことが保証されている。更に、ヌメーバの生命時間中に生成される細胞数は5000を超えないことも保証されている。
3 <= K <= 9999

• 解法

シミュレーションです。
木構造の変化の処理は、問題文の通りになるように注意して実装しました。親と子の関係がひっくり返るところとかは慎重にやる必要があります。

• ソース

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

//Numoeba
public class AOJ1221 {
	
	class R{
		int id, val, pre;
		R parent;
		Set<R> child, copy;
		boolean candidateLeaf;
		public R(int id, int val, R parent) {
			this.id = id;
			pre = this.val = val;
			this.parent = parent;
			child = new HashSet<R>();
			copy = new HashSet<R>();
		}
		void nextVal(){
			pre = val;
			val = 3*val+1;
			while((val&1)==0)val>>=1;
			val%=L;
			candidateLeaf = child.isEmpty() && pre < val;
			for(R r:child)r.nextVal();
		}
		void shrink(){
			if(val==1){
				parent.child.remove(this);
				if(child.size()==1){
					R r = null;
					for(R t:child)r=t;
					r.parent = parent;
					parent.child.add(r);
					r.shrink();
				}
				return;
			}
			copy.clear();
			copy.addAll(child);
			for(R r:copy)r.shrink();
			if(candidateLeaf){
				int k = (val+1)>>1;
				if((k&1)==0)k++;
				child.add(new R(ID++, k, this));
			}
		}
		void findLeader(){
			cnt++;
			if(max < val){
				next = this;
				max = val;
				c = 1;
			}
			else if(max==val)c++;
			for(R r:child)r.findLeader();
		}
		void rev(R p){
			child.remove(p);
			if(parent==null){
				parent = p;
				return;
			}
			parent.rev(this);
			child.add(parent);
			parent = p;
		}
		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + getOuterType().hashCode();
			result = prime * result + id;
			return result;
		}
		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			R other = (R) obj;
			if (!getOuterType().equals(other.getOuterType()))
				return false;
			if (id != other.id)
				return false;
			return true;
		}
		private AOJ1221 getOuterType() {
			return AOJ1221.this;
		}
		
	}
	
	int cnt, max, c, ID, L = 12345678;
	R next;
	
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int n = sc.nextInt();
			if(n==0)break;
			ID = 0;
			R root = new R(ID++, n, null);
			int res = 1, T = 1;
			for(;;T++){
				root.nextVal();
				if(root.val==1)break;
				root.shrink();
				cnt = max = c = 0;
				next = null;
				root.findLeader();
				if(c==1){
					int k = (next.val+1)>>1;
					if((k&1)==0)k--;
					if(1<k){
						cnt++;
						next.child.add(new R(ID++, k, next));
					}
					root = next;
					if(root.parent!=null){
						root.parent.rev(root);
						root.child.add(root.parent);
						root.parent = null;
					}
				}
				res = Math.max(res, cnt);
			}
			System.out.println(T+" "+res);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1221().run();
	}
}