はまやんはまやんはまやん

hamayanhamayan's blog

2017-02-01から1ヶ月間の記事一覧

競技プログラミングにおける区間DP問題まとめ

区間DP dp[L][R] := 区間[L,R]についての何か 簡単な入門問題があまりなかった 発展的だが、Monge性を利用して更新高速化できる場合がある 区間DPのよくある方針としてdp[L][R]をdp[L+1][R]とdp[L][R-1]を使って更新する方針がある 【テク1】中心が決まって…

競技プログラミング練習問題集

他 競技プログラミングにおける細かな話題まとめ - はまやんはまやんはまやん DEGwerさんの数え上げテクニック集問題まとめ - はまやんはまやんはまやん セグメントツリーにセグメントツリーを乗せる手法(2Dセグメントツリー) - はまやんはまやんはまやん …

競技プログラミングにおけるゲーム問題まとめ [Nim,Grundy数,後退解析,ミニマックス法]

ゲーム問題を解決する手段 Nim 「N個の石山があり、交互に山から石を任意個取っていく。先に取れなくなったほうが負け。」 各石山の個数をx[i]個とすると、勝敗は各山の個数を全てxorした値を見れば分かる。全てxorして=0なら先手は負け、!=0なら勝ち Nimの…

競技プログラミングにおける動的計画法問題まとめ

動的計画法をまとめたもの 入門者向け まずは「最大最小系」「yes/no系」「組み合わせ系」 基礎はこことか、こことか、こことかで勉強しよう ループで書くか、再帰関数かというのがあるが、こっちの方が書きやすいとかがあったりするので、どちらも書けるよ…

雪の足跡 [yukicoder 340]

問題 https://yukicoder.me/problems/no/340W×Hの盤面があり、N人の人がそこを通る。 i番目の人はM[i]回移動していて、移動先はB[i][j]->B[i][j + 1]である。 移動元と移動先はw + h * Wで表記されていて、距離が1とは限らない。その移動後に(0,0)から(W - 1…

競技プログラミングにおける2-SAT問題まとめ

2-SATとは 「x ∧ y」の選言の充足判定をする 解説 コドフォ記事 2-SATはSCCで解ける ダメな組合せが見つかったときに制約を作る 問題 yukicoder No.274 The Wall 解説 CF400 The Door Problem yukicoder No.470 Inverse S+T 解説1 解説2 CC Vertex Cover 解…

PalindromicSubseq [SRM 708 : Div1 Med]

問題 https://community.topcoder.com/stat?c=problem_statement&pm=14526N文字の文字列Sがある。 X[i] := Sの部分文字列のうちS[i]を含み、回文となる組合せ Y[i] = i * X[i] % (10^9 + 7) Y[1] xor Y[2] xor ... xor Y[N]を答えよ。1

競技プログラミングにおけるマージテク問題まとめ

マージテク 正式名称、データ構造をマージする一般的なテク 集合をまとめる時に大きい方に小さい方を移動させることでマージさせると計算量がならしO(logN) 発祥の地 併合(マージ)可能なheapをmeldable heapといい、実装の1つとしてマージテクを使うものがあ…

競技プログラミングにおける全方位木DP問題まとめ

全方位木DP よく分かる解説 問題 CSA Connected Tree Subgraphs [解説 CF397 Tree Folding CF405 Bear and Tree Jumps AtCoder Driving on a Tree CSA Root Change EDPC Subtree 解説 CF Centroids 解説1 解説2 解説3 CF395 Timofey and a flat tree CF302 R…

競技プログラミングにおける木の同型判定問題まとめ

木の同型判定問題 木についてDFSでハッシュを求め、その比較によって同型判定をする snukeさんの記事にrng_58さんのやり方の和訳が書いてある 問題 CSA73 Binary Isomorphism 解説 ACM-ICPC 2016 国内予選 F: 文字解読 HackerRank Tree Isomorphism Codechef…

MultiplyAddPuzzle [SRM 707 : Div1 Med]

問題 ある数sについて以下の手順をしてある数tにしたい。1. +aする 2. *bする最小のステップ数は?0