問題 解法 解答 問題 https://www.ioi-jp.org/camp/2010/2010-sp-tasks/2010-sp-day2_21.pdf 解法 小さい位から順に考えていく．桁を１つ１つ見ていては TLE になってしまうので，１つ目か２つ目の整数の桁の数が変わる桁の位置で区切って考える．１つの区間…

問題 解法 解答 問題 https://www.ioi-jp.org/camp/2010/2010-sp-tasks/2010-sp-day2_21.pdf 解法 dp(i) := S の i 文字目までを構成するのに素 DNA 鎖が最小で何本必要か と DP を定義する．このとき，S の i 文字目から文字列が一致する素 DNA 鎖の最大の…

問題 解法 解答 問題 atcoder.jp 解法 問題文中に 書き足された各辺 u→vu→v は、ある頂点 uu からその子孫であるような頂点 vv に向かって伸びています とあるので答えは一意に定まる（これを見落としていて複数答えがあるのでないかとちょっと悩んでいた）…

結果 A - Subscribers B - Touitsu C - Different Strokes 結果 ６問中３問正解（700 / 3200 点, 63:43），2443 位中 993位，パフォーマンス 1398，新レート 1629 (-23)．最近にないレートの下げ幅を記録してしまった．A, B 問題を早く通せたのはよかったが…

問題 解法 解答 問題 atcoder.jp 解法 自分と相手にとって幸福度の高いものを食べたいと考えると，(a_i + b_i) が大きいものから食べていけば最適だと気付く．言い方を変えると，最初に求める答えが -(b_1 + b_2 + ... + b_N) だった場合，ここに最大の (a_i…

問題 解法 解答 問題 atcoder.jp 解法 ２人の操作後の各カードの所属は，N が偶数のとき「TATA...TAAA...ATT...T」のように高橋君と青木君が交互になっている区間（区間１）・青木君の区間（区間２）・高橋君の区間（区間３）となっている．また．区間２と区…

問題 解法 解答 問題 atcoder.jp 解法 雪マスは必ず２つ以上連続するので，１つの雪マスを氷マスに変化させても氷マスの連続する区間が１つの区間になることはない．また，氷マスの区間が最も長い区間の前後どちらかの雪マスを氷マスに変化させるのが最適で…

問題 解法 解答 問題 atcoder.jp 解法 まず，N 個の寿司を「おいしさ」が大きい順にソートし，大きいものから K 個選び答えの候補にする．このとき選んだ寿司のネタの種類数が k だとしたとき，1 ~ (k - 1) 種類のネタだけで K 個選ぶことは不可能 or 最適で…

問題 解法 解答 問題 atcoder.jp 解法 「水やり」の回数を最小化したいので，１回の「水やり」で出来るだけ多くの花の高さを伸ばしたい．なので，あと 1 以上伸ばさなければいけない花の連続する区間は１回の「水やり」で 1 ずつ伸ばす．h_i に達した花がそ…

結果 A - Beginning B - KEYENCE String C - Exam and Wizard D - Double Landscape 結果 ６問中４問正解（1200 / 2700 点, 115:24），1986 位中 405位，パフォーマンス 1750，新レート 1652 (+11, Highest)．目標であった４問正解を達成できたのでよかった…

問題 解法 解答 問題 atcoder.jp 解法 各マス (i, j) に書くことが出来る数字の最大値を max_(i, j) とする．また，数字 i が書くことが出来る数字の最大値になっているマスの個数を cnt_i とし，数字 i を書く時点で書くことが出来るマスの総数を avail_i …

問題 解法 解答 問題 atcoder.jp 解法 まず，A_i < B_i の状況であるものは必ず A_i を B_i まで上げる必要があるのでこれらは答えの個数に加わる． 上げる必要がある準備度の総和を sum とし，準備度が十分であるものの余剰分（B_i - A_i）を降順ソートした…

結果 A - Bulletin Board B - Contests C - Alternating Path 結果 ５問中３問正解（600 / 1700 点, 39:10），1970 位中 420 位，パフォーマンス 1696，新レート 1641 (+6, Highest)．何とかレート Highest 更新出来たが，D 問題を WA が多発し，通せなかっ…

問題 解法 解答 問題 atcoder.jp 解法 問題文の条件より，i 枚目のコインをある頂点 v に置くと決めた場合，(i + 1) 枚目以降のコインを頂点 v とその子孫の頂点に置くことが出来なくなる．よって，1 枚目のコインから順に置く場所を決めていく． (i - 1) 枚…

結果 A - Frog 1 B - Frog 2 C - Vacation D - Knapsack 1 E - Knapsack 2 G - Longest Path H - Grid 1 I - Coins K - Stones L - Deque M - Candies P - Independent Set 結果 26 問中 12 問正解（1200 / 2600 点, 216:15），1124 位中 252 位．AC した問…

問題 解法 解答 問題 atcoder.jp 解法 dp(i, f) := 頂点 i を黒で塗れるかどうかが f のとき，頂点 i から到達できる頂点を塗り分ける通り数 と定義する．このとき， dp(i, f) = dp(v_1, true) * dp(v_2, true) * ... (f == false のとき) dp(i, f) = dp(v_1…

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j) := i 人目までで j 個分けるときの通り数 と定義する．このとき， dp(i, j) = dp(i - 1, j) + dp(i - 1, j - 1) + ... + dp(i - 1, j - a_(i - 1)) dp(i, j) = 1 (j == 0 のとき) dp(i, j) = 0 (j < 0, i == 0…

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j, k) := 数列 a_i ~ a_j の中で k が操作するときの (X, Y) の値 と定義する．このとき， dp(i, j, k) = ( dp(i + 1, j, (k + 1) % 2).X + a_i, dp(i + 1, j, (k + 1) % 2).Y ) か ( dp(i, j - 1, (k + 1) % 2).…

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j) := 石が i 個あり操作するのが j のとき，j が勝てるかどうか と定義する．このとき，残りの石の状態のうちどれかが相手を負けにすることが出来るならば，自分を勝ちにできることを踏まえると， dp(i, j) = !d…

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j) := i 枚目まで操作し j 枚表のときの，表が裏より多くなる確率 と定義する．このとき， dp(i, j) = dp(i - 1, j + 1) * p_(i - 1) + dp(i - 1, j) * (1 - p_(i - 1)) と漸化式が立つ．状態数 O(N^2)，遷移 O(1…

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j) := マス (i, j) に到達するまでの経路数 と定義する．このとき， dp(i, j) = 1 (i == 1 かつ j == 1 のとき) dp(i, j) = dp(i - 1, j) + dp(i, j - 1) (それ以外のとき) と漸化式が立つ．状態数 O(HW)，遷移 O…

