結果
問題 |
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`
ソースコード
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]); }