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という目…

SRM 625 Div2 Medium IncrementingSequence

問題 SRM 625 - TopCoder Wiki N個の要素からなるシーケンスが与えられた時,シーケンスを修正して1..Nのシーケンスを作りたい. 可能な修正は与えられたkを任意の要素に任意の回数を足す. 1..Nのシーケンスを作れるかどうか判定する問題 解答 足すだけなの…

SRM 624 Div2 Medium BuildingHeightsEasy

問題 SRM 624 - TopCoder Wiki 色々な高さの建物がある時に,同じ高さの建物が最低M個出来るように 建物の高さを増設したい. 増設しなくてはいけない高さの最低の数を求める問題. 解答 増加だけしか出来ないので,既存の建物の何れかの高さに合わせるよう…

SRM 623 Div2 Medium CatAndRat

問題 SRM 623 - TopCoder Wiki 半径Rの円のチューブがある. ねずみはこのチューブの任意の方向にVratの速度で移動する. ねずみがチューブの中に入ってT秒後,猫もネズミが入ったのと同じ場所から入って, 同じようにVcatの速度で移動する. ねずみは猫から…

SRM 622 Div2 Medium BoxesDiv2

問題 SRM 622 - TopCoder Wiki candyを2xのサイズの箱に入れる. 異なる種類のcandyは異なる種類の箱に入れなくてはいけない. 箱2つは,その2つがすっぽり入るようなより大きい箱に入れることが出来る. 最終的に1つの箱にすべていれこむ時の最小の箱の…

SRM 621 Div2 Medium NumbersChallenge

問題 SRM 621 - TopCoder Wiki 整数配列が与えられた時,A君は任意の数字を思い浮かべる,B君はA君が思い浮かんだ数字を与えられた整数配列の数字を抜き出し足し合わせることで作る. B君が作ることの出来ない最小の数を求める問題. 解答 入力シーケンスサ…

SRM 620 Div2 Medium PairGameEasy

問題 SRM 620 - TopCoder Wiki 二つの数のペア(x,y)が与えられた時,このペアから(x+y, y)もしくは(x, x+y)に変換できる. このとき,(a, b), (c, d)が与えられた時,(a, b)を上記の操作を繰り返して(c, d)に変換できるかを判定する問題. 解答 やるだけ. …

SRM 619 Div2 Medium ChooseTheBestOne

問題 SRM 619 - TopCoder Wiki N人を円上の椅子に座らせる.ステップiでi3番目の人を円から外す. 次のステップは外された人の次の人から始める. 最後に残った人を答える問題. 解答 本当に愚直にシミュレーションすると,N=5000の時,最後には49993の移動…

SRM 618 Div2 Medium LongWordsDiv2

問題 SRM 618 - TopCoder Wiki 次の性質を満たす文字列が好き. 与えられた文字列が好きかどうかを判定する問題. 全て大文字 同じ文字が連続しない 同じサブシーケンスが出現しない,xyxyとならない. 解答 入力長が100なのでサブシーケンスとなりえるペア…

SRM 617 Div2 Medium SlimeXSlimonadeTycoon

問題 SRM 617 - TopCoder Wiki i日目の朝にmorning[i]だけのSlimonadesを生産でき,customers[i]の顧客がSlimonadesを求めに来る. i日目の朝,i-stale_limit日前に生産されたSlimonadesは腐っていて廃棄しなくてはいけない. N日間に売ることの出来る最大の…

SRM 615 Div2 Medium LongLongTripDiv2

問題 SRM 615 - TopCoder Wiki 距離1もしくは距離Bにジャンプできる時, 1方向のみT回ジャンプして距離Dに到達できるかどうか判定する問題. 解答 距離Bのジャンプの回数によって到達できる距離は単調増加に伸びる. そのため,距離Bのジャンプの回数を二分…

SRM 614 Div2 Medium MinimumSquareEasy

問題 SRM 614 - TopCoder Wiki N個の2次元平面上の点が与えられる. これらのうちN-2の点を完全に内包する正方形を考える. そのような正方形の最小面積を求める問題. 解答 N-2の選び方は,何を選ばないかということと同じなので, 選ばない点を求め,最小…

SRM 612 Div2 Medium EmoticonsDiv2

問題 SRM 612 - TopCoder Wiki 絵文字をx個作りたい,初期状態で1個の絵文字が表示されている. 行える操作は以下 今表示されている絵文字を全てクリップボードにコピー クリップボードの絵文字を追加 必要な総和数を返す問題. 解答 シミュレーションすれば…

SRM 610 Div2 Medium TheMatrix

問題 SRM 610 - TopCoder Wiki 2次元平面上に01が書かれたボードが与えられるので この中に含まれるチェスボードの最大面積を求める問題. ここでチェスボードとは隣り合うセルが自セルと違う数字のこと. 解答 入力は100x100,チェスボードも100x100なので…

SRM 664 Div2 Medium BearPlaysDiv2

問題 3つの数字があって2つの数字A, Bを選ぶ,小さい方の数を大きい方から持ってくる(A + A, B- A). この作業を繰り返して3つの数字が等しくなるかどうかを判定する問題 解答 入力の3つの数は高々500. 順序は無視して良い,かつ操作の数が限定されていると…

SRM 608 Div2 Medium MysticAndCandiesEasy

問題 SRM 608 - TopCoder Wiki 箱のなかにキャンディが入っている,個々の箱にいくつキャンディが入っているか知ることは出来ないが, 箱iのなかに入っている可能性のあるキャンディの最大数high[i]と,全ての箱のなかに入っているキャンディの総数Cを知るこ…

SRM 606 Div2 Medium EllysNumberGuessing

問題 SRM 606 - TopCoder Wiki Aさんがある数を思い浮かべて,Bさんがその数を予想する.AはBが指摘した数と自分が思い浮かんだ数の差を答える. 複数回,この試行をした時,Aが思い浮かべた数がわかるならその数を分かるならその数を,複数あるなら-1を,A…

SRM 605 Div2 Medium AlienAndGame

問題 SRM 605 - TopCoder Wiki 2次元配列の各セルが黒白で塗られている. 今任意の行のセルの色を反転できる時, 作ることの出来る最大の白色の正方形の面積を求める問題. 解答 まず白の正方形を作るという作業は,操作で反転できるので特に意味は無い. …

SRM 604 Div2 Medium PowerOfThreeEasy

問題 SRM 604 - TopCoder Wiki 2次元平面上の(0, 0)地点にいる. 各kステップにおいて(0ステップから始まる) y軸方向x軸方向のどちらかに3k移動する. (x, y)が与えられた時,到達可能かどうかを判定する問題 解答 全探索. 各ステップで必ずx, yのどちら…

SRM 598 Div2 Medium BinPackingEasy

問題 SRM 598 - TopCoder Wiki 容量が101から300の商品が与えられた時,これらの商品を複数の容量300の瓶に詰め込むことを考える. 全て詰め込むのに必要な最小に瓶の数を答える問題 解答 入力の商品の容量が101から300というのがポイント. つまり最適に詰…

SRM 597 Div2 Medium LittleElephantAndString

問題 SRM 597 - TopCoder Wiki ある文字列Aをある文字列Bに変換する. 変換方法は任意の位置の文字を一番左に持ってくる. 最小の変換コストを答える問題. もし変換不可能であれば-1を返す. 解答 操作の順番を考えるとややこしいので,操作の話を一旦脇に…