ferinの競プロ帳

競プロについてのメモ

SRM

SRM 636 div1 easy ChocolateDividingEasy

解法 二次元累積和を計算しておくと矩形の範囲の値の総和をO(1)で計算できる。あとは切る位置を全通り試すO(H^2W^2)をすればよい。 #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<ll> VL; typed</ll></vi></int></bits/stdc++.h>…

SRM635 div1 easy SimilarRatingGraph

解法 i,jから始まる部分列について同型である直線の長さを考える。各区間について傾きが等しく、比率が等しいならば同型であると判定できる。 i+k→i+k+1、j+k→j+k+1の線分について傾きが等しく、day[i+k+1]-day[i+k] と day[j+k+1] - day[j+k] の比率が等し…

SRM634 div1 easy ShoppingSurveyDiv1

概要 M種類の品物を売っている店でN人の人が買い物に来た。同じものを2つ以上買った人はいない。商品iが売れた数はS[i]である。このとき、K個以上の商品を買った人を大口顧客と呼ぶ。このとき、大口顧客の最少人数を求めろ。 解法 できるだけ大口顧客の数を…

SRM632 div1 easy PotentialArithmeticSequence

概要 正の整数列であるaがある。aは与えられず、d[i] = (a[i]の末尾の0が連続する数) である数列dが与えられる。この数列の部分列で、a[i]が1ずつ増加していく部分列はいくつ存在するか求めろ。 解法 2^6 = 64、n <= 50 から部分列においてd[i] = 6が二つ以…

SRM631 div1 easy TaroJiroGrid

概要 各マスが黒か白に塗られているn*nの二次元グリッドが与えられる。同じ色がN/2マスより長く連続している列が存在する時、そのグリッドはだめなグリッドである。操作を繰り返すことでだめなグリッドを解消したい。このとき最小の操作回数を求めろ。なお、…

SRM630 div1 easy Egalitarianism3

概要 n頂点の重み付きの木が与えられる。集合の任意の2頂点の距離が等しくなるような頂点集合のうち、集合の要素数の最大を求めろ。 解法 ある頂点を根とした木で根からの距離を考える。根からの距離が等しい2頂点a, bでaとbのLCAが根であるような頂点であれ…

SRM629 div1 easy RectangleCovering

概要 holeH、holeWの大きさの穴を複数の板を使って塞ぐ。板iの大きさはboardH[i]、boardW[i]である。板は重なっても良いが全ての角が穴の外に位置していなければならない。このとき塞ぐのに必要な最小枚数を答えろ。不可能なら-1を答える。 解法 holeH >= bo…

SRM628 div1 easy DivisorsPower

概要 d(n) = (nの正の約数の個数)、h(n) = n^d(n)とする。x = h^-1(n) を求めろ。複数存在する場合は最も小さいものを求めろ。 解法 d(x) として使われうる値は20程度までしか存在しない。d(x)を決め打って、そのd(x)のときh^-1(n)が存在するか考える。nのm…

SRM626 div1 Easy FixedDiceGameDiv1

概要 Aliceはa個のb面ダイス、Bobはc個のd面ダイスを投げる。このとき、ダイスの目の合計が大きい方を勝ちとする(引き分けはどちらの勝ちでもない)。Aliceが勝つことがありえないときは-1を出力しろ。そうでないときはAliceが勝った条件下でAliceのダイスの…

SRM726 div2 med TurtleGame

概要 2次元グリッド上で亀が左上のセルから右下のセルに右か下への移動を繰り返して移動する。グリッド上には障害物があり亀は通ることができない。このグリッドを用いて2人でゲームを行う。各プレイヤーはそれぞれの手番でグリッド上に障害物を配置する。こ…

SRM726 div2 easy StringHalving

概要 英アルファベットから成る文字列Sが与えられる。文字列Sは同じ種類の文字を2個ずつ含んでいる。この文字列Sを同じ種類の文字が1個ずつになるように文字を消去する。辞書順最小になるときに文字を消去したとき、文字列の最初の文字を出力しろ。 解法 辞…

SRM625 div1 easy PalindromePermutations

解法 まず、回文が存在する条件として * それぞれの文字種の個数が全て偶数 * 一つの文字種だけ奇数でそれ以外は偶数 のいずれかの条件を満たす必要がある。文字種ごとに文字列内の個数を数え、奇数のものが2個以上あれば存在しないので0を出力する。 cnt[i]…

SRM624 div1easy BuildingHeights

考えたこと 題意がよくわからなかったのでサンプルを試してみると、同じ高さのビルをi個(1<=i<=N)つくるために必要なコストをA[i]としたとき、A[1]^A[2]^…A[N]を出力すればよさそう。離れた階層のビルの高さを同じにする利点はないのでソートして考える。 dp…

SRM623 div1easy UniformBoard

考えたこと PをAに置き換えるためにはPをどこか別の空マスに移し、Aをどこかから持ってくるため2手かかる。.をAに置き換えるためには1手かかる。 ある長方形の範囲を条件を満たす範囲とできるかを考える。Aが2個、Pが1個、.が1個ある範囲を全てAに置き換える…

SRM621 div1 easy RadioRange

