D - Choose Your Characters 都合のため、iはiに対して不利とする 解法 rok[l] := lに対して、選べる最小のr 上が出来れば解ける 例えばi に対して不利なキャラが 2 3 5 6 7の時、 rok[7] = max(rok[7],8 ) rok[6] = max(rok[6],8 ) rok[5] = max(rok[5],8 )…

C - Permutation City 木の方が扱いやすそうなので、全域木に変換して0を根とする dfs(i,親)で以下を繰り返す iと子のうち、他の頂点に選ばれていない物の集合Vを考える Vの要素数が1以下ならreturn 2つ以上あればv[0] -> v[1] ......v[last] -> v[0]の様に(…

No.409 ダイエット - yukicoderすぐに見えて成長を感じた 解法 断食日数がはっきりしないと面倒なのでdp[i] := i日目に食べる際の最適とする こうするとdp[j]から遷移する際に断食日数が定まるためやりやすい これは一見O(n^2)だが、これはconvex hull trick…

Y - Grid 2 解法壁へ行ける事にする。dp[i] := iへの行き方のうち、他の壁を通らないような場合の数とする。ここで、ゴール地点gを壁としてやると、dp[g]が答えである。 遷移方法は、iの左上にある任意の壁jでdp[i] = iへの行き方 - sum(dp[j]からiへ行く方…

W - Intervals dp[i] := iまで見ていて、iが1の時の最大値としたいすると、あるi未満のjで、dp[i] := max(dp[j]) + iが含まれる区間のコスト という風にしたくなるmax(dp[j])はセグ木を使えば管理できる しかし、このままではi,j共に含まれる区間が、重複し…

https://atcoder.jp/contests/arc102/tasks/arc102_cあるiについて考えると合計がiとなるようなペアがp種類存在する この時、ペアの片方は自由に選べ、選ぶ物の数をq種類とする するとiが奇数の時に res += pCq * 2^q * k-2p+q H n-q となる 全てのqについて…

E - Independence解法 辺で繋がっていない都市は、別のグループに属さないといけない よって補グラフが二部グラフでなければ答えは-1二つの集合サイズを均等に分けると答えが最小になる これは、ナップザックにより解ける グラフは複数の二部グラフに分けら…

E - Symmetric GridPItS さんのコードを参考にしました ARC095 E : Symmetric Grid(700) - PItS' Buffer Solution解法 まず列の並び方を決めた後、全ての行に対応する行があるかを判定するまた、列の並び替えは全て試す必要はなく、ペアを決めるだけでいい具…

No.794 チーム戦 - yukicoderこの手の一つ一つ選んでいく問題は、選ぶ対象が単調増加していくように設定すれば解ける ソートして大きい順に見ていくと、選べる相手はあるv以下の数であり、このvは単調増加のため解けた類題 F - チーム分け D - Double Landsc…

F - Normalization操作において、不変の値に気付けると強いの意味が分かったabcを012とするとmod3上で合計は変化しない 自明に作れないケース以外はうえで作れる nが3以下の時はどの操作でも真ん中が使われるため例外的に全部は作れないSubmission #4271328 …

E - Tozan and Gezanまずaiがbi以下なら限界まで取ったほうがよさそう 残ったaj > bj なる任意のあるjについてj以外が０になるまで選べる なぜならとざん君がjを取らない限りa[j] > b[j] が保たれるためよって答えは全体の合計からa[i] > b[i]なる最小のb[i]…

E - Both Sides Merger「どちらの操作も全体の合計から自分を引いている」 という事を利用するのかと思ったが、持てる合計を書いてみると最終的な合計に偶数番目と奇数番目が含まれることはないとわかる また、偶奇上なら自由に選べる Submission #4267606 -…

E - Avoiding Collision二人が最短で動く方法から出会う組み合わせを引くsからtへの最短距離をdとする すると二人が出会うのはd/2移動したときところで、ある頂点iにいる時の時刻は一定なので diss[v] := sからvへ移動するのにかかる時間 dist[v] := tからv…

E - Bichrome Tree解法 木のdpを考えたくなる頂点iの色をai、違う色をbiとする 頂点i以下でaiの合計はXiであり、biの合計は自由であるよってdp[i][bsum] := i以下でbiの合計がbsumとなるものが作れるか としたくなったが、計算量が多すぎるここでbsumは小さ…

Submission #4195664 - AtCoder Regular Contest 0812*2の時について考えると 黒の合計が偶数の時のみ全てを黒くできるとわかる また、この領域からなる長方形も全て黒くできるなぜなら、どのような操作をしても2*2正方形内の黒は偶数個あり 左端と上を黒く…

E - guruguruお気に入りを使わなかったときに比べて、それぞれのお気に入りボタンで答えがいくつ少なくなるかの表 サンプル1 分かりやすさのためm+1は1として扱う fからtで移動する際、f+2からtにかけて-1 -2と増えていく これは下のようにいもす法を二回使…

E - Connected?よく考えると端同士が繋がれてるもののみ考えればいいとわかる その中で、全ての線が交わらなければYes時計回りで見た時に123321のように対応が取れていれば繋げるため、スタックの要領で溶ける(kmjpさんのコード参考) Submission #4184430 - …

E - Frequency最大の石を減らすには、石の数×高さの回数が必要になる この操作をシミュレートする 自分と同じ高さの場所の数と二番目に高い物の位置が必要になる pairに（石の高さ,インデックス）を持たせて降昇順にソートすると石の数と最小のインデックス…

E - Frequency最大の石を減らすには、石の数×高さの回数が必要になる この操作をシミュレートする 自分と同じ高さの場所の数と二番目に高い物の位置が必要になる pairに（石の高さ,インデックス）を持たせて降昇順にソートすると石の数と最小のインデックス…

E - Snuke Lined毎に行ける駅をm log nで見れる 累積和を使えば各駅に置かれる名産品の数がわかる ここで、dで行ける駅について名産品の数を加算していくと名産品が重複してしまうなので、区間の長さがd以上の名産品は必ず取れることと、区間の長さがd未満の…

E - 高橋君とホテル / Tak and Hotelsホテルiからd日で移動できる場所は、「現在地点から距離がLを超えない範囲で移動する」をd回繰り返した場所です 全てのiについて1日で移動できる場所は二分探索でO(log n) よってダブリングが出来て二分探索しますまた左…

E - 和風いろはちゃん / Iroha and Haiku余事象を考えるとわかりやすい 桁毎に全探索するメモ化で解く ある桁iで使える数vは、iを右端としたときに575とならないようなvだが これは右端から数の累積和を取ってbitに持たせれば575になるか判定できる 18以上の…

atcoder.jp2乗の木dp なのでdpのサイズは気にしなくていい切り離したものは条件を満たしていないといけないが、今見ている連結成分は後々マージされるためその限りではない Submission #4131219 - AISing Programming Contest 2019 / エイシング プログラミ…

E - Weights on Vertices and Edgesコストが大きいものから辺を消していきたい しかし実現困難なため逆の操作を行うコストが小さいものから辺を繋いでいくある辺を繋いだ時にその辺が成り立つ場合、集合内の辺はすべて成り立つこれはunionfindで頂点につなが…

C - 部門分けo(n ^ 3)で部分集合が列挙できる いくつかの集合に分けるため、それらの評価値を独立して考えたい 部分問題として考えるには dp[m] := 全体の集合がmとした時の問いの答えとすればいい 遷移はdp[m] = dp[s] + dp[m-s] - 二つの間の信頼値の合計…

D - Double Landscape 解法まず縦横に同じ数があってはいけないabをソートするそのうえで、大きい数から置ける範囲を考えていくと 前回の範囲を含む長方形となるため、その中から一つ自由に選べる（今までに置いた数だけ 置ける場所は引かれる） ただし、aか…