問題 解法 dp[ i ][ j ] := #( [0,j) のみ消されていて, i-1 開始の区間を列挙し終えた ) として, i 開始の区間を考える. 半開区間で考えているので消す区間 [l,r) の満たす条件は r-l >= K+1. 新しく [0,x) から [0,j) ( x < j ) まで消す場合 [ i, j ) は…

問題 解法 n文字からなる文字列の変換の典型として, 'a' -> 0, 'b' -> 1, 'c' -> 2 に変換して総和のmod3に注目する この場合でも総和のmod3は保存されることがわかる. この非自明な必要条件が本質. 更に実験すればわかるが,1回以上の操作によって a[i] == a…

メモ 17完. 解けない問題いっぱいあるなあ 集めるDPの方がバグらせにくくて(当社比),メモ化にもしやすいのでほぼそっちで書いた. 簡潔なまとめはプロのツイッターを見るのが良い. DPコン、解法全部書いた。 https://t.co/BqSnOQIkbR— ꑄ꒖ꐇꌅꏂ (@snuke_) 2…

問題 解法 お絵描きしたのでメモ. 部分点は O(N2) の区間DP. それ以上に早くやるにはどうするか. 遷移が O(1) なので状態を減らすしかない. しかし,DPテーブルは疎でもなく,あまりまとめられそうにもない. よってある状態(操作)を禁止して状態を減らすことを…

問題 問題概要 自然数Nに対し次の操作をK回繰り返す. K回後の期待値を求めよ. 自然数に対してその約数を等確率で1つ選び,その約数で置き換える. 1 <= N <= 1015 , 1 <= K <= 104 解法 本番は愚直なDPを定数倍高速化しようとしたが無理だった. これは約数を全…

問題 解法 スコアは中央値なので,そのままやるとこれまで書いた和を全て持っておく必要がある(どれも中央値になり得る) => これは当然全探索に近いので不可能 => 中央値は2ぶたんがやりやすい(X以上がY個の条件が判定しやすい) という典型もあり,判定関数を…

問題 解法 最初maxの方を選択していって差分が小さい順に種類を増やしていくgreedyが思いつく -> なんかgreedyはやばそうなのでDPかな? (やばそうと言いつつも反例は思いつかなかった,教えて欲しい) -> key: i 番目まで見た, j 種類出た として1枚ずつ表裏を…

問題 解法 K個以上の区間は消せる Greedyは厳しそう dp[i] := (最後に[i,i+K) を消したときのmax ) とすると..? dp[i+1] = max_{ j, [i,i+K) と [j,j+K) の区間が被っている } ( dp[j] + sum_b [j+K, i+K) ) と, dp[i+1] = max_{ j, [j,j+K) の区間は [i,i+K…

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

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

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

問題 解法 前提知識 分割数 蟻本にも載ってる. この問題は,X=sum(death)=sum(相手チームのkill)とすると, kill数が全員同じ -> sum(death_i) = X, death_i は昇順の通り数 -> すなわち分割数,DPで出せる kill数が全員違う -> sum(death_i) = X, death_i の順…

問題 問題概要 N以下の正整数であって、十進法表記したときの各桁の数の和がDの倍数であるものの個数をmod 1e9+7で求めよ。 1<=D<=102,1<=N<=10104 解法 dp[0][i][j] := (下からi桁までの数で、modがjであるものの数) dp[1][i][j] := (下からi桁までの数で、…

問題 問題概要 文字列Sが与えられる。 Sを各々が並び替えれば回文にできるような部分文字列に分割するときその最小数を求めよ。 1 <= |S| <= 2*105 解法 回文条件を言い換えると、「文字列の中に奇数回出てくるようなアルファベットはたかだか1種類である」…