UVa 13039 : Fibonacci Triangle

問題リンク :
https://uva.onlinejudge.org/external/130/13039.pdf

問題概要 :
1番目のフィボナッチ数を2, 2番目のフィボナッチ数を３とする
i番目のフィボナッチ数と同じ長さの線分がそれぞれa[i]個存在する
これらの線分を使って作れる三角形の本数の最大値を求めよ

解法 :
これもlaycrsさんの解説をみて解いた

三角形のうち一番長い線分の長さをF、Fの１つ前のフィボナッチ数の長さをF1とする
この時に考えられる三角形の構成は次のとおり

1. F が３本
2. F が２本 + なんでも良いので１本
3. F が１本 + F1が２本

短い線分から順番に三角形を作っていくことを考えたとき、
最大の辺の長さより前のものをできる限り消費したいので、
3,2,1の順番で三角形を作っていくとよい

コード:

nclude<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;

int main() {
  int T;
  cin >> T;
  while( T-- ) {
    int n;
    cin >> n;
    vector<ll> vec(n);
    rep(i,n) cin >> vec[i];
    ll sum = 0, prev = 0;
    rep(i,n) {
      while( i-1 >= 0 && vec[i] && vec[i-1] >= 2LL ) {
        vec[i-1] -= 2LL, prev -= 2LL, --vec[i];
        ++sum;
      }
      while( prev && vec[i] >= 2LL ) {
        vec[i] -= 2LL, --prev;
        ++sum;
      }
      while( vec[i] >= 3LL ) {
        vec[i] -= 3LL;
        ++sum;
      }
      prev += vec[i];
    }
    cout << sum << endl;
  }
  return 0;
}

UVa 13036 : Birthday Gift to SJ - 2

問題リンク :
https://uva.onlinejudge.org/external/130/13036.pdf

問題概要 :
フィボナッチ数の積として表されるような数で、a以上b以下のものの最大値を求めよ

解法 :
laycrsさんの解説を読んで解いた
フィボナッチ数のうち2から89までを前半、それ以降を後半として列挙する
前半のフィボナッチ数を入れた配列をX、後半のフィボナッチ数を入れた配列をYとする
Xの各要素について、b/X[i]となるようなYの最大値を求める

