解法2解説PDFから。bなので、「vがN以下かどうか」だけを考えれば良いことがわかる。上からiビットまで決まっているとき、j=vとなる通り数が考えられる。このままだと、jの部分がNまで考える必要があり、N<=10^18なので、メモリが足りない。ここで、jを「上からiビットまでの部分だけ」で考える。上からiビットまで決まっているとき、(N>>i)-j=(v>>i)となる通り数というのを考える。・・・のような遷移になる。上記の遷移は周期性があり、j=2以上のときは、j=2以上のところにしか遷移しないため、「2以上」というふうにまとめ上げて計算してもよい。3とすることができる。dp[0][j]になる。クエリ全部盛り問題すべての要素が0で初期化された長さNの数列{a_i}が与えられる。Q個のクエリが与えられるので、処理せよ。各クエリ(q,l,r,k)はqの値に応じた処理を行うこと。範囲更新として、遅延セグメント木を検討する。遅延セグメント木を考えるため、モノイドMと作用素Opの構造、それらの写像、単位元を考える。モノイドMについて必要そうな構造を考える。query処理で必要なのはq=0の時で、Σa_iが必要。q=4で、iについてのF_i値がそれぞれ個別に必要となる。F_i}という元を考える。F_i+F_j}で考える。次に、上記のMを踏まえつつ、作用素Opについて考える。いま必要なのは「kに置き換える」「kを加える」「kをかける」「k*F_iを加える」の4操作になる。F_i}になるように考えればよいことがわかる。区間に対する操作で、要素数に応じて変化する部分を考える。区間の要素を一様にx倍する場合は、要素をまとめあげた区間の構造に対してx倍するのと変わらないが、xを加える場合は、要素数*xが増えるので、考慮する必要がある。F_i}になるように考えればよい。c*p+r)と計算してあげればよい。作用素の単位元は、何も作用しないのと同じになる(1,0,0)を考えればよい。ここまでで、遅延セグメント木を適用でき、十分高速に答えを求められる。Equilateral問題HxWのグリッドにコインがいくつか置かれている。このとき、相異なるコインの3つ組で「その3つのうち、どの2つのコインを取っても、それらの存在する座標の間のマンハッタン距離が一定」であるようなものの個数を求めよ。「マンハッタン距離が一定」というのは、実際に図示してみると、ある点を中心とした正方形を45度回転させたところになる。他の2点はこの正方形の線上に乗っている必要がある。適当に2点を定めてみると、該当する点の範囲(赤い領域)は以下のように絞られる。W*H)になってしまい間に合わない。ここで無駄なところを探してみると、「ある点xを決めた場合、残り2点のうちどちらかは必ずxの45度斜めに存在する」、ということに気付く必要がある。ある点xに対して、45度斜め方向にある点yがある場合、最後の3点目zは上の図の一番右の図のように赤い範囲の部分となる。)で、全体としてO(W*H*(W+H))≒O(N^3)程度で求められる。上記のアルゴリズムを実装するのに、単純に45度の4方向すべてに対して求めると重複で数え上げてしまうので、その分を引いてあげる必要がある。解説放送では、盤面全体を90度回転を4回行い、それぞれの回転ごとに、以下の部分をカウントする方法が紹介されていた。ある点xについて、その右上方向の45度方向にだけ点yを探し、点zの範囲のうち、一番右上の部分だけカウントしない。そのカウントしない部分に点zがあった場合は、時計回りに90度回転したときにカウントされる。右下の範囲については、180度回転した場合にカウントされ、右上のカウントしないところも270度回転したときにカウントされるので、重複なくカウントできる。添え字間違い、範囲外アクセスなどしまくった。怪しい部分は範囲外アクセスなどしていないかチェックする。あと、斜めのまま実装したけど、「絶対値を見たら45度回転」から45度回転した状態で処理した方がいろいろミスがなさそう。Blocks問題1~Nの番号が書かれた箱が1列に並べてあり、各箱の重さは整数A_iで与えられる。この箱を一つずつ取り除いていくことを考える。ある箱を取り除くときのコストは、その両隣に連続している箱の重さの総和になる。取り除き方はN!通り考えられるが、そのすべての取り除き方について、N回の取り除くコストの総和の合計を求めよ。A_i」で求められる。制約的にこの計算をO(NlogN)以下の計算量で行う必要がある。(気付くのが厳しいが、)全事象を考えているので、確率的に考えて期待値を求めることでこのe_iを求める。p_ij」で求められる。(abs(i-j)+1)と求められる。今、MODで計算しているため、p_ijは逆元を計算しておけば整数値になる。Σp_ijを考えるとき、p_ijは1/1+1/2+1/3+...のように連続した和になるので、累積和を求めておけばO(1)で求められる。A_iもO(N)で求められるので、全体でO(N)で求められる。反省DPや法則性の方向で考えてしまっていたので、確率・期待値の発想がまったく考慮できていなかった。Polygon問題M頂点の凸多角形の頂点同士をN本順番に線分で結ぶ。このとき、頂点は一度線分に使われたら2度は選ばれない。i番目に結んだ線分の頂点a_iとb_iの情報が与えられるので、追加した線分同士の交点の総数を答えよ。頂点a_iとb_iを結ぶときは、始点終点ではないので、a_iとb_iを交換してもかまわないことがわかる。重要な性質として、「頂点を結ぶ順番は関係ない」ということに気付く必要がある。交点ができるケースを考えるために、多角形を直線上にのばして、線分を曲線で表した以下のような図を考える。今は、太線の線分を追加する場合を考える。交点ができるケースは、1と3のケースで、a_iからb_iの間にある頂点に、a_i以下b_i以上の頂点からの線分がある場合になっている。図の左側付近(1と2のケース)を考える。b_kとする)は、a_kがa_iよりも右側にある。したがって、「頂点を結ぶ順番は関係ない」性質から、左側から順番に線分を追加していき、すでに結んだ頂点のうち、bにあたる部分がa_iとb_i内に何個あるか?がわかればよい。これはBITなどでO(logM)で求められる。図の右側付近(3のケース)を考える。3を追加する場合を考えると、これは上記の1のケースに当たるので、太線の追加時には考えなくてよいことがわかる。各文字は0または1の長さnの文字列sが与えられる。n頂点の木について考えたとき、i文字目が0なら、木からどのように辺を1つ取り除いてもサイズiの連結成分が作れないi文字目が1なら、木からある辺を1つ取り除いてサイズiの連結成分を作れるを満たすような木を実際に1つ構築せよ。構築できない場合は-1を出力せよ。最後の文字が1の場合は構築できないリーフの頂点につながる辺を除くと連結成分が1のものが必ずできるので、最初の文字は必ず1でないといけない辺を取り除いてサイズxの連結成分ができたら、対称的にN-xの連結成分ができるので、文字列は最後の文字を除いて対称になっていないといけないということがわかる。以下、上記の条件を満たすような文字列について考える。今、満たしたい連結成分集合が{1,3,5,...}のような場合を考える。「1」は、リーフの部分の辺を切ればよい。「3」は、木の形を考えてみると、以下のようなものになる(赤枠と交差している辺を切ればよい)。「5」は、上記の形を残しつつ、5個の頂点を入れる必要があるので、以下のように青枠を考えればよい。「5」ではなく「6」だった場合は、以下のように頂点を増やせばよい。上記のように、与えられた連結成分集合の小さい方から考えて、それまでの形を残しつつ、順次構築していけば目的の木が作れる。上記の木は、「キャタピラ木」といい、線グラフの各頂点にいくつか頂点を生やしたような木になっている。Wikipedia生やした部分はリーフなので、必ず連結成分は1のものができ、線グラフの部分の辺を消すことが題意に相当する。発想をするようにしていれば効率的にたどり着けたかもしれない。Tr/eeTweet広告を非表示にするもっと読むコメントを書く次のページプロフィールid:phyllo_algoレッドコーダーへの道のりは遠い。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。