きままにものづくり

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

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)

コード

SRM573Div1Easy

問題

サイズNの配列が与えられる。Nは3の倍数である。プログラミングコンテストを考える。各要素はプログラマの実力を示し、はじめの3要素X,Y,Zが自身のチームメンバーである。チームの能力はmax(X,Y,Z)+min(X,Y,Z)で求まる。この能力より真に大きいチームは、自身のチームより高い順位となる。
この時の自身のチームの最悪の順位を求めよ。

解法

能力順にソートし、大きい要素と小さい要素で能力を比較することで答えが求まる。

計算量

O(N log N) (ソート)
O(N) (探索処理)

コード