ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

TopCoder SRM

TopCoder SRM 646 Div1 Easy : TheConsecutiveIntegersDivOne

概要N個の整数が与えられる。(N 整数の中から一つ選び1増減させる操作を複数回行うことができるとき、K個以上の連続した整数列になるためには最低何回その操作をする必要があるか求めよ。解法次のような処理で解いた。 ・N個の整数をソートさせる。 ・N個の…

TopCoder SRM 648 Div1 Easy : AB

概要以下の条件を満たす文字列が存在するか求めよ。・N文字 ・文字列sは'A'と'B'の2種類からなる ・s[i]=='A'かつs[j]=='B'となるペア(i,j)がK組ある (0 解法[2015/2/3:別解(動的計画法)を追加]== 貪欲 == 'A'と'B'のそれぞれの個数の積がK以上になるもの…

TopCoder SRM 647 Div1 Easy : BuildingTowersEasy

概要1~Nの建物を横一列に以下の条件で建てたい。(N・1番目の建物の高さは0 ・隣り合う建物の高さの差は1以内にする ・一部の建物について、x[i]番目の建物の高さはt[i]以下にするこのとき建物の高さの最大値を求めよ。解法建設条件の1,2つ目から、i番目の建…

【TopCoder】1つ上の色のコーダーになるために

初めにこの記事はCompetitive Programming Advent Calendar 2014の19日目の記事です。どうも、ぱーぽーです。 この記事では「TopCoderのアルゴリズム部門であるSRM(Single Round Match)で1つ上の色コーダーになるためにはどのようにすれば良いのか」につい…

TopCoder SRM 636 Div2 Hard : ChocolateDividingHard

概要 NxMの二次元グリッドがあり、縦横にそれぞれ3本ずつ線を引き16個に分割する。(N, M 各グリッドには0~9の数字が書いてあり、分割した領域内に書かれた数の和がその領域の得点になる。そしてその16個に分割された領域の中で最も得点が低いものが選ばれる…

TopCoder SRM 635 Div1 Easy : SimilarRatingGraph

概要 (問題文が個人的に読みづらいと感じた)日付とレートを軸とした折れ線グラフがあり、N個の点がプロットされている。 ある2つの区間にある折れ線を比較すると相似な関係になっている場合がある。そのような相似な関係にある折れ線のの中で最長の折れ線の…

TopCoder SRM 634 Div1 Easy : ShoppingSurveyDiv1

概要 N人がM種類の商品の中から買い物をする。 ・何種類でも買ってもいいし、買わなくてもよい。 ・ただし各商品はお一人様1つまでとなっていて同じ商品を複数買うことはできない。 ・K種類以上の商品を買った人はbig shopperと呼ばれる。M種類の商品をそれ…

TopCoder SRM 631 Div2 Medium : CatsOnTheLineDiv2

概要 ある直線上のN箇所にネコがいて、それぞれ座標position[i]にcount[i]匹ずついる。ネコは時間が1進むごとに以下の行動をとる。 ・その場にとどまる ・左に1進む ・右に1進む上記の行動をネコ達がtime回行ったときに同じ座標に2匹以上のネコがいない…

TopCoder SRM 629 Div1 Easy : RectangleCovering

概要 長方形の穴が開いていて、それを長方形の板で隙間なく埋める。 そのときに使う板の枚数の最小値を求めよ。各板の四隅は穴の外側にないとダメ。板同士は重なってもよい。解法 板を十字にして埋めていくのは意味がないので、板を縦または横向きに揃えて並…

TopCoder SRM 629 Div2 Medium : CandyMaking

概要 容積がcontainerVolume[i]である箱がN個あり、それぞれの箱にdesiredWeight[i]の重さの飴を入れたい。しかし飴の密度は1種類しか選ぶことができないので、全ての箱に希望通りの重さの飴が入れられるかどうか分からない。希望の重さと実際の重さの差の…

TopCoder SRM 633 Div2 Medium : Jumping

概要 二次元平面があり、(0, 0)から(x, y)へ移動したい。あらかじめ移動する距離リストが決められていて、それらを全て使って移動したときに目的地に辿り着けるか判定する問題。各移動先の座標は整数でなくてもよい。解法 TopCoder SRM 633 Div1 Easy : Peri…

TopCoder SRM 633 Div2 Easy : Target

概要 ##### # # # # # # # ##### ######### # # # ##### # # # # # # # # # # # # # # # ##### # # # #########↑みたいな感じのを出力せよ。というSRMではあんまり見ない感じの問題。解法 やるだけ問題。しかしどう実装するか悩んだ挙句、クソコードを書いて…

TopCoder SRM 633 Div1 Easy : PeriodicJumping

概要 二次元平面があり、(0, 0)から(x, 0)へ移動したい。1回の移動で移動できる距離 jumpLengths が与えられ、n種類の移動パターンがあり、i回目の移動で jumpLengths[i % n] 移動することができる。移動先の座標は整数でなくてもよい。移動にかかる最小回…

TopCoder SRM 626 Div2 Hard : NegativeGraphDiv2

概要 N個のノードとE本のエッジからなる有向グラフがある。各ノード間の移動にはコストがかかる時、ノード1からNに到達するための最短コストを求めよ。ただし、以下の操作をcharges回行うことができる。 ・ノード間のコストweightをweight*(-1)にする解法 (…

TopCoder SRM 631 Div1 Easy : TaroJiroGrid

概要 NxNの二次元グリッドが与えられ、各グリッドには"W"か"B"が書かれている。(Nは偶数)プレイヤーはある行を"W"か"B"で埋めることができる。各列で同じアルファベットがN / 2 + 1以上連続しないようにするとき、上記の操作を最低何回行えばいいかを求め…

TopCoder SRM 627 Div2 Hard : BubbleSortWithReversals

概要 数列Aが与えられる。 同じ要素が被らないように連続する要素をK回まで反転することができる。例えば、 A = {3, 2, 1, 5, 4}, K = 2のとき、 {3, 2, 1}と{5, 4}を選んで反転させると{1, 2, 3}と{4, 5}となり、数列Aは、A = {1, 2, 3, 4, 5}となる。この…

TopCoder SRM 626 Div1 Easy : FixedDiceGameDiv1

問題概要 1~bの値が書いてあるb面サイコロをa個持っているAさんと、1~dの値が書いてあるd面サイコロをc個持っているBさんがいる。二人がそれぞれ持っているサイコロを全て振って出た目の合計を比べるとき、AさんがBさんより大きい値になる期待値を求める問題…

TopCoder SRM 626 Div2 Medium : FixedDiceGameDiv2

解法・感想など (Div1のが分からなくて先にこっちをやってしまった)サイコロがお互い一つずつ所持しているので、お互いの出す目を全探索で調べて計算させればよい。ソースコード class FixedDiceGameDiv2 { public: double getExpectation(int a, int b) {…

TopCoder SRM 626 Div2 Easy : SumOfPower

解法・感想など O(n^2)で解いたがn 3重ループで区間の始点と終点を決めて計算させてもよい。ソースコード class SumOfPower { public: int findSum(vector <int> array) { vector<int> sum(array.size() + 1, 0); rep(i, array.size()) { sum[i + 1] = sum[i] + array</int></int>…

TopCoder SRM 627 Div2 Medium : HappyLetterDiv2

解法・感想など Div1の問題と少しルールが違う。 どんな順番で2種類ずつ削っていっても最後に残るアルファベットが全て同じかどうか判定する問題。全ての文字数に対してその過半数を占めているアルファベットがあればそれが必ず生き残るのでその判定をしてや…

TopCoder SRM 627 Div2 Easy : ManySquares

解法・感想など 正方形を何個作ることができるかを求める問題。4で割ればよい。ソースコード class ManySquares { public: int howManySquares(vector <int> sticks) { int count[1001]; memset(count, 0, sizeof(count)); rep(i, sticks.size()) count[sticks[i]</int>…

TopCoder SRM 627 Div1 Easy : HappyLetterDiv1

解法・感想など greedyにやっていく。アルファベットを2種類1つずつ除外していき、最終的に1種類だけ残すことができるかが分かればよい。まず残したいアルファベットを固定し、それ以外のアルファベットの中で出現数の多い2種類を1つずつ除外する。 除外を繰…

TopCoder SRM 628 Div2 Medium : BracketExpressions

解法・感想など 「Xは最大で5箇所しかこないからXに入る括弧の組み合わせは全部で6^5通りか、5重ループ書いちゃえ」とかやってすみませんでした。全探索で条件を満たしてるかどうか調べているだけ。stackを久々に使った感じする。 - 355.42 / 500ソースコー…

TopCoder SRM 628 Div2 Easy : BishopMove

解法・感想など 長ったらしく探索させているが、そんなことしなくてよい。斜め移動しかできないことが分かっているので、市松模様の同じ色にコマが置かれているかどうかが分かれば良い。 同じ色に置いてあれば最大でも2回以内に目的地に到達できる。 - 215.5…

TopCoder SRM 628 Div1 medium : CircuitsConstruction

解法・感想など (Easyよりmediumのほうが簡単に感じる)やや構文解析+greedyで解くことができる。入力データは木構造になっていて、根や節点にはAまたはB、葉にはXが入る。この問題では最大値を求めるので、とりあえず葉に1を入れて何枚の葉を使用するかを…

TopCoder SRM 628 Div1 Easy : DivisorsPower

解法・感想など 本番で解けなかったやつ。問題文読んだ瞬間、二分探索っぽい!って思ったが、1から順番にn^d(n)を列挙してみると n = 1: 1 n = 2: 4 n = 3: 9 n = 4: 64 n = 5: 25 n = 6: 1296 n = 7: 49 n = 8: 4096 n = 9: 729 n = 10: 10000 n = 11: 121 …

TopCoder SRM 620 Div2 Medium : PairGameEasy

解法・感想など (a, b)という状態から(a+b, b)または(a, b+a)と遷移させていくときに(c, d)にできるかどうか判定する問題。(c, d)から(a, b)に状態を戻すことを考える。 a > bのときは(a, b) -> (a - b, b)となり、 a (a, b - a)となる。ソースコード class …

TopCoder SRM 620 Div2 Easy : CandidatesSelectionEasy

解法・感想など 以下のコードでもシステムテストは通ったが、このコードはよくない点がある。標準ライブラリに搭載されているsortは不安定なソートであるため、stable_sortを使う必要がある。このソートは安定なソートである。ちなみにどちらのソートもO(nlo…

GooseTattarrattatDiv1 (SRM589 div1 easy)

解法・感想など 本番で解けなかったやつ、悔しい。回文を作る問題です。 文字xを文字yに変え、文字yを文字zに変えるような動作は行いません。 文字xを文字zに、文字yを文字zに、それぞれ独立して考えます。文字列を見ていき、回文にするために文字を変えなけ…

GUMIAndSongsDiv1 (SRM588 div1 easy)

解法・感想など 本番で解けなかったやつ。toneをソートさせてから動的計画法で解くことができます。 dp[歌った曲数][最後に歌った曲] := 最小時間 で解きました。 ソースコード class GUMIAndSongsDiv1 { public: int maxSongs(vector <int> duration, vector <int> to</int></int>…