問題 解法 1,..,N の順列を p1,..,pN として, 最大化したい関数は |A_p1 - A_p2| + .. + |A_pN-1 - A_pN| になる. 目的関数の絶対値を外したい気持ちになるので,そのためには数列の順序付けが必要になる. それを念頭に起きつつ最適解の必要条件を列挙してみ…

問題 解法 解説にある通り,上書きしていくような問題では操作列を逆に見ていって,そのマスで一番最初の操作で色が確定すると考えるのが良くて,そうするとそのマスに関してそれ以降の色の変化を考えなくて良くなる. さて,逆順に見ていったときの最初(つまり元…

問題 解法 最初に右を向いていて,次に右折するパターンを考える. 各マスで上方向に累積和をとると下に何マス進めるかというのがO(NM)でわかる. それを左方向に累積和をとっていくとその場所を始点として1マス以上進み,右に何マス進めるかというのがわかるの…

問題 解法 解説の1つの解釈として. 解説/解説放送と同じように, iをremoveした時に A_j が足されるかどうかを考える. ただし,確率ではなくそのような順列の場合の数を数え上げることにする. 事前準備として,n個の順列のうちで そのうちの要素 x,y (x!=y) に…

問題 解法 典型的な文字列AとBの編集距離を求める問題において, B = "yahoo" と固定したバージョンになる. (は正規表現における閉包) i=1,2,.. として 部分文字列S[0,i) を最終的な状態 "yahoo"* の前半と一致させることにしよう. それまでの最小の編集距離…

問題 解法 a_i は K と共通の因数しか注目しなくて良いことがわかるので, a_i = gcd(a_i, K) とみなして良い. Kの約数は高々 2sqrt(K) しかないので(エラトステネスの篩をやっていくとわかる), a_i として現れる数は O(sqrt(K)) しかない. 定跡としてこの分…

問題 解法 最短路なので2人とも(0,+1) or (+1,0) で進む 1人だったら? -> DPで(x,y)または(何回進んだか,x)をキーとして持ってやればできる なぜなら(x,y)で最大のお土産を持つためには(x-1,y)or(x,y-1)で最大のお土産を持っている必要があるため 2人でも2人…

問題 解法 制約から半分全列挙をエスパーする 2Nとあるので半分と後半に分けてみる 前半の赤色がa文字とすると,前半の青色はN-a,後半の青色はaになる 前半の赤色=reverse(後半の青色) かつ 前半の青色=reverse(後半の赤色)である必要がある どちらも全列挙し…

問題 解法 明らかに,解説で除いている3ケースはわかる. そうでないとき, 個数をy個とすると無限に買い続けられるときは y = C の周りを振動する 無限ループするので,yが周期をもつ-> C+1 <= y <= C+B の値を全て取りうる? .. そうであればC+1-B>=0を判定すれ…

問題 解法 考察 XOR swapによりswapが可能( a ^= b, b ^= a ) これによってa_i, a_j (i!=j) で操作ができる あるbitだけ立っている要素があればそれを使ってそのbitを自由に立たせることが可能 そのような要素は {1101, 1001} のような1bitだけ異なる数があ…

問題 解法 良解説を聞くのが良い とりあえずsortして分布(c[x] := #( a_i=x なる i ) )をまとめておく 1人ずつグループに入れていこうとすると,分布(k人グループが何個できているか)を持たないといけないので状態が指数時間になって無理 視点を変えて,人数が…

問題 解法 sample2をじっと見ると,必要条件として X_i, Y_i の和のパリティが全て一致する というのがあることがわかる パリティに注目するのはよくやるのでこれは気づかないとどうにもならない. 実際に,そのときdとして1を20個/21個用意すれば300点は取れる…

問題 解法 まず十分条件を列挙していく. 0-indexedとして, s[0] = 1 s[N-1] = 1 s[i] = s[N-1-i] D問題でもそうだったが,自明な必要条件が必要十分条件になっているというパターン. s = "100..01.." として,k番目に初めて1が現れるとする. このとき,1つの辺…