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

問題 No.368 LCM of K-products - yukicoder 個の正整数からなる数列がある． の添字が異なる個の要素の積からなる集合をとした時， の全要素の最小公倍数をで割った余りを求める．解法 は素数)とした時， 最小公倍数は lcmとなる． ちなみに最大公約数は gc…

問題 No.367 ナイトの転身 - yukicoder のチェス盤が与えられ，ナイトとミニビショップを操作する． ミニビショップは斜めに１マスだけ移動できる駒である． ナイトでスタートし，赤いマスを通るとミニビショップになる． スタート地点，ゴール地点，赤いマ…

問題 No.366 ロボットソート - yukicoder 個の数字が並べられていて， との数字を入れ替えることができる． 昇順に並べ替えられる時はその操作回数を 並べ替えられない時はを出力するという問題．解法 添字に対してが等しくなる集合に分ける． それぞれをバ…

問題 No.365 ジェンガソート - yukicoder の数字がランダムに並べられている． １回の操作で数字を１つ選んで一番前に持ってくることができる． 数字を昇順に並び替えるための最小の操作の回数はいくつか．解法 最悪でも回の操作でソートが可能である． そこ…

問題 Problem - B - Codeforces 棒が本あり，それぞれの長さはである． それらを繋げても多角形を作ることが出来ない． 1本棒を加えるとき，多角形を作るために必要な最短の長さは幾つか．解法 の最大値をとした時， その他の棒を合わせてが得られれば多角形…

問題 Problem - A - Codeforces 直径cmの円筒があり，初めに高さcmだけ水が入っている． 毎秒mlで水を飲み，また雨によって毎秒cmだけ水かさが増すとき， 水を飲みきれるか，飲みきれるとしたら何秒かかるか．解法 が成り立つので ならば飲みきれ， が答えに…

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

問題 No.38 赤青白ブロック - yukicoder 赤，青，白の各10個のブロックがあり，一列に並べられている． すべてのブロックに対して 赤の左右Kr個離れた位置に赤がない 青の左右Kb個離れた位置に青がない を満たすように赤と青のブロックを抜くときの最大のブ…

問題 No.199 星を描こう - yukicoder XY座標上の点が５つ与えられる．点を線で繋いで星が描けるかどうかを判定する．解法1 それぞれの頂点を結ぶ線分をすべて考えて， 他の線分と交わる回数が２回のものが５つあれば星を描ける（端は数えません）． 交点の求…

問題 2932 -- Coneology 平面上に円がN個あり，それらが交わることはない． どの円にも囲まれていない円はいくつあるか．解法 x座標の小さい方から走査していく． 走査する直線が円の左端にぶつかった時，その円が他の円に含まれているか調べる． この時，調…