これでも結構時間がかかるので、
素因数分解した時に、全て他のフィボナッチ数で表されるようなものは配列から除外した(8と144だけかな

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;
const ll MAX = 1000000000000000000LL;

vector<ll> sasami_san_kawaii(vector<ll> vec) {
  vector<ll> S;
  S.push_back(1);
  rep(i,(int)vec.size()) {
    ll coef = vec[i];
    vector<ll> tmp = S;
    tmp.push_back(coef);
    rep(j,(int)S.size()) {
      ll v = S[j];
      while( v <= v * coef && v * coef <= MAX ) {
        v *= coef;
        tmp.push_back(v);
      }
    }
    S = tmp;
  }
  S.erase(S.begin());
  sort(S.begin(),S.end());
  S.erase(unique(S.begin(),S.end()),S.end());
  return S;
}


int main() {

  vector<ll> X,Y;
  {
    vector<ll> fib1,fib2;
    fib1.push_back(2);
    fib1.push_back(3);
    fib1.push_back(5);
    fib1.push_back(13);
    fib1.push_back(21);
    fib1.push_back(34);
    fib1.push_back(55);
    fib1.push_back(89);

    fib2.push_back(233);
    fib2.push_back(377);
    while( 1 ) {
      int size = (int)fib2.size()-1;
      ll tmp = fib2[size] + fib2[size-1];
      if( tmp > MAX || tmp < 0 ) break;
      fib2.push_back(tmp);
    }
    X = sasami_san_kawaii(fib1);
    Y = sasami_san_kawaii(fib2);
  }
  int T;
  cin >> T;
  while( T-- ) {
    ll a,b;
    cin >> a >> b;
    ll maxi = -1LL;
    rep(i,(int)Y.size()) {
      if( Y[i] < a ) continue;
      if( Y[i] > b ) break;
      maxi = max(maxi,Y[i]);
      if( maxi == b ) break;
    }
    rep(i,(int)X.size()) {
      if( X[i] < a ) continue;
      if( X[i] > b ) break;
      maxi = max(maxi,X[i]);
      if( maxi == b ) break;
    }
    
    rep(i,(int)X.size()) {
      if( X[i] > b ) break;
      if( a <= X[i] && X[i] <= b ) maxi = max(maxi,X[i]);
      if( maxi == b ) break;
      ll v = b / X[i];
      if( v < 233LL ) continue;
      
      int pos = lower_bound(Y.begin(),Y.end(),v) - Y.begin();
      if( 0 <= pos && pos < (int)Y.size() && Y[pos] > v ) --pos;
      if( pos < 0 || (int)Y.size() <= pos ) continue;
      maxi = max(maxi,X[i] * Y[pos]);
    }
    cout << maxi << endl;
  }
  return 0;
}

Typical DP Contest F : 準急

問題リンク：

F: 準急 - Typical DP Contest | AtCoder

解法：
dp[i] := i番目の駅に停まらない数 = dp[max(0,i-K)] + ... + dp[i-1]
初期値は dp[0] = 1, dp[1] = 0
また、dp[N] = 0
dp[1]=dp[N]=0は、必ずその駅にとまることを意味する
dp[i]は
max(0,i-K)駅では停車せず、開区間(max(0,i-K),i)の各駅で停車する総数と
....
(i-2)駅では停車せず、(i-1)駅で停車する総数と
閉区間[max(0,i-K),i]のどの駅にも停車しない総数の和として表される
愚直に数えると間に合わないのでdpの総和を持っておく

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;
const ll mod = 1000000007LL;
const int MAX = 1000010;
ll dp[MAX];
int N,K;

int main() {
dp[0] = 1;
dp[1] = 0;
cin >> N >> K;
/*-- debug
REP(i,2,N+2) {
if( i == N ) { dp[i] = 0; continue; }
for(int j=max(0,i-K);j<i;j++) {
( dp[i] += dp[j] ) %= mod;
}
}
cout << dp[N+1] << endl;
debug -- */

ll sum = 1;
REP(i,2,N+2) {
if( i == N ) {
dp[i] = 0;
} else {
dp[i] = sum;
( sum += dp[i] ) %= mod;
}
if( i - K >= 0 ) { sum -= dp[i-K]; while( sum < 0LL ) sum += mod; }
}
cout << dp[N+1] << endl;
return 0;
}

Typical DP Contest E : 数

問題リンク : E: 数 - Typical DP Contest | AtCoder

解法 :
桁DP
dp[桁][余り][現在の桁までがNのこの桁までと一致しているか] := 総数

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;

const ll mod = 1000000007LL;
ll D,dp[10010][110][2]; // dp[桁][余り][Nとぴったりか] := 総数
string N;

void compute() {
  reverse(N.begin(),N.end());
  dp[(int)N.size()][0][1] = 1LL;
  for(int i=(int)N.size();i>=1;i--) {
    for(ll remain=0;remain<D;remain++) {
        rep(sameN,2) {
          rep(digit,10) {
            ll new_remain = (remain + (ll)digit) % D;
            if( sameN && digit > ( N[i-1] - '0' ) ) continue;
            int new_sameN = sameN;
            if( sameN && digit < ( N[i-1] - '0' ) ) new_sameN = 0;
            ( dp[i-1][new_remain][new_sameN] += dp[i][remain][sameN] ) %= mod;
          }
      }
    }
  }
  cout << ( dp[0][0][0] + dp[0][0][1] -1LL + mod ) % mod << endl;
}

int main() {
  cin >> D >> N;
  compute();
  return 0;
}

AOJ 2607 : Invest Master

問題リンク : Invest Master | Aizu Online Judge

問題概要：
n日間の株価の情報が与えられる
初日にx円所持しているので、株の売買を行い最終日の所持金を最大化せよ
株の売買に手数料はかからないものとする
また、最終日の所持金の最大値は高々１０＾５である

解法：
動的計画法
最終日の所持金の最大値は高々１０＾５なので途中にその金額より大きくなることはない
また、株の売買に手数料はかからないため、その日に買った株をその日に売っても損しない
このことから、一日ごとの所持金の最大化をすればよい
dp[i] := 現在i円持っているときの翌日の所持金の最大値

コード：

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

int n,d,x,p[11][11],dp[100010];//??


int main() {
  cin >> n >> d >> x;
  rep(i,d) rep(j,n) cin >> p[i][j];
  int maxi = x;
  rep(day,d-1) {
    memset(dp,0,sizeof(dp));
    rep(i,maxi+1) dp[i] = i;
    int tmp = maxi;
    rep(i,n) {
      REP(j,p[day][i],maxi+1) {
        dp[j] = max(dp[j],dp[j-p[day][i]]+p[day+1][i]);
        tmp = max(tmp,dp[j]);
      }
    }
    maxi = tmp;
  }
  cout << maxi << endl;
  return 0;
}

SEERC 2015 A : Equivalence

問題リンク : https://icpcarchive.ecs.baylor.edu/external/71/7173.pdf

問題概要　：
２つの論理式が与えられる
それらが等価か判定せよ

論理式は論理変数、論理和、論理積、否定から構成される
論理演算の優先度は気にしなくても良い（適切に括弧がつけられている）
論理式に含まれる論理変数は高々５１個

解法：
BDDで解いた
最悪ケースが大丈夫なのか謎ではあったが、、
BDD自体は北大の授業のスライドを参考に作成
codeforcesのGYMで他の人のコードを見たら皆乱数で適当に変数に値を割り当てて評価し、適当な回数だけ繰り返し評価を行い全て一致するかどうかで判定していた
LiveArchiveはまだジャッジが用意されていないようなのでジャッジ待ち

コード:

import java.io.*;
import java.util.*;


class BinaryOperatorMemoState implements Comparable<BinaryOperatorMemoState> {
	public char op;
	public int F, G;

	public BinaryOperatorMemoState() {

	}

	public BinaryOperatorMemoState(char op, int F, int G) {
		this.op = op;
		this.F = F;
		this.G = G;
	}

	@Override
	public int compareTo(BinaryOperatorMemoState o) {
		int result = new Character(this.op).compareTo(o.op);
		if (result == 0) {
			result = new Integer(this.F).compareTo(o.F);
			if (result == 0) {
				result = new Integer(this.G).compareTo(o.G);
			}
		}
		return result;
	}
}

class BooleanExpression {
	public BooleanExpression deepCopy() {
		System.out.println("WARNING");
		return this.deepCopy();
	}

	public BooleanExpression assignBooleanValueToLogicVariable(boolean booleanValue, LogicVariable logicVariable) {
		System.out.println("WARNING");
		return this.assignBooleanValueToLogicVariable(booleanValue, logicVariable);
	}

	public int traverse() {
		System.out.println("WARNING");
		return -1;
	}

	public boolean eval(HashSet<State> F, HashSet<State> L) {
		System.out.println("WARNING");
		return false;
	}

	public BooleanExpression recoverPredicate() {
		System.out.println("WARNING");
		return this.recoverPredicate();
	}

}


class And extends BooleanExpression {
	public BooleanExpression left, right;

	public And() {

	}

	public And(BooleanExpression left, BooleanExpression right) {
		this.left = left;
		this.right = right;
	}

	@Override
	public int traverse() {
		int F = this.left.traverse();
		int G = this.right.traverse();
		return BDD.apply('&', F, G);
	}

	@Override
	public And deepCopy() {
		return new And(left.deepCopy(), right.deepCopy());
	}

	@Override
	public And recoverPredicate() {
		return new And(left.recoverPredicate(), right.recoverPredicate());
	}

	@Override
	public BooleanExpression assignBooleanValueToLogicVariable(boolean booleanValue, LogicVariable logicVariable) {
		BooleanExpression tmp_left = left.assignBooleanValueToLogicVariable(booleanValue, logicVariable);
		BooleanExpression tmp_right = right.assignBooleanValueToLogicVariable(booleanValue, logicVariable);
		if ((tmp_left instanceof LogicVariable) && (tmp_right instanceof LogicVariable)) {
			boolean leftHasValue = ((LogicVariable) tmp_left).hasValue();
			boolean rightHasValue = ((LogicVariable) tmp_right).hasValue();
			if (leftHasValue && rightHasValue) {
				return new LogicVariable(-1, ((LogicVariable) tmp_left).getValue() && ((LogicVariable) tmp_right).getValue());
			} else if (leftHasValue) {
				if (!((LogicVariable) tmp_left).getValue()) {
					return new LogicVariable(-1, false);
				} else {
					return tmp_right;
				}
			} else if (rightHasValue) {
				if (!((LogicVariable) tmp_right).getValue()) {
					return new LogicVariable(-1, false);
				} else {
					return tmp_left;
				}
			} else {
				return new And(tmp_left, tmp_right);
			}
		} else if (tmp_left instanceof LogicVariable) {
			if (((LogicVariable) tmp_left).hasValue()) {
				if (!((LogicVariable) tmp_left).getValue()) {
					return new LogicVariable(-1, false);
				} else {
					return tmp_right;
				}
			} else {
				return new And(tmp_left, tmp_right);
			}
		} else if (tmp_right instanceof LogicVariable) {
			if (((LogicVariable) tmp_right).hasValue()) {
				if (!((LogicVariable) tmp_right).getValue()) {
					return new LogicVariable(-1, false);
				} else {
					return tmp_left;
				}
			} else {
				return new And(tmp_left, tmp_right);
			}
		} else {
			return new And(tmp_left, tmp_right);
		}
	}

	@Override
	public boolean eval(HashSet<State> F, HashSet<State> L) {
		return left.eval(F, L) && right.eval(F, L);
	}

	@Override
	public String toString() {
		return "(" + left + "&" + right + ")";
	}

}

class LogicVariable extends BooleanExpression {
	int ID;
	byte value;

	public LogicVariable() {
		this.value = -1;
	}

	public LogicVariable(int ID) {
		this.ID = ID;
		this.value = -1;
	}

	public LogicVariable(int ID, byte value) {
		this.ID = ID;
		this.value = value;
	}

	public LogicVariable(int ID, boolean value) {
		this.ID = ID;
		this.value = (byte) ((value == true) ? 1 : 0);
	}

	@Override
	public int traverse() {
		if (this.hasValue()) {
			return this.getValue() ? 1 : 0;
		}
		return BDD.getNode(new BDDNode(this.ID, 0, 1));
	}

	@Override
	public LogicVariable deepCopy() {
		return new LogicVariable(ID, value);
	}

	@Override
	public LogicVariable recoverPredicate() {
		return new LogicVariable(((ID < 0) ? -ID : ID), value);
	}

	@Override
	public BooleanExpression assignBooleanValueToLogicVariable(boolean booleanValue, LogicVariable logicVariable) {
		if (ID == logicVariable.getID()) {
			return new LogicVariable(-1, booleanValue);
		}
		return this.deepCopy();
	}

	public boolean hasValue() {
		return this.value != -1;
	}

	public boolean getValue() {
		return this.value == 1;
	}

	public boolean isFalse() {
		return this.hasValue() && !getValue();
	}

	public boolean isTrue() {
		return this.hasValue() && getValue();
	}

	public void setValue(boolean value) {
		this.value = (byte) (value ? 1 : 0);
	}

	public void reverseValue() {
		if (this.value != -1) {
			this.value = (byte) ((this.value == 1) ? 0 : 1);
		}
	}

	public int getID() {
		return this.ID;
	}

	@Override
	public boolean eval(HashSet<State> F, HashSet<State> L) {
		if (ID == -1) {
			if (value == -1) {
				System.out.println("What is this Logic Variable");
			}
			if (value == 1) {
				return true;
			} else {
				return false;
			}
		}
		return F.contains(new State(ID)) || L.contains(new State(ID));
	}

	@Override
	public String toString() {
		if (ID == -1) {
			if (value == -1) {
				System.out.println("What is this Logic Variable");
			}
			if (value == 1) {
				return "true";
			} else {
				return "false";
			}
		}
		return String.valueOf(ID);
	}

}

class Not extends BooleanExpression {
	public BooleanExpression inner;

	public Not() {

	}

	public Not(BooleanExpression inner) {
		this.inner = inner;
	}

	@Override
	public int traverse() {
		int address = inner.traverse();
		return this.notApply(address);
	}

	public int notApply(int address) {
		if (address == 0 || address == 1) {
			return (address == 0) ? 1 : 0;
		}
		BDDNode bn = BDD.nodeTable[address];
		int H0 = notApply(bn.zeroID);
		int H1 = notApply(bn.oneID);
		return BDD.getNode(new BDDNode(bn.variableID, H0, H1));
	}

	@Override
	public Not deepCopy() {
		return new Not(inner.deepCopy());
	}

	@Override
	public Not recoverPredicate() {
		return new Not(inner.recoverPredicate());
	}

	@Override
	public BooleanExpression assignBooleanValueToLogicVariable(boolean booleanValue, LogicVariable logicVariable) {
		BooleanExpression tmp = inner.assignBooleanValueToLogicVariable(booleanValue, logicVariable);
		if (tmp instanceof LogicVariable) {
			if (((LogicVariable) tmp).hasValue()) {
				((LogicVariable) tmp).reverseValue();
				return tmp;
			}
		}
		return new Not(tmp);
	}

	@Override
	public boolean eval(HashSet<State> F, HashSet<State> L) {
		return !inner.eval(F, L);
	}

	@Override
	public String toString() {
		return "!(" + inner + ")";
	}
}

class Or extends BooleanExpression {
	public BooleanExpression left, right;

	public Or() {

	}

	public Or(BooleanExpression left, BooleanExpression right) {
		this.left = left;
		this.right = right;
	}

	@Override
	public int traverse() {
		int F = left.traverse();
		int G = right.traverse();
		return BDD.apply('|', F, G);
	}

	@Override
	public Or deepCopy() {
		return new Or(left.deepCopy(), right.deepCopy());
	}

	@Override
	public Or recoverPredicate() {
		return new Or(left.recoverPredicate(), right.recoverPredicate());
	}

	@Override
	public BooleanExpression assignBooleanValueToLogicVariable(boolean booleanValue, LogicVariable logicVariable) {
		BooleanExpression tmp_left = left.assignBooleanValueToLogicVariable(booleanValue, logicVariable);
		BooleanExpression tmp_right = right.assignBooleanValueToLogicVariable(booleanValue, logicVariable);
		if ((tmp_left instanceof LogicVariable) && (tmp_right instanceof LogicVariable)) {
			boolean leftHasValue = ((LogicVariable) tmp_left).hasValue();
			boolean rightHasValue = ((LogicVariable) tmp_right).hasValue();
			if (leftHasValue && rightHasValue) {
				return new LogicVariable(-1, ((LogicVariable) tmp_left).getValue() || ((LogicVariable) tmp_right).getValue());
			} else if (leftHasValue) {
				if (((LogicVariable) tmp_left).getValue()) {
					return new LogicVariable(-1, true);
				} else {
					return tmp_right;
				}
			} else if (rightHasValue) {
				if (((LogicVariable) tmp_right).getValue()) {
					return new LogicVariable(-1, true);
				} else {
					return tmp_left;
				}
			} else {
				return new Or(tmp_left, tmp_right);
			}
		} else if (tmp_left instanceof LogicVariable) {
			if (((LogicVariable) tmp_left).hasValue()) {
				if (((LogicVariable) tmp_left).getValue()) {
					return new LogicVariable(-1, true);
				} else {
					return tmp_right;
				}
			} else {
				return new Or(tmp_left, tmp_right);
			}
		} else if (tmp_right instanceof LogicVariable) {
			if (((LogicVariable) tmp_right).hasValue()) {
				if (((LogicVariable) tmp_right).getValue()) {
					return new LogicVariable(-1, true);
				} else {
					return tmp_left;
				}
			} else {
				return new Or(tmp_left, tmp_right);
			}
		} else {
			return new Or(tmp_left, tmp_right);
		}
	}

	@Override
	public boolean eval(HashSet<State> F, HashSet<State> L) {
		return left.eval(F, L) || right.eval(F, L);
	}

	@Override
	public String toString() {
		return "(" + left + "|" + right + ")";
	}
}

class BDDNode implements Comparable<BDDNode> {
	public int variableID, zeroID, oneID;

	public BDDNode() {
	}

	public BDDNode(int variableID, int zeroID, int oneID) {
		this.variableID = variableID;
		this.zeroID = zeroID;
		this.oneID = oneID;
	}

	public BDDNode deepCopy() {
		return new BDDNode(this.variableID, this.zeroID, this.oneID);
	}

	public boolean equals(BDDNode o) {
		return variableID == o.variableID && zeroID == o.zeroID && oneID == o.oneID;
	}

	@Override
	public int compareTo(BDDNode o) {
		int result = new Integer(this.variableID).compareTo(o.variableID);
		if (result == 0) {
			result = new Integer(this.zeroID).compareTo(o.zeroID);
			if (result == 0) {
				result = new Integer(this.oneID).compareTo(o.oneID);
			}
		}
		return result;
	}

	@Override
	public String toString() {
		return "(" + variableID + "," + zeroID + "," + oneID + ")";
	}
}

//Reference : http://www-erato.ist.hokudai.ac.jp/html/php/seminar5_docs/minato_alg2010-5.pdf
class BDD {
	public static int MAX_TABLE_SIZE = 10000000;
	private static int topOfNodeTable;
	public static BDDNode[] nodeTable = null; // 0番地は0定数節点,1番地は1定数節点
	public static TreeMap<BDDNode, Integer> nodeTableCache;
	public static TreeMap<BinaryOperatorMemoState, Integer> binaryOperatorCache;

	public int addressOfNodeTable;

	public BDD() {
		if (nodeTable == null) {
			nodeTable = new BDDNode[MAX_TABLE_SIZE];
			nodeTable[0] = new BDDNode(-1, -1, -1);
			nodeTable[1] = new BDDNode(-1, -1, -1);
			topOfNodeTable = 2;
			nodeTableCache = new TreeMap<BDDNode, Integer>();
			binaryOperatorCache = new TreeMap<BinaryOperatorMemoState, Integer>();
		}
	}

	public BDD(BooleanExpression be) {
		this();
		addressOfNodeTable = build(be);
	}

	public int build(BooleanExpression be) {
		return be.traverse();
	}

	public static int getNode(BDDNode bn) {
		if (bn.zeroID == bn.oneID) {
			return bn.zeroID;
		}

		if (nodeTableCache.containsKey(bn.deepCopy())) {
			return nodeTableCache.get(bn.deepCopy());
		}
		if (topOfNodeTable >= MAX_TABLE_SIZE) {
			System.out.println("FATAL ERROR : NODE TABLE => OVERFLOW : size : " + topOfNodeTable + " capacity : " + MAX_TABLE_SIZE);
		}

		nodeTable[topOfNodeTable] = bn.deepCopy();
		nodeTableCache.put(bn.deepCopy(), topOfNodeTable);
		return topOfNodeTable++;
	}

	public static boolean isConst(int address) {
		return address == 0 || address == 1;
	}

	public static int apply(char op, int F, int G) {
		// 1. F,Gのいずれかが定数のとき、およびF=Gのとき
		if (isConst(F) || isConst(G) || F == G) {
			if (F == G) {
				return F;
			}
			if (op == '|') {
				if (isConst(F) && isConst(G))
					return F | G;
				if (isConst(F)) {
					int tmp = F;
					F = G;
					G = tmp;
				}
				if (G == 0) {
					return F;
				} else {
					return 1;
				}
			} else if (op == '&') {
				if (isConst(F) && isConst(G))
					return F & G;
				if (isConst(F)) {
					int tmp = F;
					F = G;
					G = tmp;
				}
				if (G == 0) {
					return 0;
				} else {
					return F;
				}
			} else {
				System.out.println("INVALID OPERATOR : WHAT IS " + op + "?");
			}
		}

		BinaryOperatorMemoState boms = new BinaryOperatorMemoState(op, F, G);
		if (binaryOperatorCache.containsKey(boms)) {
			return binaryOperatorCache.get(boms);
		}

		// 2.両者の最上位変数F.vとG.vが同じとき
		BDDNode bnF = nodeTable[F].deepCopy(); // deepCopyでないと手順４を実行した場合にnodeTableの値が書きかわるので注意
		BDDNode bnG = nodeTable[G].deepCopy();
		if (bnF.variableID == bnG.variableID) {
			int H0 = apply(op, bnF.zeroID, bnG.zeroID);
			int H1 = apply(op, bnF.oneID, bnG.oneID);
			if (H0 == H1) {
				binaryOperatorCache.put(boms, H0);
				return H0;
			}
			int address = getNode(new BDDNode(bnF.variableID, H0, H1));
			binaryOperatorCache.put(boms, address);
			return address;
		}
		// 変数の番号が大きいほど下位であることに注意
		// 4.F.vがG.vよりも下位のとき
		// FとGを入れ替えて、3.と同様に処理
		if (bnF.variableID > bnG.variableID) {
			int tmp = F;
			F = G;
			G = tmp;
			bnF = nodeTable[F].deepCopy();
			bnG = nodeTable[G].deepCopy();
		}

		// 3.F.vがG.vよりも上位のとき
		int H0 = apply(op, bnF.zeroID, G);
		int H1 = apply(op, bnF.oneID, G);
		if (H0 == H1) {
			binaryOperatorCache.put(boms, H0);
			return H0;
		}
		int address = getNode(new BDDNode(bnF.variableID, H0, H1));
		binaryOperatorCache.put(boms, address);
		return address;
	}

	public static void printNodeTable() {
		System.out.println("table size = " + topOfNodeTable);
		for (int i = 0; i < topOfNodeTable; i++) {
			BDDNode bn = nodeTable[i];
			System.out.println(i + "-th : " + bn);
		}
	}

	public boolean equals(BDD bdd) {
		// System.out.println("bdd1 = " + this.addressOfNodeTable);
		// System.out.println("bdd2 = " + bdd.addressOfNodeTable);
		return this.addressOfNodeTable == bdd.addressOfNodeTable;
	}

	public static int getNodeTableSize() {
		return topOfNodeTable;
	}

}

class State {
	private int ID;

	public State() {

	}

	public State(int ID) {
		this.ID = ID;
	}

	public void setID(int ID) {
		this.ID = ID;
	}

	public int getID() {
		return this.ID;
	}

	@Override
	public String toString() {
		return String.valueOf(ID);
	}

	@Override
	public int hashCode() {
		return new Integer(ID).hashCode();
	}

	@Override
	public boolean equals(Object obj) {
		if (obj != null && obj instanceof State) {
			final State state = (State) obj;
			return this.getID() == state.getID();
		}
		return false;
	}

	public int compareTo(State state) {
		return new Integer(ID).compareTo(state.getID());
	}

}

class BooleanExpressionEvaluator {
	private String context;
	private int currentPosition;

	public BooleanExpressionEvaluator(String context) {
		this.context = context;
		currentPosition = 0;
	}

	BooleanExpression fact() {
		boolean not_coef = false;
		if (context.charAt(currentPosition) == '~') {
			++currentPosition;
			not_coef = true;
		}
        BooleanExpression be = null;
		if (context.charAt(currentPosition) == '(') {
			++currentPosition;
			be = exp();
			++currentPosition;
		} else {
            int ID = context.charAt(currentPosition++);
            be = new LogicVariable(ID);
		}
		if (not_coef) {
            be = new Not(be);
		}
		return be;
	}

	BooleanExpression exp() {
		BooleanExpression state1 = fact();
		while (currentPosition < context.length() && (context.charAt(currentPosition) == 'V' || context.charAt(currentPosition) == '^')) {
			char opr = context.charAt(currentPosition++);
			BooleanExpression state2 = fact();
			if (opr == 'V') {
                state1 = new Or(state1,state2);
			} else {
                state1 = new And(state1,state2);
			}
		}
		return state1;
	}

	public BooleanExpression eval() {
		return exp();
	}

}

class Main {    
    public static BooleanExpression toBooleanExpression(String s) {
        BooleanExpressionEvaluator bee = new BooleanExpressionEvaluator(s);
        return bee.eval();
    }

    public static int exec(String p1,String p2) {
        BDD bdd = new BDD();
        BooleanExpression be_p1 = toBooleanExpression(p1);
        BooleanExpression be_p2 = toBooleanExpression(p2);
        return (bdd.build(be_p1) == bdd.build(be_p2))?1:0;
    }

    public static String removeSpace(String s) {
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<s.length();i++) if( s.charAt(i) != ' ' ) {
                sb.append(s.charAt(i));
        }
        return sb.toString();
    }
    
    public static void main(String args[]) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        while(true) {
        String p1 = in.readLine();
        if( p1 == null )break;
        String p2 = in.readLine();
        p1 = removeSpace(p1);
        p2 = removeSpace(p2);
        //System.out.println(p1 + " ?= " + p2);
        System.out.println(exec(p1,p2));
        }
    }
}

