ferinの競プロ帳

競プロについてのメモ

SRM

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個…

SRM 716 div2 med

概要 文字列sと文字列tが与えられる。sの各文字をtの文字で置き換えることができる。tの文字はそれぞれ1回ずつしか使用できない。書き換えた後の辞書順最大となるsを出力する。 解法 先に現れる文字を大きいものにしたほうが辞書順としては後のものになる。…

SRM 717 div2 easy

概要 要素が0か1の2次元配列tが与えられる。x[i] xor y[j] == t[i][j] となる要素が0か1の配列x、yを構成することが可能か判定する。与えられる配列のサイズは5×5以下。 解法 1行目(y[0])を0か1で固定すれば残りの列の数字(x[i])は一意に定まる。残りの行に…

SRM 710 div2

Easy 問題概要 解法 Med 問題概要 解法 Hard 問題概要 解法 Writerの方の解説 codeforces.com Easy 問題概要 n要素の配列Aが与えられる。この配列の部分列の和を最大化したい。ただし、配列の最初の要素のA[0]を選択した場合、部分列の和の正負を反転させる…