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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

概要 要素が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])は一意に定まる。残りの行に…

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