Typical DP Contest D : サイコロ

問題リンク : D: サイコロ - Typical DP Contest | AtCoder

解法 :
Dを素因数分解したとき、その素因数に２、３、５以外のものが存在するのであれば求める確率は０となる
（サイコロの目が１から６までしかないので、例えば７は２、３、５の積ではどうやっても作れない）
それ以外の場合については、次のようなdp配列を用意し解を求める
dp[i][j][k][l] := i回さいころを振ったとき、素因数として２がj個、３がk個、５がl個となるような確率
また、愚直に配列を確保できないため、i,j,kがそれぞれ対応する素因数の数以上になったのであれば、その素因数の数にまとめる

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define EPS (1e-10)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

typedef long long ll;
const int MAX = 75;
double dp[101][MAX][MAX][MAX];
//                      2              3              5 
int N,factor[3][6] = {{0,1,0,2,0,1},{0,0,1,0,0,1},{0,0,0,0,1,0}};//1,2,3,4,5,6
ll D;

map<ll,int> prime_factor(ll n) {
  map<ll,int> res;
  for(ll i=2;i*i<=n;i++) {
    while(n % i == 0) {
      ++res[i];
      n /= i;
    }
  }
  if(n != 1)res[n] = 1;
  return res;
}

int main() {
  cin >> N >> D;
  int a_2 = 0, a_3 = 0, a_5 = 0;
  map<ll,int> pf = prime_factor(D);
  for(map<ll,int>::iterator it=pf.begin();it!=pf.end();it++) {
    if( it->first != 2LL && it->first != 3LL && it->first != 5LL ) {
      puts("0.0000000000");
      return 0;
    }
    if( it->first == 2LL ) a_2 = it->second;
    if( it->first == 3LL ) a_3 = it->second;
    if( it->first == 5LL ) a_5 = it->second;
  }

  dp[0][0][0][0] = 1;
  rep(i,N) rep(_2,a_2+1) rep(_3,a_3+1) rep(_5,a_5+1) if( !equals(dp[i][_2][_3][_5],0) ) {
    rep(dice,6) {
      int n_2 = _2 + factor[0][dice], n_3 = _3 + factor[1][dice], n_5 = _5 + factor[2][dice];
      dp[i+1][min(a_2,n_2)][min(a_3,n_3)][min(a_5,n_5)] += dp[i][_2][_3][_5] / 6.0;
    }
  }

  printf("%.10f\n",dp[N][a_2][a_3][a_5]);
  return 0;
}