考えたこと 中心が(0, 0)で半径がrの円と中心が(X, Y)で半径がRの円が共有する部分を持つ条件について考える。半径rが (2円が外接する半径r_1)<= r < (2円が内接する半径r_2)の条件を満たすときと言い換えられる。 r_1 = max(0, sqrt(XX+YY)) (円の中に(…

SRM619 div1easy SplitStoneGame

考えたこと ゲームで石の山だしgrundy数かなあと思いつつ問題文を読む。敗北条件を考えると石の数が1個以下の山しか存在しない場合か山が2個以下しかない場合になる。サンプルを読んでいると山の石の数は2個以上か1個の2パターンしか考慮しなくていいことに…

SRM618 div1 easy Family

考えたこと サンプルのグラフを書いてみると、parent1[i]とparent2[i]が2つの異なる値で分類できれば可能であると判定できそうなことに気づく。これはparent1[i]とparent2[i]をつないだグラフが2部グラフであるかどうか判定すればできる。提出したら通った。…

SRM617 div1 easy MyLongCake

概要 長さnのケーキがあり友人に配るためケーキを切っておきたい。友人には同じ長さの連続したピースのケーキを渡せるようにしたい。来る友人の人数はn以外のnの約数の人数ということしかわかっていない。この条件を満たすような最小のピースの数を出力しろ…

SRM 712 div2 med RememberWordsEasy

考えたこと O(max(d_1,d_2)max(w_1,w_2))で愚直にDPするのは無理。考察の方針が思い浮かばなかったのでとりあえず手で試してみる。区間の端を0単語とすると1~d1までの和の単語数までは全て実現することが可能そう。区間の端を決め打ってその区間で実現でき…

SRM616 div1 easy WakingUp

考えたこと とりあえず周期性がありそう。全てのアラームが鳴るタイミングまで進めばあとは周期lcmで繰り返されそう。10以下の整数のlcmは5*7*8*9=2520で計算量的には問題なさそう。周期の部分が負なら必ず起きそうなので-1を返すことにする。サンプル3で全…

SRM615 div1 easy AmebaDiv1

考えたこと Xに含まれないサイズはそのサイズを初期サイズとすれば最終サイズも等しくなるので必ずSに含まれる。Xに含まれるサイズを全て試せばいい。 実装したら通った。ものすごい簡単で逆に驚いた。 // BEGIN CUT HERE // END CUT HERE //#define __USE_M…

SRM614 div1 easy MinimumSquare

概要 xy座標上の点がn個与えられる。このうち少なくともk点を含むような正方形のうち面積が最小のものを求めろ。 考えたこと x座標、y座標でそれぞれソートして小さい方からk点取る貪欲をしようとする。正方形を長方形だと誤読したりなぜか実装をバグらせた…

tco2017 Pittsburgh Regional round med

概要 数列のどの要素の3つ組を取っても和が9の倍数とならないような最大の部分集合の大きさを求める。 考えたこと コンテスト中の誤った思考を書いてるだけ。 与えられる数列の要素は200以下なので3乗くらいまでできそう。試しに9の倍数になる3つ組を全列挙…

SRM 613 div1 easy TaroFriends

概要 太郎くんの友達がいる位置が1次元座標として与えられる。友達はそれぞれ1回、左か右にX動かなければならない。最長の友達の距離を最小化する。 考えたこと とりあえず入力をソートして考える。最初任意の回数移動できるのかと思い距離Dを達成できるかを…

SRM 612 div1 easy EmoticonsDiv1

考えたこと dp[i] = (i個をつくるのにかかる回数)としたO(n^2)のDPを投げたらシステスで落ちた。 解説読んで状態に(テキストの数、クリップボードの数)を取るdijkstraを書いた。

SRM 610 div1 easy TheMatrix

考えたこと この間のARC080Fとか最大長方形とかを思い出す 制約を見たらh,w 二次元累積和っぽく実装したら通った かなり簡単目だったのかO((HW)^2)が嘘解法だったのか…? 解法 (x, y)を左上、(w-1, h-1)を右下とする各長方形について、条件を満たす長方形を…

SRM 609 div1 easy MagicalStringDiv1

考えたこと ><><>'の数-' 罠 誤読 解法 i番目までの'>'の数を前から、i番目からn-1番目までの' ans = max(i番目までの'>'の数, i+1番目からn-1番目までの'

SRM 608 div1 Easy MysticAndCandies

考えたこと まず適当に箱を選んだ時その選び方が条件を満たしてるかの判定について考える 選んだ箱のlowの和をlsum、選んでない箱の和をhsumとする C-lsum-hsumが正ならその分選んだ箱のキャンディーの最低数が増える max(C-lsum-hsum, 0) + lsum >= X とな…

SRM 607 div1 easy PalindromicSubstringsDiv1

考えたこと 長さ5000以下なのでO(|S|^2)までいけそう dp[i][j] = (i番目までの文字列で長さjの回文がつくれる確率)を考える 区間[i+1, j)が回文かどうか前計算で求めておくのをとりあえず実装してみる この実装をしてたら幅が小さい方から埋めていくDPを最…

SRM716 div2 hard

概要 最初のm個がp[i] != iとなっているという条件を満たす長さn+mの順列pの個数をmod 10^9+7で求める。 解法 条件がなかったとしたら順列の個数は(n+m)!となる。次にm個のうち1個が条件を満たしていない個数を考える。m個の中から1個を選び、残りのm+n-1個…