問題ページ 解法 順列全てや部分列それぞれについて計算しろといった問題で与えられた通りに数えるのはTLEしてしまうので別の視点から数え上げるのが有効な場合が多い。今回の問題ではi番目の長方形が底でj番目の長方形の高さまで水が入っているような並び方…

問題ページ 解法 3つ組のうちaとcを動かしていくことを考える aがcを追い抜かすことはない [a, c]についてs[a]=='D'であれば答えに sum(区間[l,i]のMの数) (a<=i<=c, s[i]=='C') を加算する 現在の区間についてMの数(=mnum)、Cの数(=cnum)、DMC(=now)の数を…

問題ページ 考えたこと 上のbitから順番に決めていく 2^i > 2^i-1 + … + 2^0 より上のbitから貪欲に決めてよいはず 2^i の位が1となっている区間がk個以上存在した場合、2^iを1とできる 一旦1と決めた位が合った場合、その下の位で使える区間が限定される i…

問題ページ 解法 木DPを行う。dp[i][j][k]=(j回動かしたときに頂点iにk個(=0,1か2個以上)ビー玉が存在するような初期配置の数) と定義してDPをする。頂点iの子をc_0とc_1とする。これらの子の情報dp[c_0]とdp[c_1]をマージする方法について考える。j=0~d(頂…

問題ページ 考えたこと addとcheckだけなら簡単 completeで辺がO(N^2)本できるので辺を持つとやばい 辺はやばいけど頂点を持てばO(N)個しかない completeで完全グラフになった頂点集合をまとめておけばよさそう checkはaddで追加された辺に該当するものがあ…

問題ページ 解法 転倒数が答えになるので転倒数の定義を考える。最初の数列をA、最終状態の数列をBとする。(転倒数) = (A[ia]=B[ib]=x,A[ja]=B[jb]=yとしたときにia<jaかつib>jbとなるペア(x,y) (x</jaかつib>

問題ページ 考えたこと 45度回転 これ以降チェビジェフ距離で考える 距離が等しい点はある正方形上の点になる 2点を固定してその2点のどちらとも距離が等しい点を探す 各点を中心として2点間の距離*2を1辺の長さとする正方形を書く 2点どちらとも距離が等し…

問題ページ 考えたこと とりあえず実験 部分集合の大きさを4に固定してみる 1つ目の集合に異なる要素が3個は入っていないと、積集合の大きさが1となる条件を満たせない 1つ目と2つ目、1つ目と3つ目、1つ目と4つ目については以下のように取れば条件を満たす 1…

問題ページ 思考過程 ジグザグにするのがよさそう 一番小さい、大きいのを端に置くと損してる ジグザグな山みたいなのをつくるのがよさそう 一番小さいのを中央に置くか、一番大きいのを中央に置くかで2種類あるのに気をつけながら書くと通った #include <bits/stdc++.h> us</bits/stdc++.h>…

問題ページ 解法 回文が成り立つ⇔奇数個の文字が1種類以下 である。回文が成り立つかの判定を高速にするため hash = (文字種iが奇数個だったらiビット目を1とする) となるハッシュを考える。このハッシュを使うと 回文が成り立つ⇔1のビットの数が1個以下 と…

問題ページ 考えたこと ロボットiの前にたくさんロボットがいるとロボットiがゴールするのは不可能 ロボットiがゴールする前にある程度捌けてもらわないといけない ロボットiがゴールするのに必要な条件を考える 1 or 2マスジャンプなので2台連続でロボット…

問題ページ 考えたこと sample1のうちGBGGBGみたいな部分列は一方向から入れ続けても全部消せる 上のような部分列は当然消せる これを消した後はRGBGBRみたいに同じ色が絶対に隣り合わない列となる 筒に入っているボールをできるだけ消すとして考えてみると…

問題ページ 考えたこと とりあえず木DPっぽい dp[頂点i][部分木iでまだペアが確定していない頂点の数j] みたいなのを考える 頂点数がdpテーブルに来てるし二乗の木DPっぽい 遷移がどうなるか考えるけど全くまとまらない 数学できれいになるのかなあと思って…

問題ページ 考えたこと まずどんな動きをするのか試してみる 進行方向が反転だったりを考える必要はなくて目的地までの距離だけ使えばよさそう 現在の目的地までの距離をXでd[i]を入力するとX' = min(X, abs(X-d[i])) に変化する Xは単調に減少していくいう…

問題ページ 考えたこと Q=1ならどうか？ SとTの間に重み0の辺を張ってMSTを求めればよい MSTを求めるのをQ回やったら当然TLE MST+αのやつは元のグラフのMSTを求めてそこからいじるのがよくあるパターン 元のグラフのMSTと辺を追加したグラフのMSTは何が違う…

問題ページ 部分点 たぷとたぴが連結にならないようにする→カットなので最小カットを求めればよい。N<=500ならば最大フローを求めるアルゴリズムで間に合うのでdinicなどのライブラリを貼ればよい。 満点解法 木DPをする。dp[i][j] = (頂点iの部分木でiと連…

問題ページ 解法 bitDPで数え上げる。dp[S] = (集合Sがすでにチームが決まっているときの組み合わせ数) とする。TをSに含まれない要素の集合とすると集合Tから1人、2人、3人を選んでチームとする。このチームをSに新たに加えた集合をS'とするとdp[S'] += dp[…

問題ページ 考えたこと 区間が何個取れますかなので区間スケジューリングっぽい 都市Aに行ったあと王国に帰るなら一番早い依頼をうけるべき 王国→都市→王国 と移動するのにかかる区間を列挙しておく この区間を何個取れますか？という問題になった これは区…

問題ページ 考えたこと 1円玉が奇数枚だったら無理 10円玉が奇数枚だったら1円玉で10円分をつくらないとだめそう 100円玉が奇数枚だったら10,1円玉で100円分をつくらないとだめそう 貪欲に取っていくのを書いたら落ちた 冷静になって考えると100円玉が10^9枚…

問題ページ サンプル2眺めてたらA,Bまとめて小さい方からN個取れるとうれしい気持ちになって他のサンプルもそれであったのでそれで考えた。大体合ってたけどB問題で時間溶かしたら詰めきれなかった。 解法 A,Bまとめて小さい方からN個取ったときにハミルトン…

問題ページ i番目がカウントされる回数= sum_{j=1}^N (j番目を取り除く時にi番目と連結なパターン数) までは考察できたけど連結なパターン数を求めるパートで無限に詰まって終了した。数え上げで全通りの数え上げは実質期待値と同じなので確率っぽい考え方が…

問題ページ 考えたこと 出目i,jを使わずにK面サイコロをN個降る組み合わせ数がわかればよさそう dp[i][j] = (i面サイコロでj個振るときの出目の組み合わせ数) とする これは実質パスカルの三角形なので dp[i][j] = dp[i-1][j] + dp[i][j-1] としてO(N^2)で求…

問題ページ 1を2個並べると1(=2^1-1)通り、1を4個並べると7(=2^3-1)通り、1を2n個並べると2^(2n-1)-1通りみたいになってるのでうまく2べきっぽいのを作って貪欲に取るみたいな方針でハマって終了した。回文系でよくあるんだし片方は固定してしまってもう片方…

問題ページ 考えたこと HとWが偶数だと考えやすそう Wが奇数だったら1列分どう頑張っても1種類目のタイルを置けない なので1列分2種類目のタイルを敷き詰めてしまってよさそう Hが奇数のケースも同様に1行分1種類目のタイルを敷き詰めてよさそう これでHとW…

問題ページ 考えたこと sampleを試すと数をつくるには 0,1,2,3,4,5,… と1ずつ増える列を組み合わせてつくる以外不可能そう i < a[i] となるiがあれば a[i] を作るのは不可能なので-1 0,0,2,3 のような2以上増えているような列は作れるか？ 一回x[1]=1にした…

問題ページ 考えたこと 集合を2分割する系なのでDPを考える 集合に入っている要素のうち一番大きい要素が大事 集合が空のときを考えるのは面倒なのでX,Yには-infが入っているものとしておく dp[i][j] = (集合にs[i]まで挿入していて、Yに最後に入れた要素がs…

問題ページ 解説を読んだ。 解法 数式で扱いやすい形に変形 公式解説にある通り対称な位置の計算、位置の期待値の計算を扱いやすい形(置換)に変形する。 置換をダブリングで高速に計算 K回置換を計算するのは二分累乗、ダブリングの要領で高速にできる。置換…

問題ページ 思考過程 よくわからないのでサンプルを試してみる i日目の昼にxで回ってきたら次に補充されるタイミングには x%b 個になってそう x%b > c であれば補充できず、mod bなのでb未満なので続けられなくなる よくよく考えてみると b > c のときとかが…

問題ページ 解法 単語のリストwをソートしたものを使うと二分探索で接頭辞がpの単語の集合がわかる。各単語を反転したリストw_invをソートした物を使うと二分探索で接尾辞がsの単語の集合がわかる。wとw_invをそれぞれ座標軸にとった二次元平面上にプロット…

問題ページ 解法 円なので2次元っぽいが円の中心のy座標が0なのでこれは1次元の問題である。各円は[x-r,x+r]の区間に置き換えられこの区間でK重に内包されているよな区間があればそれはレベルKのターゲットである。区間がたくさん来たので終端でソートしてみ…