yukicoder

yukicoder No.409 ダイエット

問題 No.409 ダイエット - yukicoder 嘘解法 ドーナッツの増加量の上限が 1,000,000 であることから、B が正の値であるときストレス値が 1000 を超えないことが分かる。(1000 を超える時、どのドーナツよりもコストが高くなってしまう)よってストレス値を…

yukicoder No.372 It's automatic

問題 No.372 It's automatic - yukicoder 解法 DP コード #include <bits/stdc++.h> using namespace std; const int64_t MOD = 1e9 + 7; int main() { cin.tie(0); ios::sync_with_stdio(false); string inS; cin >> inS; int N = inS.size(); vector<int> S(N); for (int i = 0</int></bits/stdc++.h>…

yukicoder No.371 ぼく悪いプライムじゃないよ

問題 No.371 ぼく悪いプライムじゃないよ - yukicoder 解法 必要な素数をエラトステネスのふるいで全列挙しておく。列挙した素数を大きい方から見ていき、その素数が解答の最小の素因数になりうるかを考える。見ている素数をprime[i]とするとき、[L, H] に含…

yukicoder No. 177: 制作進行の宮森あおいです! (最大フロー問題)

問題 No.177 制作進行の宮森あおいです! - yukicoder 解法 始点→原画マン→作画監督→終点、という最大フロー問題に帰着する。 コード import java.io.IOException; import java.util.ArrayList; import java.util.Arrays; public class Main { public static…

yukicoder No. 176: 2種類の切手

問題 No.176 2種類の切手 - yukicoder 解法 Bの枚数を0から総当りする。Bの枚数をiとした時、切手の合計額がTをギリギリ超えるようなAの枚数jは、以下のように書ける。 j = (T - B * i + A - 1) / AB*iがTを超えていたりB*Aを超えていたりしたらbreakする。 …

yukicoder No. 174: カードゲーム(Hard)

問題 No.174 カードゲーム(Hard) - yukicoder 解法 #17295 No.174 カードゲーム(Hard) - yukicoderdp[k]:= あるターンturnにおける、j番目に小さいカードより小さいカードがk枚ある確率、をメモする。turnが遷移する時、 dp[0] *= (1 - P[player]); dp[c…

yukicoder No. 173: カードゲーム(Medium) (モンテカルロ法・シミュレーション)

問題 No.173 カードゲーム(Medium) - yukicoder 解法 誤差0.005以内で正解になるという緩さなので、10000100,000回シミュレーションして勝率を出す。@meguru_comp おっしゃるとおりです。100,000回でした。(コードは100000になってます)— 宇宙ツイッタラ…

yukicoder No. 171: スワップ文字列

問題 No.171 スワップ文字列(Med) - yukicoder 解法 重複組み合わせの式で計算するだけだが、掛け算を先にやろうとすると値が大きくなりすぎる。かと言って割り算を先にやることも出来ず、ましてや573で剰余を取ることも出来ないので、掛け算と割り算を同時…

yukicoder No. 168: ものさし (Union-Find木)

問題 No.168 ものさし - yukicoder 解法 任意の2点間の距離(最低限必要になるものさしの長さ)を求めておく。それらをソートし、距離の小さい順に取り出していく。取り出した辺の始点と終点を結び、Union-Find木で結合しておく。点1と点N-1が同じ木になるま…

yukicoder No. 165 四角で囲え! (累積和・片側全探索)

問題 No.165 四角で囲え! - yukicoder 解法 AOJ 2426の方法を使いまわして座標圧縮する。 AOJ 2426: 宝探し(2次元の累積和) - 宇宙ツイッタラーXの憂鬱かつにおける宝物の数とポイントを計算してやれば良いが、x1とx2とy1とy2を全探索するとTLEになるので…