きままにものづくり

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

SRM585Div1Easy

問題

高さNの二分木が与えられる。すべてのノードに車が通るようにするためには、最小でいくつの車が必要か求めよ。
ただし、車は他の車も含め一度通ったノードをもう一度通ることはできない。

解法

動的計画法で求まる。
f(n) = f(n-1) + 2f(n-2)
一番外側のノードを一台の車に走らせると、n-2までの二分木が2個ずつできあがる。このまま、計算すると O(N^2)となってしまうので、一つ前の要素を用いて O(N)にする。

計算量

O(N)

コード

SRM586Div1Easy

問題

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

解法

yに小数点をとることも可能なので、Yのすべての要素に2をかける。
Y[x]、Y[x]+1、Y[x]-1となる平行線を引き、すべてのxに対して調べることで答えが求まる。

計算量

O(N)

コード

SRM587Div1Easy

問題

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

解法

badStepはひとつしかないので、もしbadStepを通るようだったら、-1をすれば最大の答えが求まる。

計算量

O(N)

コード

SRM588Div1Easy

問題

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

解法

toneの範囲を指定し、その中でdurationが短いものから順に選択していく。toneの範囲を与えられた曲の組み合わせで全探索することで答えが求まる。

計算量

O(N^3 log N)

コード

SRM589Div1Easy

問題

サイズNの文字列が与えられる。与えられた文字列を回文にするのに最小な時間を求めよ。
許される操作は、以下である。
任意の2つの文字A,Bを選択し。すべての文字AをBに変更する。この時、ひとつの文字を変更するのに1秒かかる。

解法

同じ文字と反対側にある文字をひとつのグループとし、その中で最多の文字に他の文字を変更する。

計算量

O(N)

コード

SRM590Div1Easy

問題

サイズNの配列beginとtargetが与えられる。要素は'.','L','R'のいずれかである。'.'は空を示し、'L'は左に移動できる駒、'R'は右に移動できる駒を示す。
beginの状態からtargetの状態に遷移可能か求めよ。

解法

各要素の位置情報を比較することで、答えが求まる。

計算量

O(N)

コード