ちゃっくのメモ帳

ちゃっくがメモしときたいことをメモしとくよ

Topcoder

SRM 762 Div1 Easy LexicographicPartition

問題概要 community.topcoder.com長さAの数列nを連続部分列に分解する。 ただし、連続部分列に含まれる要素の合計は正にならなくては行けない。 この時、Aの連続部分列を前から長さを見た数列をBとする。 辞書順最小のBを求めよ。 解法 前から貪欲するだけ。…

SRM 736 Div2 Med ReRoll

問題概要 サイコロがN個ある。そのN個の目は配列Aで渡される。 Aのうち幾つかのサイコロを振り直して、その合計値をtargetにしたい。 最小で幾つのサイコロを振り直せば合計値がtargetになる可能性があるか? 解法 sum(A) = targetならば0個 sum(A) sum(A) > …

SRM723Div1Easy TopXorer

概要 要素数nの配列xが与えられる。 に対してを満たすような配列aに対して の最大値を求めよ 解法 基本的に最大の数の最上位bitを1にして、残った数でそれ以下のbitを1にしていくみたいな気持ち。例えば1100,0100があれば1100->1100,0100->0011にすれば排他…

SRM 700 Div1 Easy FindingFriend

問題 TopCoder Statistics - Problem Statement 解法 (2017/4/29:解き直したので下にちょっと付け足す.解法を確認するなら下に追記した部分を読んだほうがよい) leader[i]がfriendPlaceよりも大きい場合、部屋i以降はleader[i]以上のランクの人だけで調整し…

SRM699 Div1 Easy OthersXor

問題 TopCoder Statistics - Problem Statement要はN個の数字があり入力x[i]にはi番目の数字以外の数字のxorを取ったものが入っている。 入力xを満たすようなN個の数字の組み合わせのうち合計が最小となるようなものを見つけその最小値を求める(ただしそのよ…

TCO2016Round2C Easy BearBall

TCO2016Round2C Easy BearBallの解き方 問題 N個の点がある。 N個の点から始点と終点を選ぶ方法はN*(N-1)通り。 この全ての始点と終点の組み合わせについて、始点から終点に向かってボールを飛ばしたい。 ただし、点1と点2の間に点が存在しなければコスト1で…