t8m8-mem8

競プロとか、学んだことを書いていきます。

Topcoder SRM

SRM 672 Div1 Easy: Procrastination

問題 Procrastination 社員が無限にいる会社がある。 社員其々に1つずつタスクが割り当てられており、始めは社員番号x番の社員にタスク番号x番が割り当てられている。社員番号は1から無限に続く。 h時間経過すると、社員番号がhより大きいhの倍数の社員は、…

SRM 477 Div1 Medium: PeopleYouMayKnow

問題 友人関係friendsと人の番号person1,person2が与えられる friendsはN文字の文字列を値とするN要素配列で、i番目要素のj番目文字が'Y'のときはiとjが友人、'N'のときは友人でない。 あるAとBを決めた時に、AがBの友人であるときBはAの友人であるが、AとC…

SRM 396 Div1 Medium: FixImage

問題 白('.')と黒('#')のピクセルで構成されたテーブル(alteredImage)が与えられる。黒のピクセル同士が上下左右のいずれかで接しているとき、それらのピクセルは連結しているとする。連結した黒のピクセルの中から任意の2点を選んだとき、その2点のパスの長…

SRM 398 Div1 Medium: CountPaths

問題 r×cマスのテーブル上にいくつかの特別なマスがある。この特別なマスを踏んだ回数ごとに(1,1)から(r,c)への経路数を求める。 移動は(i,j)から(i+1,j)または(i,j+1)へのみ可能で、特別なマスは与えられた順番を戻るように踏むことはできない(i番目の特別…

SRM 399 Div1 Medium: BinarySum

問題 整数a,b,cが与えられる。それぞれを2進表現(no leading zeros)にしたあと桁数を一番大きいものに合わせて0で埋める。a,b,cのビットの順番を入れ替えたものをそれぞれa',b',c'としたときに、a'+b'=c'となる最小のc'を求める。解がなければ-1を返す。 制…

SRM 400 Div1 Medium: ReversalChain

問題 0と1から成る文字列initをgoalに変換する。できる操作は区間(i, j)の反転(ビットの反転ではなく、文字列の反転)のみで、これをr(i, j)と書く。 が与えられた時に が成り立つとき、これをreversal chainと呼ぶ。initをgoalに変換する際の最小のreversal …

TopCoder SRM 664 Div2 Hard : BearSorts

問題 TopCoder Statistics - Problem Statement 大小比較の際に、真偽が50%の確率でランダムに返ってくる恐ろしいマージソートがある。 入力として、このマージソートでソート済みの配列seqが与えられる。 [1,2..N]の配列をこのマージソートにかけたときに、…