2016-01-18から1日間の記事一覧

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の実行時間はキャッシュされていないメモリの個…