主食は米

主に競プロ備忘録

日経コン 2019 E - Erasure (700)

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

ARC 094 F - Normalization (700)

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

KEYENCE Programming Contest 2019 D - Double Landscape

問題 反省 解法は解説見ればわかるのでなんで反省点のみ. {a}, {b} をsortして右下から入れていこうとしていた -> 明らかに煩雑. 典型要素として perm を考えるときには挿入/数字が入る場所から決めていく -> 上の数字から入れていくのを a_i = b_j = x なる…

Educational DP Contest / DP まとめコンテスト 復習

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

Codeforces ECR #57 F. Inversion Expectation

問題 問題概要 一部が -1 である [1,N] のpermが与えられる. 各-1に等確率で残りの数が入る時,転倒数の期待値を求めよ. 解法 A = もともとある数, B = -1の場所に入る数 とする. A-A, A-B, B-B の期待値を足せば良い. A-A はBITを使って数え上げる. B-B は b…

AGC 030 B - Tree Burning

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

Hello 2019 D. Makoto and a Blackboard

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

CODE THANKS FESTIVAL 2018 H - Median Game (500)

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

CADDi 2018 D - Harlequin (500)

問題 解法 公式動画&解説で基本的にわかるので個人的な備忘録にとどめておく. ゲームの問題の基本的な戦略として,手で書いて実験をする. N個の数のケースで実験すると1回の遷移が O(2N) になるので, N=2で実験する. 公式解説のようなグラフを書いて実験をす…

CODE THANKS FESTIVAL 2018 G - Sum of Cards (500)

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

DDCC 2019 予選 D - チップ・ストーリー ~黄金編~ (700)

問題 解法 全力で必要条件を列挙していく. Nのk進数表記が下の桁から n_0, n_1, n_2, .. であったとすると, N = n_0 + n_1 r1 + + n_2 r2 + .. a_k = n_0 + n_1 + n_2 + .. N - a_k = n_1 (r - 1) + n_2 (r2 - 1) + n_3 (r3 - 1) で, rx - 1 は r-1 で割り切…

数列操作に関する手筋まとめ

とりあえず考えること 要素/総和のmod/パリティに注目する 操作回数を求めることができるか(特に総和を用いて) 逆操作が可能か 操作が単純な操作に分解できるか 階差数列を考える 数列2つを一致させるなら差を取る 操作の縮約ができないか/周期を持たないか …

SoundHound Programming Contest 2018 Masters Tournament Open B - Neutralize(400)

問題 解法 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…

Tenka1 Programmer Contest 2018 C - Align

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

AGC 008 B - Contiguous Repainting (400)

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

Mujin Programming Challenge 2018 C - 右折

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

AtCoder Grand Contest 028 B - Removing Blocks (600)

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

「みんなのプロコン」2017 本選 A - YahooYahooYahoo

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

DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選 C - ロト2

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

square869120Contest #3 D - お土産購入計画2 / Souvenirs (600)

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

AGC 026 C - String Coloring

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

AGC 026 B - rng_10s

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

codeFlyer 2018 final D - 数列 XOR(600)

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

Mujin Programming Challenge 2018 F - チーム分け(600)

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

ARC 103 D - Robot Arms (600)

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

ARC 103 E - Tr/ee (700)

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

CODE FESTIVAL 2018 qual A C - 半分

問題 解法 関連した以下のような簡単な問題について考える. n個の0があり,K回だけ 0<=i < n なるa_i を+1 する操作を行う. 数列は何通りできるか. これは以下のようなO(NK) の DPで解くことができる.(普通にコンビネーションでも解ける) def : dp[i][j] := (…

Warshall-Floyd の本質ミス

ミス o rep(k,N) rep(i,N) rep(j,N) d[i][j] = d[j][i] = min(d[i][j],d[i][k]+d[k][j]); x rep(i,N) rep(j,N) rep(k,N) d[i][j] = d[j][i] = min(d[i][j],d[i][k]+d[k][j]); なぜか Warshall-Floydの証明を考えれば明らか. 証明 Warshall-Floydが何をしてい…

AGC 027 B - Garbage Collector

問題 解法 本番中の考察 何回原点に戻ってくるかでXの係数が変わるのでこの回数を決めうちして1回O(N)でやったら部分点取れそう 部分最適構造( [l,r) 間のごみの最適なとり方が x=l,..,r として [l,x),[x,r) の最適なとり方を各々やってきたうちコスト最小の…

codeFlyer 2018 final C - 部分文字列と括弧

問題 問題概要 '(' と ')' のみからなる文字列Sがある. 1 <=i < j <=|S| で, S[i :j] が対応が取れているのは何組あるか. 1 <= |S| <= 105 思考と反省 考えたこと 構文木作れば k 個の子を持つ親を見つける度に kC2 足していけば出来る -> 再帰で実装しよう …