問題ページ まず，各ケーブルについて爆弾 のスイッチを反転するという形に書き換えておきます． 爆弾のスイッチについて差分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の要領で色々操作ができてうれしい． このスライド が…

6完1258で本番13位相当 (開始) いつもどおり手分けして読む．Lが簡単そうだったのでおるふぇに説明して書いてもらう． (14分) Lが通る．Bが簡単らしくおるふぇが書き始める．Iが解かれてるので考えると，LCAで2点の位置関係を見ればできそう． (42分) BがTLE…

問題ページ trie木を構成すると D - Game on Tree に帰着できる．追加するクエリが存在するが，文字列追加でgrundy数が変更される頂点の数は高々40個なのでその部分だけgrundy数を再計算すればよい． #include <bits/stdc++.h> using namespace std; using ll = long long; </bits/stdc++.h>…

問題ページ http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2270 のL番目を中央値に変更したものであるが，複数テストケースで15ケースあってTLが厳しくなっている．HL分解 + BIT でlog3つ，並列二分探索 + 辺重みを変更できるLCA でlog2つの解…

問題ページ 時刻 に座標 にいる粒子は，時刻 に座標 に存在する．よって， が同じ場合，同じ粒子であると判定できる． であるような4数が何通り存在するか求める問題に帰着できた． これは約数系包除で解ける．gcdがi以上であるような4数の組は 個で簡単に求…

問題ページ サイクル基底入門として解いた サイクル基底・サイクルの個数について - 競プロ練習記録 グラフのサイクルについて扱いたいけれど，サイクルの個数は多すぎてどうしようもないみたいなときに使える話．サイクルの対称差を演算として考えると，い…

問題ページ ナップサック問題のように 重みが最大の価値 としたDPテーブルを更新することを考える．このDPテーブルに となるクッキーを追加する場合，chmax(dp[(i+w)%mod], dp[i]+v) となる．クッキーを追加する順番にかかわらずDPの結果は同じであり，この…

問題ページ 解法1 横棒の消去を無視すると周期 で同じ列に戻ってくる．ある横棒 を消す場合，その横棒の左端/右端にくる列が何列目なのか求め，その位置をswapする．左端/右端にくる列を求めるには，0列目/w-1列目に当たるまで上に戻るを繰り返すことで で求…

問題ページ ぬくもり需要 をソートしておくと，おふとんを増やす操作のみに置き換えられる．したがっておふとんを積む順番は記録せずに，使ったおふとんの集合だけ記録すればよくなる． 日目使った布団の集合 最小の不快度の和としたDPを考える．このDPの遷…

問題ページ 障害物がなければ行列累乗をすればよい．障害物に対応するため障害物が存在する行ごとに区切って考える．行列累乗で 列目に到達する方法を求めたあと，障害物が存在する位置に到達する方法を0通りに置き換える． で解けた． #include <bits/stdc++.h> using name</bits/stdc++.h>…