SRM588Div1Easy
問題
N個の曲と時間Tが与えられる。各曲にはdurationとtoneが与えられており、T秒間だけ曲を流すことができる。durationは曲の長さを秒で示す。現在の曲がtone[i]で次の曲がtone[j]だとすると、次の曲に移るのに|tone[i]-tone[j]|秒必要とする。
T秒間の間にながせる曲の最大値を求めよ。
解法
toneの範囲を指定し、その中でdurationが短いものから順に選択していく。toneの範囲を与えられた曲の組み合わせで全探索することで答えが求まる。
計算量
コード
SRM589Div1Easy
問題
サイズNの文字列が与えられる。与えられた文字列を回文にするのに最小な時間を求めよ。
許される操作は、以下である。
任意の2つの文字A,Bを選択し。すべての文字AをBに変更する。この時、ひとつの文字を変更するのに1秒かかる。
解法
同じ文字と反対側にある文字をひとつのグループとし、その中で最多の文字に他の文字を変更する。
計算量
コード
SRM590Div1Easy
問題
サイズNの配列beginとtargetが与えられる。要素は'.','L','R'のいずれかである。'.'は空を示し、'L'は左に移動できる駒、'R'は右に移動できる駒を示す。
beginの状態からtargetの状態に遷移可能か求めよ。
解法
各要素の位置情報を比較することで、答えが求まる。
計算量
コード
SRM571Div1Easy
問題
N個の曲が与えられ、各曲の名前はN+".mp3"となっている。辞書順に並べ、はじめのmin(50, N)個の要素を求めよ。
解法
はじめに桁を上げていき、その後は数字を1ずつあげていく。
計算量
コード
SRM573Div1Easy
問題
サイズNの配列が与えられる。Nは3の倍数である。プログラミングコンテストを考える。各要素はプログラマの実力を示し、はじめの3要素X,Y,Zが自身のチームメンバーである。チームの能力はmax(X,Y,Z)+min(X,Y,Z)で求まる。この能力より真に大きいチームは、自身のチームより高い順位となる。
この時の自身のチームの最悪の順位を求めよ。
解法
能力順にソートし、大きい要素と小さい要素で能力を比較することで答えが求まる。
計算量
コード
SRM657Div1Easy
問題
SRMのようにEasy, Medium, Hardの3つでひとつである問題セットを考える。E,M,HはそれぞれEasy, Medium, Hardの問題であり、EMはEasyにもMediumなれる問題であり、MHはMediumにもHardにもなれる問題である。
E,M,H,EM,MHの数が与えられた時の問題セットの最大値を求めよ。
E,M,H,EM,MHの最大値はNである。
解法
問題セットの数を固定すれば、それを満たすかの確認はできる。
問題セットの数に対して二分探索をすることで、答えが求まる。
計算量
コード
SRM659Div1Easy
問題
N個のフルーツが並んでおり、それらはりんごかオレンジである。K個の連続するフルーツは最大でもK/2個のりんごしかない。
いくつかのりんごの位置の配列が与えられた時の最大のりんごの数を求めよ。
解法
左側の要素から探索していき、周囲K個のりんごの数がK/2より小さいならその要素をりんごにする。
計算量
