2012-01-11から1日間の記事一覧

TopCoder SRM 328 Div1 Medium BlockEnemy

問題 n個の都市がn-1本の双方向に通行可能な道路によって結ばれている。 全ての都市のペアに対して、その都市同士を結ぶ道がただ一通りだけ存在する。 それぞれの道には、その道を破壊するコストが定められている。 occupiedTowns[]の都市を敵が占領した。 …

TopCoder SRM 329 Div1 Medium LogCutter

問題 長さLの丸太がある。 整数A,Kが与えられて、 この丸太を、 ( (A * i) mod (L - 1) ) + 1 (1≦i≦K)の位置で切ることができる。 丸太を最大でC回まで切ることができ、 丸太の最長の部分の長さを最小にするように切りたい。 最長の部分の長さの最小値およ…

TopCoder SRM 330 Div1 Medium PrefixFreeSubsets

問題 文字列の集合がprefix-freeであるとは、 どの文字列も、他の文字列の接頭辞となっていないことをいう。 空の文字列もprefix-freeである。 文字列の集合が与えられる。 この集合の部分集合(空集合および、元の集合そのものも含む)のうち、prefix-free…

TopCoder SRM 331 Div1 Medium Shopping

問題 n種類のコインがあり、それぞれの価値はvalues[i]である。 X以下の整数の値段を全ておつりなしで支払えるようにコインを持ちたい。 コインは最小で何枚持つ必要があるか、求めよ。 制約条件 n≦10 values[i]≦1000 X≦1000

TopCoder SRM 333 Div1 Medium RepeatedPatterns

問題 '0'または'1'からなる文字列P1,P2が与えられる。 文字列S(n)を、P1を100万回繰り返した後、P2をn回繰り返した文字列とする。 文字列Sを、S(1)+S(2)+……と無限につなげたものとする。 文字列Tを、Sの先頭から10^16文字を取った文字列とする。 Tにおいてゼ…

TopCoder SRM 334 Div1 Medium ExtendedHappyNumbers

問題 Nに対してSk(N)を、 Σ(Nの各桁)^kと定義する。 Nに対して、Nの幸福度を、数列N,Sk(N),Sk(Sk(N)),...,の最小値とする。与えられた整数A,Bに対して、 A≦i≦Bなるすべてのに対するiの幸福度の和を求めよ。 制約条件 A,B≦1000000 k≦6

TopCoder SRM 335 Div1 Medium ExpensiveTravel

問題 hxwのグリッドが与えられる。 グリッドのそれぞれには1〜9の数字が書かれている。 このグリッドの(startRow,startCol)を出発して、(goalRow,goalCol)へ行きたい。 一回の移動では、上下左右に何回か動くことができる。 ただし、一回の移動中に通ったマ…

TopCode SRM 336 Div1 Medium LikelyWord

問題 文字列が辞書順に並んだ辞書dictionary[]が与えられる。 k文字からなる単語を一つ、ランダムに生成する。 ただし、dictionaryの要素に一致するような単語は生成されない。 一致しない単語はすべて等確率で生成される。 生成した単語を辞書に入れるとき…