Div.2TopCoder無事に全完。contiguous.)文字列sが与えられるので、重ならない同一の部分文字列の組の総数を求めよ。解説これは色々解き方はありそうですが、|S|≦50なので全探索で十分です。自分は部分文字列a,bの左端をループで指定し、一致するまで文字数を増やしながら答えに加算していくO(N^3)を使いました。reached.石の集まりがn、1列に並んでいます。要素nの配列a,bが与えられます。現在、塊iにはa[i]個の石がありますが、b[i]にしたいです。石を隣り合った塊に1つずつ移していくとき、最小何回石を動かせばよいか求めよ。解説yukicoderに似た問題が有った気がします...例として{5,0,0,0,0}→{1,1,1,1,1}を考えます。左端から石を4個1つ右に動かし、うち3個を右に動かし、2個、1個と移動させるので答えは10。この考え方を、今度は{0,0,0,0,5}→{1,1,1,1,1}に適用します。左端から-1個石を1つ右に動かし、そこから-2個を右に動かし、-3個、-4個動かすので、合計-10→10回石を動かしたことになります。違和感を覚えそう(自分自身覚えました)なのでもう1例。{1,0,0,4,0}→{1,1,1,1,1}は、左端から0個、-1個、-2個、1個動かします。それぞれ正に変えた上で足して答えは1+2+1=4。こんな感じで左から見ていけばOKです。1,000,000,007).n頂点からなる1つの無向木Tが与えられます。Tの部分木Aの大きさは「Aに所属する頂点の数」とします。全部分木の大きさXを1,000,000,007で求めてください。辺は線形乱数っぽいアルゴリズムで生成されます。適当に根を決めて、DFSします。この時に、「その頂点をルートとした時に、この後通る頂点を使ったX」が求まれば良さそうです。cnt[i]:頂点iをルートとした時のルートを使った部分木の大きさの総和kind[i]:cnt[i]に入っている木の数ある状態の木のルートiに新しく部分木(ルートはj)を付けることを考えます。この時、出来る木のcnt[i]には元の木のどのパターンもkind[j]+1回(新しい木を一切含まない場合あり)出ていて、加える部分木のどのパターンもkind[i]回出現することから、cnt[i]=cnt[i]*(kind[j]+1)+cnt[j]*kind[i]で更新できます。kind[i]も同様にkind[i]=kind[i]*(kind[j]+1)で更新できます。後は、各頂点のcntを全て足せばOKです。modを取ってください。https://github.com/HyogaGlacier/TopCoder/blob/master/683/Div2/Hard.cpp感想1159->1296(Highest)。Div1になりますが、事故って緑に戻らないように気を付けたいです。日)ネットの海に生息するらしいバーチャルグソクムシ。競プロとCTFをメインに、たまにEsolangを混ぜます。(7)月別アーカイブリンクGitHubはてなブログをはじめよう!Hyogaさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。