解くのに10時間ほどかかった... 問題 TopCoder Statistics - Problem Statement 人が横に２列になって写真を撮る．それぞれの人はからまで番号がふられている． この時の並びは"nice"かつ"different"でなくてはいけない．"nice"とは，以上の番号がふられた人…

問題 No.210 探し物はどこですか？ - yukicoder 部屋が個あり，そのどこかにメガネがある． 番目の部屋にある確率がでその部屋を見た時に見つけられる確率がである． メガネを見つけるまでの部屋を見る回数の期待値を最小にする問題．解法 回目に番目の部屋…

問題 No.25 有限小数 - yukicoder 整数が与えられてが循環少数なら-1を有限少数なら0でない一番小さい桁の数を出力する問題．解法 まずを最大公約数で割って互いに素にする． を10で割り切れるなら10で割っておく． 次にが2の倍数ならに5をかけ，が5の倍数な…

問題 No.209 Longest Mountain Subsequence - yukicoder 個の整数が与えられる． を地形の高さだと考えた時に，の部分列から構成される山で，麓に近づくにつれて坂が緩やかになるような山の幅の最大値を求める問題．解法 ある地点を頂上だと考えた時にそこか…

問題 No.313 π - yukicoder 20万桁ある円周率のうち，一箇所だけ間違いがある． どの数字が間違っているか指摘する問題．解法1 （解法1では解けません） 円周率を20万桁まで計算して比較するという方法を取ろうとしてしまった． しかし5秒以内に計算するとな…

問題 No.165 四角で囲え！ - yukicoder 座標上に個の点があり，それぞれ点数が与えられている． を超えないように四角で囲った時最も多く囲える点の数を求める問題解法 座標圧縮と半分全列挙としゃくとり法を使う． まず，座標圧縮をする． 座標用のmapと座…

問題 No.356 円周上を回る3つの動点の一致 - yukicoder 円周上を3つの点が時計回りに移動している． それぞれ，秒で一周するとき， 同じ点から動き始める時，次に3点が一致するのは何秒後か．解法 秒後にが整数かつが整数ならば，3点が一致する． まずとの最…

問題 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座標の小さい方から走査していく． 走査する直線が円の左端にぶつかった時，その円が他の円に含まれているか調べる． この時，調…