h_nosonの日記

競プロ、CTFなど

二分探索

Codeforces Round #367 (Div. 2) D. Vasiliy's Multiset

問題 Problem - D - Codeforces 3つのクエリに答える. 1. xをmultiset Aに加える 2. xをmultiset Aから取り除く 3. を出力する 解法1 c++のmultisetを使って二分探索をする. xorをとった値が大きくなるように上位のbitから0か1か決めていけばいい.xを反転…

AtCoder Grand Contest 002 D - Stamp Rally

問題 D: Stamp Rally - AtCoder Grand Contest 002 | AtCoder N頂点,M辺からなるグラフがあり,Q組の兄弟がスタンプラリーを行う.i番目の兄弟はそれぞれXi,Yiにいて合わせてZiのスタンプを集めたいと思っている.通ることになる辺の最大の番号を最小にす…

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

問題 No.174 カードゲーム(Hard) - yukicoder A君とB君がカードでゲームを行う.1から1000までの数字が書かれたカードがあり,その中から枚ずつ配られる.試合は回あり,試合ごとにプレイヤーがカードを出していき,大きい数字を出したほうがその数字…

Codeforces Round #350 (Div. 2) D1,D2. Magic Powder

問題 Problem - D1 - Codeforces クッキーを作ろうとしている.1つ作るのに種類の材料がずつ必要である.初めにずつ持っているとする.また,のマジックパウダーも持っており,そのパウダーはどの材料にも変えることができる.作れるクッキーの最大値はいく…

yukicoder No.75 回数の期待値の問題

問題 No.75 回数の期待値の問題 - yukicoder 1つのサイコロを繰り返し振り,出た目の合計をにする. もしを上回ったら合計を0にリセットする. サイコロの振る回数の期待値はいくらか.解法1 絶対誤差か相対誤差がに収まればいいので モンテカルロでも正解を…

yukicoder No.67 よくある棒を切る問題 (1)

問題 No.67 よくある棒を切る問題 (1) - yukicoder N本の棒がある. それらの棒を切ってK本の同じ長さの棒を取り出したいとき そのK本の棒の最大の長さは幾つか.解法 棒の長さの二分探索で解ける. 問題は誤差で,相対誤差または絶対誤差が以下ならよいので…