TopCoder

SRM 676 Div2 Medium BoardEscapeDiv2

問題 SRM 676 - TopCoder Wiki 二次元ボード上のゲームを考える. どんなゲームかは説明が面倒なので略. 解答 このゲームは2手読めば,どちらが勝つか分かる. 初期状態でどこにも動けない.Bobの勝ち. k=1.Aliceの勝ち 出口に隣接しないセルに動ける.か…

SRM 675 Div2 Medium ShortestPathWithMagic

解けなかったので解説見ながら写経 問題 SRM 675 - TopCoder Wiki n個の点と各頂点から各頂点までの距離が与えられる. k個のポーションを持っており,ポーションを使うと,ある頂点からある頂点までの距離が半分になる. 任意の枝でポーションは高々1回しか…

SRM 673 Div2 Medium BearSlowlySorts

問題 SRM 673 - TopCoder Wiki 要素Nの配列をソートする,今N-1個の連続する要素は1回の操作でソート可能. 全体の配列をソートするのに必要な最小の操作回数を求める問題. 解答 パターン分けをすると幾つかの場合が考えられる. 既にソートされている.操…

SRM 672 Div2 Medium SubstitutionCipher

問題 SRM 672 - TopCoder Wiki 大文字からなる文字列について,ある文字をある文字へと変換する変換テーブルで違う文字列へと変換する. 今,変換後の文字列yと部分的な変換テーブルが与えられる. 元の文字列が分かるならその文字列を,分からないなら空文…

SRM 671 Div2 Medium BearDartsDiv2

