2018-10-04から1日間の記事一覧

SRM549 Div1 Easy - PointyWizardHats

問題 円錐状の帽子を2つ組み合わせて魔女の帽子を作りたい 上側用の帽子がn個、下側用の帽子がm個ある 上側用の帽子iと下側用の帽子jは以下の条件を満たすときのみ組み合わせて魔女の帽子にできる 1) 上側の帽子の頂点は下側の帽子の頂点より上にある 2) 下…

SRM548 Div1 Easy - KingdomAndTrees

問題 木がn本あり、i本目の高さはa[i]である コストxの魔法を使うと各木の高さを0〜xだけ増やすか減らすことができる aを競技単調増加にするために使う必要のある魔法の最小コストを求めよ2 1 解法 二分探索 使う魔法のコストを決めたとき、各木の高さは単調…

SRM547 Div1 Easy - Pillars

問題 2本の塔があり、距離はwである これらの塔の高さは1本目が[1,x]、2本目が[1,y]の範囲から等確率で決まる 2本の塔それぞれの頂上同士をまっすぐなロープで繋ぐ ロープの長さの期待値を求めよ1 1 解法 1本目の塔の高さをkに固定する 更に2本目の高さがmに…

SRM546 Div2 Medium - TwoRectangles

問題 長方形が2つ、それぞれ左下と右上の点の座標が与えられる これらの長方形の共通範囲が 長方形 or 線 or 点 or 存在しない のどれであるか判定せよ0 解法 初期値0の2次元配列で2つの長方形が占める領域をそれぞれ全部+1すると、重なってる部分は2になる …

SRM546 Div1 Easy - KleofasTail

問題 「xのkleofas tail」とは、1個目の要素がxで、i(>2)個目の要素が i-1個目の要素=yが偶数のとき) y/2 yが奇数のとき) y-1 であるような長さ無限の数列である a 0 0 解法 kからスタートして逆操作をしていく kが偶数のときはk*2かk+1へ、奇数のときはk*2…

SRM545 Div1 Easy - StrIIRec

ちょっと面白かった 540台はなかなか解き応えのある問題が多い 問題 以下の条件を満たす文字列を作れ 1) 長さnで、アルファベット26文字の最初のn文字を1文字ずつ使っている 2) 転倒数がk以上 3) 辞書順でs以上 4) これらの条件を満たす中で辞書順最小 解法 …

SRM544 Div2 Medium - BoardSplitting

問題 長さkの板が無限にある これらを切ったりくっつけたりして長さLの板をn枚作りたい 長さkの板を必要最小限の枚数だけ使うとき、最低何回板を切る必要があるか求めよ1 解法 貪欲 長さkの板を切って余った板を寄せ集めてちょうど長さLにできる場合はコスト…