問題 問題概要 LとRをK回2分探索をして、最終的な答えが、T-E < h' < T + Eに入る確率を求める問題。確率Pで誤った2分探索をして、確率(1-P)で適切な2分探索をする。 解法 全探索で、やろうと思うと、2k(k=30)でTLE?? ただし、2分探索をしていく途中で、 (T …

問題 問題概要 省略 解法 dpで解いた。dp[i][j] := i回数字を引いて、jになるなら、true、とおいてループで回して埋めていった。 dp[i][j+k]=trueならdp[i][j]=trueとなるので(ただし、jはngでない)、このことから漸化式らしきものが立てられる。 ミス nがい…

問題 問題概要 省略 解法 幅が小さいものから貪欲に選んでいけばいい。 ミス なし。 コード #include <iostream> #include <cstdio> #include <vector> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) int main(void){ int l, n; cin </algorithm></vector></cstdio></iostream>…

問題 問題概要 省略 解法 grundy数をメモ化再帰で求めることにした。 grundy数の求め方だが、 grundy数は -負けの状態で0 -遷移先のGrundy数に含まれない最小の整数 なので、状態遷移先を列挙していき、最小のgrundy数を求めに行けばいい。今回の問題は、nか…

問題 問題概要 省略 解法 grundy数をメモ化再帰で求めることにした。 この問題は竹が分裂していくが、竹が一個の時のgrundy数をxorとるだけで、複数のゲームが合わさった状態のgrundy数を考えることができる。蟻本p284に書いてある。 grundy数の求め方だが、…

問題 問題概要 省略 解法 grundy数をメモか再起で求めることにした。 この問題は山が分裂していくが、山が一個の時のgrundy数をxorとるだけで、複数のゲームが合わさった状態のgrundy数を考えることができる。蟻本p284に書いてある。 grundy数の求め方だが、…

問題 問題概要 省略 解法 Mが与えられ、その中で、同じ素因数であれば1回以上2回まで同時に割ることができる。よって、それぞれのMの中でさらに素因数ごとに山に分ける。そうすると、それぞれの山をmod3とった値がgrundy数となる。 mmxsrup.hatenablog.com …

問題 問題概要 省略 解法 grundy数とNimの勉強しました. 参考サイト pekempey.hatenablog.com d.hatena.ne.jp 上のサイトを参考にgrundy数を、１つの山について考えると、 残り枚数:0 1 2 3 4 5 grundy:0 1 2 3 0 1 のような関係になっている。 よって、n1,n…