結果

問題 No.65 回数の期待値の練習
コンテスト
ユーザー ゴリポン先生
提出日時 2025-04-15 20:44:57
言語 D
(dmd 2.109.1)
結果
WA  
実行時間 -
コード長 7,356 bytes
コンパイル時間 5,346 ms
コンパイル使用メモリ 226,848 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-04-15 20:45:04
合計ジャッジ時間 6,394 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 3 WA * 13
権限があれば一括ダウンロードができます
コンパイルメッセージ
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/numeric.d(3130): Warning: cannot inline function `std.numeric.gcdImpl!(BigInt).gcdImpl`

ソースコード

diff # 

module main;

// https://qiita.com/NokonoKotlin/items/483c08d892b1ad751330 より
/*   
    このコメントは消さないでください。
    Don't remove this comment!!!

    Copyright ©️ (c) NokonoKotlin (okoteiyu) 2024. 
    Released under the MIT license(https://opensource.org/licenses/mit-license.php) 
*/
import std;
// 有理数の構造体
struct Fraction {
private:
	BigInt A, B;	// 分子と分母
	BigInt mEpsSign = 0;	// 微小部分の符号
public:
	// 約分(正規化)を行う
	void normalize() @safe pure nothrow
	{
		if (A == 0 && B == 0) return;
		if (A == 0) {
			B = 1;
			return;
		}
		if (B == 0) {
			A = A > 0 ? 1 : -1;
			return;
		}
		BigInt g = gcd(A, B);
		A /= g;
		B /= g;
		if (B < 0) {
			A = -A;
			B = -B;
		}
	}
	// 定数
	static immutable(Fraction) inf() pure nothrow @safe
	{
		return Fraction(1, 0);
	}
	static immutable(Fraction) ninf() pure nothrow @safe
	{
		return Fraction(-1, 0);
	}
	static immutable(Fraction) amb() pure nothrow @safe
	{
		return Fraction(0, 0);
	}
	static immutable(Fraction) zero() pure nothrow @safe
	{
		return Fraction(0);
	}
	// コンストラクタ
	this(T : BigInt)(T a) pure
	{
		A = a;
		B = 1;
		normalize();
	}
	this(T : BigInt, U : BigInt)(T a, U b) pure
	{
		A = a;
		B = b;
		normalize();
	}
	this(T)(T a) pure
		if (isIntegral!T)
	{
		this(BigInt(a));
	}
	this(T, U)(T a, U b) pure
		if (isIntegral!T && isIntegral!U)
	{
		this(BigInt(a), BigInt(b));
	}
	this(T)(T rhs) pure nothrow @safe
		if (is(immutable T == immutable BigInt))
	{
		opAssign(rhs);
	}
	// 代入演算子
	Fraction opAssign(T)(T rhs) nothrow @safe pure
		if (isIntegral!T)
	{
		A = rhs;
		B = 1;
		mEpsSign = 0;
		normalize();
		return this;
	}
	Fraction opAssign(T : Fraction)(T rhs) @safe pure
	{
		A = rhs.A;
		B = rhs.B;
		mEpsSign = rhs.mEpsSign;
		normalize();
		return this;
	}
	// 不定値かどうか
	bool isAmbiguous() pure nothrow @safe const
	{
		return A == 0 && B == 0;
	}
	// 無限大かどうか
	bool isInfinite() pure nothrow @safe const
	{
		return A != 0 && B == 0;
	}
	// 符号
	BigInt sign() pure nothrow @safe const
	{
		assert(!isAmbiguous());
		if (A == 0) return mEpsSign;
		return A > 0 ? BigInt(1) : BigInt(-1);
	}
	// 分子と分母のタプルを返す
	auto rawPair() pure const
	{
		return tuple(A, B);
	}
	// 絶対値
	Fraction abs() pure nothrow @safe const
	{
		if (A > 0)
			return this;
		if (A < 0)
			return -this;
		if (mEpsSign >= 0)
			return this;
		return -this;
	}
	// 逆数
	Fraction inv() pure nothrow @safe const
	{
		if (isAmbiguous())
			return amb();
		if (A == 0) {
			if (sign() == 0) return amb();
			return Fraction(sign(), BigInt(0));
		}
		if (B == 0) {
			auto res = Fraction(0);
			res.mEpsSign = sign();
			return res;
		}
		return Fraction(B, A);
	}
	/*
	 * 単項演算子
	 */
	Fraction opUnary(string op : "-")() pure nothrow @safe const
	{
		return Fraction(-A, B);
	}
	/*
	 * 演算代入演算子
	 */
	// 足し算
	ref Fraction opOpAssign(string op : "+")(Fraction rhs) pure nothrow @safe
	{
		if (isAmbiguous() || rhs.isAmbiguous()) {
			this = amb();
		} else if (isInfinite() && rhs.isInfinite()) {
			if (sign() != rhs.sign()) this = amb();
			else if (sign() == -1) this = ninf();
			else this = inf();
		} else if (isInfinite()) {
		} else if (rhs.isInfinite()) {
			this = rhs;
		} else if (A == 0 && rhs.A == 0) {
			if (sign() == rhs.sign()) {}
			else if (sign() == 0) this = rhs;
			else if (rhs.sign() == 0) {}
			else this = amb();
		} else {
			this = Fraction(A * rhs.B + B * rhs.A, B * rhs.B);
		}
		return this;
	}
	// 掛け算
	ref Fraction opOpAssign(string op : "*")(Fraction rhs) pure nothrow @safe
	{
		if (isAmbiguous() || rhs.isAmbiguous()) {
			this = amb();
		} else if (isInfinite() || rhs.isInfinite()) {
			if (A && rhs.A) {
				if (sign() == rhs.sign()) this = inf();
				else this = ninf();
			} else {
				if (sign() == 0 || rhs.sign() == 0) this = 0;
				else this = amb();
			}
		} else if (A == 0 || rhs.A == 0) {
			if (sign() == 0 || rhs.sign() == 0) this = 0;
			else {
				auto newEps = Fraction(0);
				newEps.mEpsSign = sign() * rhs.sign();
				this = newEps;
			}
		} else {
			this = Fraction(A * rhs.A, B * rhs.B);
		}
		return this;
	}
	// 引き算
	ref Fraction opOpAssign(string op : "-")(Fraction rhs) pure nothrow @safe
	{
		return this += -rhs;
	}
	// 割り算
	ref Fraction opOpAssign(string op : "/")(Fraction rhs) pure nothrow @safe
	{
		return this *= rhs.inv();
	}
	// 剰余
	ref Fraction opOpAssign(string op : "%")(Fraction rhs) pure nothrow @safe
	{
		assert(!isAmbiguous() && !isInfinite() && !rhs.isAmbiguous() && !rhs.isInfinite());
		assert(rhs.A);
		auto tmp = this;
		tmp /= rhs;
		auto pair = tmp.rawPair();
		BigInt m = pair[0] / pair[1];
		return this -= m * rhs;
	}
	ref Fraction opOpAssign(string op, T)(T rhs) pure nothrow @safe
		if ((op=="+" || op=="-" || op=="*" || op=="/" || op=="%") && isIntegral!T)
	{
		return opOpAssign!op(Fraction(rhs));
	}
	/*
	 * 二項演算子
	 */
	Fraction opBinary(string op)(Fraction rhs) pure nothrow @safe const
		if (op == "+" || op == "-" || op == "*" || op == "/" || op == "%")
	{
		Fraction f = this;
		return f.opOpAssign!op(rhs);
	}
	Fraction opBinary(string op, T)(T rhs) pure nothrow @safe const
		if ((op == "+" || op == "-" || op == "*" || op == "/" || op == "%") && isIntegral!T)
	{
		Fraction f = this;
		return f.opOpAssign!op(Fraction(rhs));
	}
	Fraction opBinaryRight(string op, T)(T lhs) pure nothrow @safe const
		if ((op=="+" || op=="*") && isIntegral!T)
	{
		return opBinary!op(lhs);
	}
	/*
	 * 比較演算子
	 */
	double opCmp(Fraction rhs) const
	{
		if (isAmbiguous() || rhs.isAmbiguous()) {
			return double.nan;
		} else if (sign() != rhs.sign()) {
			return cast(double)(sign() - rhs.sign());
		} else if (A == 0 || rhs.A == 0) {
			if (sign() == 0 && rhs.sign() == 0) return 0.0;
			if (A == 0 && rhs.A == 0) return 0.0;
			if (A == 0) return rhs.sign() == -1 ? 1.0 : -1.0;
			return sign() == -1 ? -1.0 : 1.0;
		} else if (isInfinite() && rhs.isInfinite()) {
			return 0.0;
		} else if (isInfinite()) {
			return sign() == -1 ? -1.0 : 1.0;
		} else if (rhs.isInfinite()) {
			return sign() == -1 ? 1.0 : -1.0;
		} else {
			return cast(double)(A * rhs.B - B * rhs.A);
		}
	}
	/*
	 * 等号演算子
	 */
	bool opEquals(ref const Fraction rhs) const
	{
		return 0.0 == opCmp(rhs);
	}
	/*
	 * キャスト演算子
	 */
	T opCast(T)() const
		if (isFloatingPoint!T)
	{
		if (isAmbiguous())
			return T.nan;
		if (isInfinite())
			return A > 0 ? T.infinity : -T.infinity;
		// A÷Bの商と余り
		auto Q = cast(T)(A / B), R = A % B;
		if (Q.isInfinity)
			return Q;
		return Q + cast(T)R / cast(T)B;
	}
	/*
	 * 標準出力
	 */
	void toString(scope void delegate(const(char)[]) sink) const
	{
		if (isAmbiguous()) {
			sink("?");
		} else if (A == 0) {
			if (sign() > 0) sink("ε");
			else if (sign() < 0) sink("-ε");
			else sink("0");
		} else if (isInfinite()) {
			if (sign() > 0) sink("∞");
			else sink("-∞");
		} else {
			sink(format("%d", A));
			sink("/");
			sink(format("%d", B));
		}
	}
}

void main()
{
	// 入力
	auto K = readln.chomp.to!int;
	// 答えの計算と出力
	auto E = Fraction(0L).repeat(21).array;
	foreach_reverse (i; 0 .. K) {
		E[i] = 1 + Fraction.zero().reduce!((a, b) => a + b)(E[i + 1 .. K + 1]) / 6;
	}
	writeln(cast(double)E[0]);
}
0