問題ページ まず，各ケーブルについて爆弾 のスイッチを反転するという形に書き換えておきます． 爆弾のスイッチについて差分XORを取っておくと，区間に一様にXORするという操作は2点にXORを行う操作に帰着できます．この操作を繰り返し行ったときに，値を全…

問題ページ 36 を支払うときに価値1の紙幣を使う枚数は「6枚」か「0枚で価値10の紙幣1枚を支払ってお釣りで価値1を4枚もらう」の二択です．このように，各価値の紙幣を使う方法はぴったり同じ枚数を用いるか，一つ上の価値の紙幣を使ってお釣りをもらうかの…

問題ページ 番目の数が 以上か？という判定問題に単調性が存在することから，こうした問題では 番目の数を決め打つ二分探索を行うのが常套手段です． 「 番目の数が 以上か？」という問題は「 未満の数が 個以下か？」と言い換えることができます． を固定し…

問題ページ 個の整数から選ぶ部分をとりあえず無視して， の表に対して条件を満たす数列 を考えます．まず，数列の先頭を0で固定してしまいます．先頭を0にしたとき，数列の先頭以外の部分については， でかかる条件から二択しかありえません． もしくは と…

問題ページ 考えたこと 長さ のパスグラフを作ったあと、 未満の経路ができないように辺をつなぐみたいな感じで考えてた ラベルを無視して数え上げたあと頂点にラベルをつければいいかと思ったら、ラベルをつけるパートが大変でダブらずに数える方法が何もわ…

問題ページ 数式を用いて問題を整理します．ベクトル に対して， となる は何種類ですか？という問題になりました． もし， が異なる場合は全て違う点に移動するならば， となるような が何種類か数える問題となり，これはcombinationを用いた計算で求めるこ…

問題ページ 順列を決めたときの転倒数の期待値を考えます． について， を 番目のほうが小さいならば1，それ以外ならば0となる変数とします．このとき，転倒数の期待値は となります．期待値の線形性から と一致します． は が1個成り立つごとに 増えます． …

問題ページ 考えたこと 差がmid以下にできるか？が解ければ，二分探索で解ける 差分を決め打ったところでつらそう min と max を決め打ってみる 全ての人の満足度をこの範囲に収められるか？ dp[i人目まで][残りのみかんj個] = 可能か？ 普通にやると かかる…

平衡二分探索木できることが多くてよくわからないのでまとめ 平衡二分探索木については プログラミングコンテストでのデータ構造 2 ～平衡二分探索木編～ がわかりやすい 平衡二分探索木にモノイドが乗る話については Implicit Treap - 競プロ練習記録 がわ…

数学的に厳密なことはしりません 高速ゼータ変換／高速メビウス変換 - naoya_t@hatenablog にあるようにゼータ・メビウス変換が色々あって何が何？？？と思っていたが，ゼータ変換・メビウス変換を理解する - Qiita によるとゼータ変換は半順序集合上で定義…

問題ページ 最小の重み を持つ頂点 について考えてみます．この頂点が隣接する頂点 が より大きい重みしか持たないとします．このとき， を違う色で塗ることは明らかに不可能です．同じ色で塗る場合，別の隣接する頂点へ進む経路で を達成する必要があります…

問題ページ 0-originで考えます． 制約からメタ読みするとどうせ かけて列挙するので，並べ替えた後の列で表が赤になるカードの集合を 通りを決め打ちます．「このような並べ方が存在するか？存在するならば何回のswapで達成可能か？」という問題が解ければ…

問題ページ Codeforces #613 (Div. 2) F. Classical? (R2800) - けんちょんの競プロ精進記録 のスタックの中に互いに素なものの個数を数える部分についてちょっと悩んだのでそこだけ書きます． 「スタックの中に が存在する． と互いに素なものの個数を数え…

問題ページ 区間 が与えられたとき，数列 の区間 に+1した数列を考える．そのまま数列をつくるとMLEなので，座標圧縮しておく．区間が交差しているかどうかを考えたいとき， と隣接していると結構大変なので，各端点を2倍して としておくと交差しない区間の…

問題ページ Trie木を考える．上の桁(Trie木の浅い方)から順番に見て，0にできるならば必ず0にするべきである ( なので)． 上から 桁目に0しかない: の 桁目を0にすれば答えの 桁目を0にできる 上から 桁目に1しかない: の 桁目を1にすれば答えの 桁目を0にで…

問題ページ 0-originで考える． より， となる． は一定なので，結局 が取りうる値の種類数を数えられればよいことがわかる． 例として要素を3個 選んだときの について考える．これは となる． が取りうる値は， 以上， 以下となる． は1刻みで値を変えられ…

問題ページ 辞書順最小を求めるのときの定石の一つとして，あとの方をうまく並べることで（辞書順最小を無視して）答えとなる要素のうち，最小のものを末尾に追加する操作を繰り返すという貪欲法がある．擬似コードを書くと以下のような感じ． REP(i, n) { R…

問題ページ 関連する問題を一つ示す． 「数列 を 回巡回シフトしたときに に一致するような を求めろ．」 この問題はZalgorithmやKMP法やローリングハッシュなどで解くことができる．ここではZalgorithmによる解法を示す． (適当な区切り文字) と連結した数…

問題ページ 答え = (N-1)! * 期待値 期待値 スライム が を通る確率 スライム j が [i,i+1] を通る確率 → j+1~i が j より前に選ばれる確率で 1/(i-j) → jだけの式にしたほうが楽なので変形すると 1/j ～ の後に が来る確率が なのとか立式するパート実質 AG…

AOJICPCを解いてたら思ったより手こずったのでその反省 AOJ2904 GuruGuru RLLLRRR みたいなのを数えて1WA 問題文に書かれていることをちゃんと書く AOJ2846 Slimming Plan 1週目だけで達成できるパターンを忘れてた 二分探索の結果が oxxxxxoooooo みたいな…

木をパスの素集合に分解して，それぞれのパスをスプレー木で表します．各パスの親になる頂点へ向かって辺を貼ることでパス同士の連結関係を表すみたいな感じ．平衡二分探索木で表しているのでsplit/mergeの要領で色々操作ができてうれしい． このスライド が…