Topcoder

Topcoder SRM 711 Div.1 Easy - ConsecutiveOnes

問題概要 整数n, kが与えられる。n以上の整数のうち、2進表現で1がk個続く部分を持つような数で最小のものを求めよ。 0 <= n < 250 k <= 50 解法 1がk個続く箇所を全探索する。1が続く箇所より上位の桁はnと同じになるよう埋めるのが最善。より下位の桁は、…

Topcoder SRM 712 Div.1 Easy - LR

問題概要 N要素の数列S, Tが与えられる。Sに対してLとRという2種類の操作を行うことができる。操作の結果SをTに等しくできるか判定せよ。できるならば具体的に操作の列をひとつ示せ。なおTに等しくできる場合、操作の回数は100回以下になることが証明できる…

Topcoder SRM 714 Div.1 Easy - ParenthesisRemoval

問題概要 開き括弧と閉じ括弧のみからなる文字列Sが与えられる。初めSの括弧は正しく対応している。Sの一番前にある開き括弧と任意の閉じ括弧のペアを括弧の対応が不正にならないよう取り除く、という操作をSが空になるまで繰り返すとき、括弧の選び方の順番…

Topcoder SRM 715 Div.1 Easy - MaximumRange

問題概要 初期値0の変数Xがある。+1と-1が並んだ命令列が与えられ、前から順番にその命令をXに適用するか無視するかを自由に選択できる。この過程において作れるXの最大値と最小値の差の最大値を求めよ。 解法 +と-の数を数えて大きい方を取る 感想 問題概要…

Topcoder SRM 722 Div.1 Easy - TCPhoneHome

問題概要 あるシステムにおいて、電話番号の桁数はNである。またこのシステムでは特定の接頭辞がついた電話番号はすべて「特別な番号」として予約されている。Nと接頭辞の集合Sが与えられるので、特別でない番号が何通り存在するか求めよ。 1 <= N <= 17, 0 …

Topcoder SRM 719 Div1 Easy - LongMansionDiv1

問題概要 N行無限列の2次元グリッドがある。各行にはコストが設定されており、その行のマスに1回乗るたびに毎回そのコストがかかる。移動の開始点と終了点が与えられるので最小のコストを求めよ。 N <= 50 解法 開始行→経由行→終了列→終了行という感じで移動…

Topcoder SRM 720 Div1 Medium - DistinctGrid

問題概要 与えられる整数n, kに対して、各行・各列をみたとき異なる数がちょうどk個存在するようなn * nのグリッドを構成せよ。解が複数ある場合は使われる数の種類が最大になるものを答えること。 3 <= n <= 50 1 <= k <= n/2 解法 1 2 3 0 0 0 0 4 5 6 0 0…

Topcoder SRM 720 Div1 Easy - SumProduct

問題概要 0~9の各数字について、それぞれを何回まで使ってよいかを示した配列amountが与えられる。amountの制限を守って桁数がblank1の非負整数A, blank2の非負整数Bをつくるとき、ありえるA, Bのすべての組合せにおけるA*Bの総和を求めよ。 max(amount) <=…

Topcoder SRM 721 Div1 Medium - GraphAndPairs

問題概要 整数d, kが与えられる。最短距離がdであるような頂点のペアがちょうどk個あるような無向グラフを構成せよ。ただしすべての辺の距離は1とし、辺・頂点とも最大で1000個までとする。 2 <= d <= 50 1 <= k <= 50000 解法 (D-1)個の頂点を一直線につな…

Topcoder SRM 721 Div1 Easy - RememberWords

問題概要 ある連続した期間の前半d1日で合計w1個の単語を覚え、後半d2日で合計w2個の単語を覚えたい。任意の連続する2日間において覚える単語の数が高々1しか変わらないように単語を覚えるという制約のもとで、このような単語の覚え方が可能か判定せよ。 d1,…

Topcoder SRM 718 Div1 Easy - InterleavingParenthesis

これまで全然やっていなかったSRMの過去問埋めをぼちぼちやっていこうという気持ちになりまして、せっかくだから解いた問題に関しては記録をつけていこうと思います。当面はDiv1 Easyを新しいものからやっていく予定です。この1回で飽きる可能性もありますが…