きままにものづくり

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

2014-11-01から1ヶ月間の記事一覧

SRM632Div1Easy

問題 整数をビット表現した際の右から0が連続する数の配列が与えられる。この配列の条件を満たしながら、実際の整数でも1ずつ増加してる数列を増加数列と定義する。 増加数列となる要素数を求めよ。 解法 増加数列には、あるパターンが存在する。 3 : 0 1 0 …

SRM631Div1Easy

問題 サイズNの各要素が'B'か'W'の2次元の配列が与えられる。各行に対して以下の操作が可能である。 全ての'W'を'B'にする 全ての'B'を'W'にする 列にN/2より大きく連続で同じ要素が並ばないようにするための最小の操作回数を求めよ。 解法 条件にひっかかる…

SRM633Div1Easy

問題 無限の平面とサイズNの数列が与えられる。数列の要素の値の距離だけジャンプができ、これを数列の順番通りに繰り返す。 (0, 0)から(0, x)へ移動するための最小のステップ数を求めよ。 解法 距離を半径とする円を考える。ジャンプを繰り返すことで円の幅…

SRM628Div1Medium

問題 サイズNの文字列とサイズMの数列が与えられる。文字列は'A','B','X'の3文字で構成され、'A'と'B'には以下の操作する。 'X'には数列の要素が入る。 'X'に適切に数字を割り当てることで返される最大の数字を求めよ。 解法 与えられる文字列からASTを構成…

SRM630Div1Medium

問題 ある文字列abcaのインデックスiに応じた接尾辞を考える。例としてs[0] = abca、s[1] = bcaとなる。 全ての接尾辞を列挙し、辞書順に並べ替えたインデックスをSAとする。abcaの場合は、SA = {3, 0 , 1, 2}となる。 SAとなる文字列の中で、最小の違う文字…

SRM629Div1Medium

問題 N個の飴の売店がある。飴には、N種類の形とN種類の味がある。各店は1種類の形で違う味の飴をそれぞれN1、N2個ずつ売っている。ひとつの味には2つの形が必ず存在する。 N種類全部の飴を手に入れるのに必要な飴の数を求めよ。 解法 ひとつの味には2つの形…

SRM616Div1Easy

問題 N個()のアラームが与えられる。各アラームは、にをの間隔で鳴らすようになっている。Alexは眠気指数Sを持っており、毎分Dずつ増えていく。これが0以下になると目覚める。Alexが起きることができる最大のSを求めよ。 解法 アラーム全体での周期を求め、…

SRM617Div1Easy

問題 長さN()のケーキが与えられる。Nの割れる数の人数が来ることは分かるが、正確な人数は分からない。来る人数に対して平等にケーキを分配するためにはいくつのピースに分けてケーキを切ればいいか求めよ。 解法 割れる数の倍数の集合を求めると、その集合…

SRM618Div1Easy

問題 サイズN()のグラフが与えられる。各ノードは2つの親を持つか、何も持たないかである。全ての親の性別が男性と女性で分けられる場合は、グラフはFamily treeとなる。与えらたグラフがFamily treeかどうか判別せよ。 解法 二部グラフ判定を行うことで、答…

SRM619Div1Easy

SRM

問題 二人のプレイヤーがいて、サイズN()の数列が与えられる。交互に配列に対して操作を行い、操作ができなくなったプレイヤーが負けとなる。操作は以下となる。 2以上の値を持つ要素を選ぶ この要素を空ではない2つの要素に分割 最初に選んだ要素を含まない…

Morris in-order traverse

コード テスト

SRM620Div1Easy

SRM

問題 (a, b)と(c, d)の2組の数字のペアが与えられる。任意のペア(x, y)を考える。可能な操作は(x+y, y)または(x, x+y)である。(a, b)と(c, d)が作れる(x, y)のペアを求め、その中でx+yが最大となるペアを求めよ。作れない場合は-1を返す。 解法 (a, b)または…

SRM621Div1Easy

問題 平面の上に中心点が、半径がの円がN個存在する。平面の中心(0,0)から半径rの円を新しく描く。rは[0,Z]の中からランダムに選ばれる。この時、新しく描く円が既に存在するそれぞれの円と全く被らないか、全て被る場合は良い円とする。逆に、一部だけ被っ…