きままにものづくり

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

SRM581Div1Easy

問題 N個のコンテナとM個の監視カメラを考える。監視カメラは連続したL個のコンテナを監視できる。コンテナが空の場合は"-"となり、何か入っている場合は"X"となる。カメラの位置は分からないが、カメラが監視している空でないコンテナの数は与えられる。 こ…

SRM582Div1Easy

問題 N人の戦士が与えられ、それぞれの戦士の強さはs[i]である。また、M種類の強さes[j]を持つec[j]匹のモンスターも与えられる。戦士は自身より強さの小さいモンスターを討伐できる。戦士は一匹のモンスターを倒すと疲労度が1増える。すべてのモンスターを…

SRM583Div1Easy

問題 N個の街がひとつの輪となるようにつながっている。各街からは電車が出ており、それぞれの電車は最大range[i]個の街を移動できる。startからendまで行くのに必要な電車に乗る回数の最小値を求めよ。 解法 最短路問題に帰着できる。 ダイクストラで解いて…

SRM584Div1Easy

問題 ある国にはN人の国民がおり、それぞれ貯金を持っている。この国のルールとして貯金額の差がdより大きい人同士では友達になることはできない。 友人関係を示す情報とdが与えられた時、国民間での貯金額の最大値を求めよ。有限値でない場合は-1を返す。 …

SRM585Div1Easy

問題 高さNの二分木が与えられる。すべてのノードに車が通るようにするためには、最小でいくつの車が必要か求めよ。 ただし、車は他の車も含め一度通ったノードをもう一度通ることはできない。 解法 動的計画法で求まる。 一番外側のノードを一台の車に走ら…

SRM586Div1Easy

問題 サイズNの配列Yが与えられる。配列の要素は座標を示しておりインデックスをxとした時、(x, Y[x])となる。隣り合う点どうしを直線で結びグラフを作成する。 x軸と平行な線と作成したグラフとの交点の最大数を求めよ。 解法 yに小数点をとることも可能な…

SRM587Div1Easy

問題 十分に長い階段を考える。整数NとbadStepが与えられた時にN回の操作で、到達できる最大の高さを求めよ。 許される操作は、i回目の操作の時に、i個分の段差を飛び越えるかそのまま動かないかのどちらかである。ただし、badStepの高さに行くことはできな…

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のど…

SRM594Div1Easy

問題 N個の惑星の相対サイズAとM個の惑星の相対サイズBが与えられる。各要素は中心からの距離が近い順に並べられている。相対サイズとはある基準に対して何倍であるかを示す値である。AとBそれぞれの中では基準は同一であるが、AとBで同じ基準であるとは限ら…

SRM595Div1Easy

問題 サイズMの配列が与えられる。各要素は白か黒である。その配列に対してロボットがある操作を行う。ロボットはサイズNの配列L,Rを持っている。その配列に従い、L[i]~R[i]までを白か黒で塗りつぶす。ロボットの作業が終わったあとの配列の状態の総数を求め…

SRM557Div1Easy

問題 隣り合う要素の差分が1である長さnの数列を考える。はじめの要素h0と最後の要素hnが与えられる。差分を示す文字列historyが与えられた時、そのhistoryを実現できるかを判定せよ。historyの要素はUかDのどちらかで、Uはh[i+1]-h[i]=1、Dはh[i+1]-h[i]=-1…

SRM645Div1Medium

問題 二次元平面上にN個の点が(x1,y1)と(x2,y2)が与えられる。平面上には3つの塔があり、ひとつの塔を指定し魔法を唱えると、その塔を中心に点対象に点を移動できる。(x1,y1)の点を(x2,y2)に移動できるかを判別せよ。 解法 TopCoder SRM 645 Div1 Medium Arm…

SRM643Div1Medium

問題 2行N列の行列が与えられる。各要素はHかSである。以下の3つの操作を行い、すべての要素をHにするための最小の操作回数を求めよ。 どれか一つの要素を選びXとし、それと隣り合っている要素を一つ選びYとする。Xの要素をYの要素に書き換える。 連続する列…

SRM642Div1Medium

問題 H個の木がある。各木のはじめの高さはで与えられ、の高さだけ毎日成長する。木を切るためのデバイスがD個与えられる。これは、高さが以上の木を高さに切ることができる。その日の最後にデバイスを使用することができる。各デバイスは1日に一度しか使え…

SRM656Div1Easy

問題 サイズNの配列が与えられる。i番目の要素はパンケーキの美味しさを示し、サイズはi+1とする。 以下の操作を行ったあとの美味しさの総和の期待値を求めよ。 選択されていないパンケーキを一様ランダムに選ぶ 選んだパンケーキのサイズがスタックの上にあ…

SRM655Div1Easy

問題 サイズX、Yの二次元配列が与えられる。各要素はWかBである。同じサイズの全ての要素がWの二次元配列から以下の操作を行い、与えられた配列にすることができるかを判定せよ。 操作は二次元配列と共に与えられるkを用いて行う。サイズkの正方形を二次元配…

SRM654Div1Easy

問題 サイズNの配列が与えられる。各要素は小文字のアルファベット(a-z)か?である。?は小文字のアルファベットに変更することができ、各アルファベットへの変換確率はpで与えられる。 全ての要素が同じ部分配列の数がその配列のスコアとする。与えられた配列…

SRM653Div1Easy

問題 様々な国から来たN人が一列に並んでいる。その内の何人かにどこの国から来たのかを聞いた。同じ国から来た人は隣合っている。 現状の調査結果を表す配列Aが与えられる。この結果から、全ての解答を一意に予測できるか求めよ。 解法 Coding is fun: SRM …

SRM641Div1Medium

問題 サイズ2Nの配列が与えられる。サイズ2Nの昇順にソートされている配列から、与えれた配列に変更するための最小な操作数を求めよ。以下の操作を1とする。 先頭のN個と次のN個に分け、前者を集合A、後者を集合Bとする。 Aの要素とBの要素を交互に繰り返し…

SRM652Div1Easy

問題 2人で行う順列ゲームを考える。Aliceはxをはじめに選び、BobはサイズNの順列を選ぶ。 AliceはBobの選んだ順列を用いてf(x)を計算する。f(x)はf(1) = p[1]、f(m) = p[f(m-1)]で計算される。 Bobがどんな順列を選んできてもf(x)=1となる最小のxを求めよ。…