問題 数値列が与えられた時に abc=dとなる(a<b<c<d)組み合わせの数を求める問題. 解答 愚直にやるとO(n4)の組み合わせを検証する 要素数が500なのでO(n4)は厳しい num[i][j]をw[i]がj..nにいくつあるのかを予め計算しておく 位置ai,bi,ci(ai < bi < ci)のO(n3)の組み合わせについて,条件が成り立つdの個数はnum[w[ai]w[bi]w[ci]]となるので,これを計算する class BearDartsDiv2 { public: long long count(vector <int> w) { int limit = 1000000…</b<c<d)組み合わせの数を求める問題.>

SRM 670 Div2 Medium Drbalance

問題 SRM 670 - TopCoder Wiki +と-からなる文字列を考える. ある文字列のスコアは+の数から-の数を引いた数で表される. 今,ある文字列のnegativityをその文字列のprefixの内,スコアが負になる数とする. ある文字列とkが与えられた時に,任意の位置の-…

SRM 669 Div2 Medium CombiningSlimes

問題 SRM 669 - TopCoder Wiki 複数のスライムが与えられた時に,任意の2個のスライムを合体させ,スライムの個数が1つになるまで繰り返す. 各スライムはサイズが与えられ,サイズx, yのスライムを合体させると,x+yのスライムが出来,x*yのスコアを得る. …

SRM 667 Div2 Medium OrderOfOperationsDiv2

問題 SRM 667 - TopCoder Wiki ある計算機を実行する時の最小の実行時間を求める問題. 命令はn個あり,s[i][j]はi番目の命令がj番目のメモリを使うことを意味する. メモリはキャッシュすることが出来,命令iの実行時間はキャッシュされていないメモリの個…

SRM 666 Div2 Medium GoodString

問題 SRM 666 - TopCoder Wiki 文字列"ab"を既存の文字列の任意の位置に挿入する,この操作を繰り返して得られる文字列を"Good"とする. 任意の文字列が与えられた時,その文字列が"Good"か否かを求める問題. 解答 Goodな文字列はabを繰り返し挿入すること…

SRM 661 Div2 Medium BridgeBuildingDiv2

問題 ノードが2列に並んでいて,各列はN個のノードが一直線に並んでいる. 一直線に並んだN個のノードのi番目のノードとi+1番目のノードは間隔がa[i]とb[i]の枝で接続されている. (aは一列目,bは二列目に対応). 今,一列目と二列目の同じインデックスの…

SRM 670 Div2 Medium Drbalance

問題 plus/minus文字列とは'+'と'-'だけで構成された文字列のこと. ここで'+'の個数から'-'の個数を引いた数をスコアとする時. 与えられた文字列のプレフィックスのスコアが負となる場合の数を考える. この数が高々kになるように文字列を'-'から'+'に編集…

SRM 659 Div2 Medium PublicTransit

問題 R行C列の2次元平面上にいて,隣接するセルに移動できる. ある点からある点に即座に移動できるテレポート地点を1つだけ作ることが出来る. 任意のポジション間の最短距離の最大をDとすると, Dの最小値を求める問題. 解答 0 <= R, C <= 10と小さいの…

SRM 656 Div2 Medium RandomPancakeStackDiv2

問題 SRM 656 - TopCoder Wiki パンケーキが並んでいて,i番目のパンケーキは(i+1)の幅があり, その美味しさはd[i]で表される. これらのパンケーキを以下の手順で選んでいったとき, 選んだパンケーキの美味しさの総和の平均を求める問題. パンケーキがな…

SRM 655 Div2 Medium FoldingPaper2

問題 SRM 655 - TopCoder Wiki 幅W,高さHの長方形が与えられる. 今,外周の辺に平行な整数の位置で長方形を折り曲げることが出来る時, 与えられた面積Aにすることが出来る,折り方の最小手数を求める問題. もし,そのような折り方がなければ-1を返す. …

SRM 653 Div2 Medium RockPaperScissorsMagicEasy

問題 SRM 653 - TopCoder Wiki じゃんけんをして勝ったら1ポイント,負けかアイコだったら0ポイントを得る時, 各ステップiで相手がcard[i]を出した時トータルのスコアがscoreとなる時の手数を答える問題. 解答 相手の手順が何でも,こちらは任意の手を選ぶ…

SRM 651 Div2 Medium FoxAndSouvenirTheNext

問題 今回は解説リンクが開けなかったのでリンクはなし. 価値value[i]の品物がn個与えられた時,品数が等価で, 価値の総和が等価な2分割が出来るかどうかを判定する問題. 解答 典型的なDPの問題. value[i]の総和をsumとするとsumあるいはnが奇数の時は等…

SRM 650 Div2 Medium TaroFillingAStringDiv2

問題 SRM 650 - TopCoder Wiki A, B, ?からなる文字列が与えられる. ?をA, Bに置き換えてAAとBBの数を極力少なくしたい. 最小のAAとBBの数の和を答える問題. 解答 問題の性質として?が連続する区間は?の連続をABAB・・・かBABA・・・のどちらかに置き換え…

SRM 647 Div2 Medium TravellingSalesmanEasy

問題 SRM 647 - TopCoder Wiki あるセールスマンはcity[i]だけで売ることが出来るprofit[i]の利益が出る商品を持っている. 今visit[i]の街を訪れることが確定している時,最大の利益を答える問題. 解答 Easyかと疑うレベル 訪れる街で売れる商品の一番利益…

SRM 646 Div2 Medium TheGridDivTwo

問題 SRM 646 - TopCoder Wiki 2次元平面上の(0, 0)にいる. 1秒で上下左右のどちらかに移動できる. 移動できないポイントがブロックリストとして与えられている. k秒で到達できる最大のx座標を答える問題 解答 移動方法は沢山あるが,ブロックリストは高…

SRM 645 Div2 Medium ConnectingCars

問題 SRM 645 - TopCoder Wiki 1つのレールの上に複数の車が並んでいる. 各車はpositions[i]に位置し,そこから右方向にlengths[i]の長さだけ車体が伸びている. いま,この車を隙間なく並びたい,各車体の位置を左右どちらかに1だけ移動するコストが1とす…

SRM 644 Div2 Medium LostCharacter

問題 小文字と'?'からなる,文字列リストが与えられる. '?'は任意の文字に置き換えられ,文字列のpositionは全ての文字列の中での辞書順位と定義される. 与えられた文字列リストの'?'を任意の文字に置き換え,positionに変換する時, 辞書順が最小となるpo…

SRM 642 Div2 Medium LightSwitchingPuzzle

問題 SRM 642 - TopCoder Wiki N個のライトが一列に並んでいて,onとoffの状態がある. i番目のライトのスイッチを押すとi,2*i,3*iのライトも同時にon, offが切り替わる. 今,全てのライトを消したい時,スイッチを押す最小回数を求める問題. 解答 1番目…

SRM 639 Div2 Medium AliceGameEasy

問題 SRM 639 - TopCoder Wiki A君とB君がそれぞれのターンでゲームをする,iターン目で勝った方はiポイントを得る. 今A君がxポイント,B君がyポイントを得た時,A君が勝った最小ターンを答える問題. 解答 何回ターンが出来たかが分かれば,半分問題は解け…

SRM 638 Div2 Medium NarrowPassage2Easy

問題 SRM 638 - TopCoder Wiki 狼が狭い路地に一列に並んでいる. 各狼のサイズがsize[i]で与えられていて, 隣接する狼のサイズの和がmaxSizeSum以下なら,入れ替わることが出来る. 狼の並び方の異なり数を答える問題. また,サイズが同じでも狼同士も区…

SRM 637 Div2 Medium PathGameDiv2

問題 SRM 637 - TopCoder Wiki 2行しかないチェスボードを考える(列は1以上). 各セルは黒か白に塗られていて,一番左のセルから一番右のセルまで白のセルを辿って到達できる. 移動は上下か横の隣接する白セルにのみ移動できる. この性質を保ったまま,…

SRM 636 Div2 Medium SortishDiv2

問題 SRM 636 - TopCoder Wiki シーケンスSが与えられた時S[i] < S[j] (i < j)となる数をsortednessと呼ぶ. ある,sortednessといくつかの数字が抜けたシーケンスSが与えられる. 本来,Sは1から|S|の要素からなる.今S[i]=0を任意の数字に置き換えれる時,…

SRM 635 Div2 Medium QuadraticLaw

問題 SRM 635 - TopCoder Wiki 教師が授業にx分遅れるとx2分予定より早く講義を終えなければならない. 沢山遅れると,ついた瞬間に授業が終わるという場合も考えられる. 授業時間dが与えられた時,授業をすることができる,最大の遅刻時間を求める問題. …

SRM 634 Div2 Medium ShoppingSurveyDiv2

問題 SRM 634 - TopCoder Wiki 問題を説明するのがちょっと難しい. N人がM個の商品についてレビューする. s[i]は商品iについて好意的に評価している人の数を表す. 全ての商品について好意的に評価している人をbig shopperと呼ぶ. 考えられる場合の内,bi…

SRM 633 Div2 Medium Jumping

問題 SRM 633 - TopCoder Wiki 二次元平面上の(0, 0)の位置にいて,jumpLengths[i]の距離だけジャンプする. 与えられた(x, y)に到達できるかを判定する問題. 解答 解説がとても分かりやすいのでまずは,そちらを見たほうが良い. 感覚的に正解となる条件は…

SRM 626 Div2 Medium FixedDiceGameDiv2

問題 SRM 626 - TopCoder Wiki Aliceは1からaまでの目があるダイスを,Bobは1からbまでの目があるダイスを持っている. 大きい方の目が出たほうが勝ちとする. Aliceが勝ったことがわかった時,Aliceが出した目の期待値を求める問題. 解答 Aliceがxという目…