No.409 ダイエット - yukicoder 問題概略N日あり、毎日ドーナッツiを食べるか食べないかを選択できる。iを食べるとDi体重が増えるがストレスが0に、食べないと、体重がA減る代わりにストレスが1増え、体重がB*(ストレス)増える。初期体重はW、最終日の最軽は…

問題概略 1 ~ Nが書かれた、白と黒のボールが2N個並べられている。 隣り合う２つのボールを入れ替えることが出来る時、白黒をそれぞれの色についてソートするのにかかる最小手数はなにか。制約 1 解法 実際にソートする時の事を考えると、左詰めにやっていき…

E - Don't Be a Subsequence問題概略 文字列Sに対して、その中の部分列でない文字列のうち、一番短く辞書順最小のものを求めよ。制約 10^5解法 0文字目からスタートして、a~zについて、自分に一番近いところをとることを文字列の外に出るまで繰り返すことで…

C - Kill/Death 問題概略 1000個の物を100個の箱に入れたい、また、いくつかの区間で昇順になっている必要がある。N,M sum 解法 昇順について考えなければ、桁DPとして解ける。 dp[i][rem] := iまで見ていて、残り使える合計がrem 昇順になっていないといけ…

問題概略 ()からなる文字列が与えられる。 空文字列 ある括弧の対応が取れている文字列 A,B が存在し、 A,B をこの順に連結した文字列 ある括弧の対応が取れている文字列 A が存在し、 (, A, ) をこの順に連結した文字列 以上を括弧の対応が取れている文字列…

問題概略盤面に金塊が並べてある。 また、回収装置がいくつか置いてあり上下左右の自分から連続した金塊を回収することが出来る。 好きな順番で回収装置を作動させる時、最大の金塊回収数を求めよ。制約 W,H 回収装置N 解法 回収装置を使うと4つの小さい盤面…

A - YahooYahooYahoo問題概略 文字列Sのyahoo....yahooへのレーヴェンシュタイン距離を求めよ。制約 10^5解法 [i]までをy,a,h,o,oにする場合で遷移していく（レーヴェンシュタイン距離を求める時と似た感じで） yahooは循環しているのでo->yへの遷移も出来る…

D: プレゼント - AtCoder Beginner Contest 038 | AtCoder 問題概略 x,yでの最大部分増加列 制約 1≦N≦105 1≦hi≦105 1≦wi≦105 解法１ dp[i] := iまでを使ってできる最長の増加列。 1次元の場合はソートして、一つ一つ見ていき小さい場合は自分より大きい最小…

D - ABS 問題概略 N枚のカードの山がある。プレイヤーが二人いて最初にz,wを持っている。 お互いに山札から1枚以上のカードを引き、最後に引いたカードを手札にする。 先行はお互いの差の絶対値を最大化、後攻は最小化する時のスコアはいくつか。 制約 入力…

B: Neutralize - SoundHound Programming Contest 2018 Masters Tournament 本戦 (Open) | AtCoder問題概略 要素Nの数列がある。連続したK個を0にする操作を何回か繰り返し、総和を最大化したい。制約 1≤K≤N≤2×10^5 −10^9≤bi≤10^9 入力中の値はすべて整数で…

D - Simple Knapsack 1≦N≦100 1 W 10^9 1 wi 10^9 w 1 vi 10^7与えられる重さが4種類しかないナップザック [i個目を選ぶ時][選んだ個数][端数の合計を足した]の3次元で解いてみた問題の芯 範囲が広くても、複数のまとまりになっていると分かる場合は、調べる…

D: サプリメント - AtCoder Beginner Contest 017 | AtCoder 複数のサプリメントを食べる方法を考える. 1,2,3,4,3,5,2,6,5,6,7みたいな場合 0 1 2 3 4 5 6 7 8 9 10 個食べる組み合わせ 1 1 2 4 8 今日何個食べるかを考えると、自分から左へ自分を含まないと…