きままにものづくり

日々の気付いたことなんかを書いてます。

2015-05-01から1ヶ月間の記事一覧

SRM588Div1Easy

問題 N個の曲と時間Tが与えられる。各曲にはdurationとtoneが与えられており、T秒間だけ曲を流すことができる。durationは曲の長さを秒で示す。現在の曲がtone[i]で次の曲がtone[j]だとすると、次の曲に移るのに|tone[i]-tone[j]|秒必要とする。 T秒間の間に…

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の数が与えられた時の問題セット…

SRM659Div1Easy

問題 N個のフルーツが並んでおり、それらはりんごかオレンジである。K個の連続するフルーツは最大でもK/2個のりんごしかない。 いくつかのりんごの位置の配列が与えられた時の最大のりんごの数を求めよ。 解法 左側の要素から探索していき、周囲K個のりんご…

SRM658Div1Easy

問題 サイズN*Nの配列xが与えられる。サイズNのツリーを考え、配列の各要素はx[i][j]はiからjまでの距離が偶数か奇数かを示している。与えられた配列の条件を満たすツリーを求めよ。 解法 TopCoder SRM 658 Div1 Easy OddEvenTree - kmjp's blogkmjp.hatenab…

SRM591Div1Easy

問題 ルートからの距離がxであるノードを個持つツリーを考える。この時のツリーの直径を求めよ。 解法 各ノードをルートとした時の子であるノードの中で深さが最大となる2つを選ぶ。これを全てのノードに対して行うことで答えが求まる。 最初に与えられたツ…

SRM592Div1Easy

問題 サイズNの文字列が与えられる。各要素はR,G,Bのどれかである。何もない文字列から始め、一文字ずつ文字を加え与えられた文字列にする時の最高のスコアを求めよ。 スコアは以下のように追加される。 初めの要素の場合は0ポイント 文字列の端に追加した場…

SRM593Div1Easy

問題 N*Nの配列が与られる。各マスは六面体となっており、要素はXか-である。Xの箇所を任意の色で塗りたい。ただし、隣り合うマスでは違う色とする。この時に必要な色の最小数を求めよ。 解法 3色あればどんな場合でも塗ることができる。なので、0、1、2のど…