問題 解法 解答 問題 atcoder.jp 解法 dp(i) := 頂点 i から始まるパスで最長のものの長さ と定義する．このとき， dp(i) = max( dp(v) + 1 ) (v は頂点 i から到達できる任意の頂点) と漸化式が立つ．答えは dp(i) (1 <= i <= N) の最大値．状態数 O(N)，遷…

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j) := i 番目のものまでで価値 j のときの重さの最小値 と定義する．このとき， dp(i, j) = inf (j < 0 のとき) dp(i, j) = 0 (j == 0 のとき) min( dp(i - 1, j) , dp(i - 1, j - v_(i - 1)) + w_(i - 1) ) (そ…

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j) := i 番目のものまでで重さ j のときの価値の最大値 と定義する．このとき， dp(i, j) = max( dp(i - 1, j) , dp(i - 1, j - w_(i - 1)) + v_(i - 1) ) と漸化式が立つ．状態数 O(NW)，遷移 O(1) となり O(NW)…

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j) := i - 1 日目に j を選んだ時の i 日目までの幸福度の和の最大 と定義する．このとき， dp(i, j) = max( dp(i - 1, 0) + a_(i - 1) (j != 0 のとき), dp(i - 1, 1) + b_(i - 1) (j != 1 のとき), dp(i - 1, 2…

問題 解法 解答 問題 atcoder.jp 解法 dp(i) := 足場 i に行くまでにかかるコストの最小値 と定義する．このとき， dp(i) = min( dp(i - j) + | h_i - h_(i - j) | ) (1 <= j <= K) と漸化式が立つ．状態数 O(N)，遷移 O(K) となり O(NK)． 解答 atcoder.jp

問題 解法 解答 問題 atcoder.jp 解法 dp(i) := 足場 i に行くまでにかかるコストの最小値 と定義する．このとき， dp(i) = min( dp(i - 1) + | h_i - h_(i - 1) |, dp(i - 2) + | h_i - h_(i - 2) | ) と漸化式が立つ．状態数 O(N)，遷移 O(1) となり O(N)…

結果 A - Gennady and a Card Game B - Petr and a Combination Lock C - Yuhao and a Parenthesis 結果 ８問中３問正解（2670点），7762 位中 2235 位，新レート 1480 (+61, Highest)．レート最高を更新出来たのでよかった．B ~ C 問題で WA を何回か出して…

問題 解法 解答 問題 codeforces.com 解法 各括弧列について，( と ) のどちらがどれだけ不足しているのかを調べる．もし，両方不足している括弧列は他のどの括弧列ともペアになれないので考えない．それ以外の括弧列の中で ( の不足分と ) の余剰分が一致す…

問題 解法 解答 問題 codeforces.com 解法 n <= 15 と小さいので，回すそれぞれの動作を時計回りか反時計回りのどちらにするかを全通り試す．針が 0 度のところに戻るかどうかは O(n) で判定できるので，O(2^n * n)． 解答 codeforces.com 360 で mod を取る…