問題 問題概要 省略 解法 与えられた関数は、下に凸の関数となるので、最小値は3分探索で探すことができる。 ミス よくわからんけど、rの大きさが大きすぎて、バグらした、3分探索を練習したい。 コード #include <iostream> #include <cstdio> #include <set> #include <vector> #include <algorithm> </algorithm></vector></set></cstdio></iostream>…

問題 問題概要 トーナメントで勝ち進んでいく確率。 解法 dpで解いた。 dp[i][j] := i回回目の試合にj番目のひとが勝つ確率 として、漸化式にそって、ループで値を埋めていく。漸化式は簡単で、 dp[i + 1][x] += dp[i][x] * dp[i][y] * memo[x][y] のように…

問題 問題概要 省略 解法 dpで解いた。 dp1[i][j] := 太郎君がサイコロをi回振って、合計がjの時の確率 dp2[i][j] := 次郎君がサイコロをi回振って、合計がjの時の確率 とおいて、漸化式でi=1からi=nまでループを回して埋めていった。 漸化式は単純で、いか…

問題 問題概要 省略 解法 bfsで解いた。よくある、2次元座標上での迷路問題などで、ゴールまで行けるかの問題と同じようにやる。ただし、4方向への移動が高さの条件で制限されるので、それを確認すればよい。また、dyとdxを2倍して、2倍の距離の移動も同様に…

問題 問題概要 省略 解法 2進数で表したときに、2倍すると、1桁左に移動するので、末尾に0をつければよい。すなわち、hamをつければいい。 ex1) 101(5) 1010(10) ex2) 111(7) 1110(14) 注意しなければならないのは、n=hamの時0なので、2倍しても0のまま。 ミ…