SRM

SRM684D1Easy CliqueParty

久しぶりの投稿。 方針 両サイドを固定すると、集合Dの最大値が決まる。 左端からk-smoothを満たすように選んで行く。 コード class CliqueParty { public: int maxsize(vector<int> a, int k) { int N = a.size(); sort(a.begin(), a.end()); int ans = 0; FOR(l</int>…

SRM658D1E OddEvenTree

SRM

docs.google.com 正答率63%。

SRM650D1E TaroFillingAStringDiv1

docs.google.com 正答率80%。

SRM646D1E TheConsecutiveIntegersDivOne

docs.google.com 正答率68%。

SRM643D1E TheKingsFactorization

docs.google.com 正答率55%解けた〜!!

SRM642D1E WaitingForBus

docs.google.com 正答率73%

SRM637D1E GreaterGame

docs.google.com 正答率67%

SRM628D1E DivisorsPower

docs.google.com 正答率48%。 方針はあってたけど誤差で死んだ。

SRM627D1E HappyLetterDiv1

docs.google.com 正答率65%。

SRM626D1E FixedDiceGameDiv1

docs.google.com 条件付き期待値の求め方知らなかった。 正答率54%。

SRM625D1E PalindromePermutations

docs.google.com 正答率68%、誤差が怖い。

SRM624D1E BuildingHeights

docs.google.com 正答率88%だけどTLEギリギリ。

SRM623 D1E UniformBoard

docs.google.com 正答率70%

SRM622D1E BuildingRoutes

docs.google.com 正答率58%

SRM621D1E RadioRange

docs.google.com 正答率66% AGC021のBと同じ解法だったのでできた。 最大でO(109)だったけどギリギリ間に合った。

SRM620D1E PairGame

docs.google.com 正答率77%なので解けた

SRM619 D1E SplitStoneGame

docs.google.com あっさりすぎて逆に不安だった

SRM D1E Family

docs.google.com 親同士結んで2部グラフ判定か... 気がつかなかった...

SRM616D1E WakingUp

docs.google.com start_i <= period_i だから0開始で良いのか...

SRM div1 Easy AmebaDiv1

docs.google.com

SRM614 div1 easy MinimumSquare

docs.google.com

SRM div1 Easy MysticAndCandies

SRM

メモ できなかった... C-sum(low[i])がどの箱に入ってるかわからない。 最悪なケースは選ばない箱にどこに入ってるかわからない飴ができるだけ入っている状態。 良い選択方法としては ・lowが大きい順に選ぶ->選ぶ箱に最低限入っている飴を多くしたい or ・h…

SRM605 div1 Easy AlienAndHamburgers

SRM

メモ tasteが正なら絶対食べた方が良い tasteが負の場合はそのハンバーガーを食べることで種類が増えるなら、食べるとjoiを大きくできる可能性がある tasteが負のハンバーガーしかない種類については、tasteが一番大きいハンバーガーだけを食べるか食べない…

SRM604 div1 Easy PowerOfThree

SRM

メモ Possibleの場合 xとyの和は ± 30 ± 31 ± ... ± 3k なので、x座標かy座標どちらかが3の倍数+1or3の倍数-1になる 余計な1を消して3で割ると ± 30 ± 31 ± ... ± 3k-1 となり、x座標かy座標どちらかが3の倍数+1or3の倍数-1になる これを繰り返していくとx=0…

SRM603 div1 Easy MaxMinTreeGame

メモ Atcoderの D - ABS と似た考察でいけた。 先攻が3ターン目以降で良い点数を狙うことができない系の問題。後攻が2ターン目で得られる最小の得点で終了させるから。 なので1ターン目で終了する時の最大値を出力すればOK。 今回は葉の頂点の中でのコストの…

SRM602 div1 Easy TypoCoderDiv1

メモ 動的計画法。 dp[i+1][j] := i個目まででレートがjの時の色が変わった回数の最大値とする。レートjにならない時は-1とする。 レートは109以上になるため工夫しないとTLE。 2200以上が2回以上続くことが禁止されているため、2200未満のレートだけ考えれ…

SRM601 div1 Easy WinterAndPresents

メモ n個の袋から取り出したappleとorangeを合わせた時、appleとorangeの個数が(a,b)になる(a+b=nX)。 それぞれの袋にappleとorangeがそれぞれX個以上あるならそれぞれの袋からX個取り出すときは、 合わせると(nX,0),(nX-1,1),...,(0,nX)となるのでnX+1通…

SRM609 div2 Med PackingBallsDiv2

解法 variety setを何個売るか決まれば、同じ色のパッケージを何個売らないといけないか決まる。 variety setを何個売るかで全探索。 コード class PackingBallsDiv2 { public: int minPacks(int R, int G, int B) { int ans = 1e9; // variety set for(int …

SRM607 div2 med PalindromicSubstringsDiv2

TopCoder Statistics - Match Overview 問題概要 文字列Sの中に回文が何個あるか 制約 |S| ≦ 5000 解説 文字列Aが回文の時Aの両サイドに同じ文字が連結した文字列も回文となる。 同じ文字でない文字が連結したらその時点で回文では無くなる。 回文の中心がsi…

SRM606 div2 med EllysNumberGuessing

TopCoder Statistics - Match Overview 問題概要 Aさんが1以上1000000000以下の数字を思い浮かべる BさんがAさんが思い浮かべた数字がx1,x2,...,xnかどうか聞く Aさんは思い浮かべた数字とxとの差の絶対値yを答える Aさんが思い浮かべた数字が一意に定まる時…