Unbalancedyukicoderhttps://yukicoder.me/problems/no/956問題概要N要素の正数列Aが与えられる。Aのすべての連続する部分列のうち、ある種類の要素が部分列の過半数を占めているものが何通りあるか求めよ。)で解いたので書き残しておく。以上か未満か」で2つに分けたうえで、それぞれを独立に解く。基本的な方針は以下のようになる。そこまでの各区間長について個別にO(N)で処理する。種類までしかありえないので、それぞれの数をO(N)で処理する。未満の数の場合この場合は条件を満たす数をまとめて処理していくことにする。場合についてそれぞれ個別にアンバランスになる区間の数をかぞえていく。これはローリングハッシュとかでよくやるように区間をひとつずつずらしながら「現在見ている区間における各数の出現回数」を管理していけばよい。入ってきた数を+1するだけ。この足し引きの結果ちょうど過半数に到達したか、あるいは逆にちょうど過半数を下回ったかを見ていれば「現在見ている区間がアンバランスか」は容易に判定できる。個しかないため、それぞれの数について個別に考えていくことにする。解くべき問題は「xかそれ以外かで埋まった数列が与えられる。xが過半数を占める区間は何通りか」である。それ以外を-1とみなして累積和をとることで効率的に求めることができる。なるので、累積和テーブルを左から見ていって「過去の値の中で今見ている値より小さいものが何個あるか」を逐一数え上げていけばよい。これは素朴にやろうとするとsetとかでlogがついてしまうが、ここで考えている数列の「+1か-1しかない」という性質を使うと各インデックスにつきO(1)で済ますことができる。あとはこの処理のあと毎回「今見ている値より小さい値の出現回数」を答えに足し込んでいけば答えが求まる。だいたい配列を舐めながら一時変数を弄っているだけなのでC++なら定数倍も軽く済む。DPhttps://yukicoder.me/problems/no/951問題概要N枚のピザがあり、ピザには値段Pi円と美味しさDiがそれぞれ設定されている。ピザを1枚買うたび、そのピザ以下の値段のピザを1枚無料で買うことができる。K円まで使えるとき、買ったピザの美味しさの総和としてありえる最大値を求めよ。K解法いかにもDPでナップサックしてくださいという見た目だが、単純なやり方ではタダ券の処理が難しい。何個余ってる】で最悪50003になってしまう。ここで「買い物が終わったあとの最終的な形」について思いを馳せると、買う商品を固定した場合、高い順に「買う→タダにする→買う→タダにする」を交互にやるのがもっとも安く済む方法である。いうわけで実は高い順に見ていったとき「タダ券を持っているなら次の買い物で即使う」のが最適であるので、DPのキーには「タダ券がある・ない」の2値を含めるだけで十分である。SがTを部分文字列として何個含むか求めよ。文字)というタプルの列として与えられる。c)はaaabbccccという文字列を表す。このようにすると、TがSの部分文字列として現れるならば対応箇所のタプル列の長さがSとTで等しくなる。これによって以下のような場合分けができる。Tのタプル列の長さが1の場合これは単純にSの要素をひとつずつ見ていって愚直に数えれば良い。Tのタプル列の長さが2の場合これもSの要素を2つずつ見ていけば数えられる。Tのタプル列の長さが3以上の場合このときSのある箇所がTの部分文字列であるための条件はすべてのタプルについて、文字が一致する両端以外のタプルについて、回数が一致する両端のタプルについて、Sの回数がTの回数以上であるのすべてが満たされることである。このような部分をSから見つけ出すためには文字だけに着目して文字列検索を行い、Sの中でTと一致する箇所を列挙する(両端以外の)回数だけに注目して「数字列」の検索を行い、Sの中でTと一致する箇所を列挙する以上2つの前処理を行っておけばよい。前者で列挙した文字列一致インデックスを舐めていき、後者で列挙した数字列インデックスに対応する箇所(両端以外の列)が存在しているか、またS側の両端の回数はTの両端の回数と一致しているかを確認する。すべて満たされていればカウント+1となる。len(T))でできる。枝刈り全探索https://codeforces.com/problemset/problem/453/B問題概要N要素の正整数列Aが与えられる。最小となるような数列Bを構成せよ。相異なる2要素が互いに素であるという条件から「1は何回でも使える」「1以外の数は最大でも1回しか使えない」ことがいえる。Aiが最大でも30までという制約の小ささに注目すると、1が何回でも使えることからBに対して59以上の数は使う意味がないということがわかる(代わりに1を使えば必ずAとの差は小さくなるので)。場合、BiとBjをswapすれば必ず最終スコアは小さくなる)。互いに素の条件から、ある数を使ったときそれとのGCDが1でない数は以降使えなくなる。使える数はたかだか60なのでどの数がもう使えないかは64bit型整数で管理することができる。以上の条件をすべて踏まえると、【今見ているインデックス、使える数の最大値、もう使えない数のビットマスク、現在の差の合計】あたりの値をもってDFSで全探索していくことができ、制限時間も長いのでこれで十分間に合う。正整数nに対してf(n)をnの10進表記での桁数と定義する。r)の組が何通り存在するか求めよ。108解法まず桁数が少しでも大きくなると「ある桁全体を覆うような区間」はそれだけで簡単にSを超えてしまって解になりえない。よってf(l)>=8のケースでは区間がある桁をまるまるまたぐということがありえないため、f(l)とf(r)の差はたかだか1にしかならない。これを元に以下のように場合分けをする。ときとりうる区間が結構面倒な形になりうるが、ここまでの大きさなら数列を陽に持った上で尺取りをやる形の全探索ができる。rの方は8桁の方に少し飛び出す可能性があることに注意する(厳密にやらずとも適当に5×107くらいまで持っておけばまあ足りる)。長さ1の区間の最小値が8)。ような形になる([]はここでは切り捨ての意)。前半の(K-S%K)個が[S/k]という形である。Sがkで割り切れないとき、このようなfの並びはただ一通りに定まる。よって1<=k<=S/8かつSの約数でないkの数だけ答えに+1が加わる。Sがkで割り切れるときはすべてが[S/k]となる。これはつまりf(l)=f(r)となるケースで、このときはその桁の中で好きに区間をとることができる。このケースをカバーするためにはSの約数を全部求めてf(l)を列挙すればよい。このとき区間長が上述の範囲に収まっているかチェックする必要があることに注意する。各文字が0または1のどちらかからなる長さNの文字列Sが与えられる。r]の中に同じ文字が3文字以上等間隔で並んでいるものの数を求めよ。3×105解法なんかこの条件を満たさないのはすごい難しいんじゃないかと考えて小さいNで実験コードを書いてみると10文字以上くらいになると必ず条件を満たす3文字が存在してしまうことがわかる。問題記録https://codeforces.com/problemset/problem/1156/D問題概要N頂点の木が与えられる。木の各辺は0または1のコストを持つ。単純パスで、かつ辺が「0個以上の0コスト辺」→「0個以上の1コスト辺」の順序で並んでいるパスをvalidと呼ぶ。2×105解法UnionFindを2つ作って、「0コスト辺だけを見たときの連結成分」と「1コスト辺だけを見たときの連結成分」を別々に作る。このとき同じ連結成分に属している頂点同士のペアは明らかにvalidであるので、連結成分ごとにこれをカウントする。単純な掛け算だが、ペアの順番はどちらもとれることに注意する(<x,y>も<y,x>も取れる)。次に各頂点ごとに「その頂点が属す0コスト辺での連結成分」と「その頂点が属す1コスト辺での連結成分」を見ると、前者から後者へのパスは「今見ている頂点を境に使う辺が0から1へと切り替わる」ようなvalidパスとなり、これも集合サイズの単純な掛け算でカウントできる(今見ている頂点自身は数に含めないことに注意する)。このような数え方は明らかに漏れ・ダブリがない。よってこれらを合計したものが答え。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。