問題ページ 経路を一つ固定したとき、寝過ごしたときに最悪となるパターンについて考える。辺 で寝過ごした場合、かかる時間は (始点からuまでの時間) + (uから終点までの時間) + (終点からtまでの時間) となる。経路上の各辺で寝過ごした場合の時間のmaxが…

問題ページ と表す。 は下から 桁目の値であり、 である。 となるような を求めたい。 の組は 通り存在するため、普通に全列挙するとTLEしてしまう。そこで半分全列挙を行う。 と についてそれぞれ和を列挙する。足したときに で0になるようなものが何個ある…

問題ページ まず のときの解き方を考える。 についてソートしておく。この数列の差分について小さい方から 個の和が答えになる。差分が大きいところから 個と一番小さい箱にドーナツを入れることでこれは達成できる。 数列の小さい方から 個の和を求めるのに…

問題ページ 原点からの半直線を引くので関係があるのは始点と終点の偏角である。各線分を[始点の偏角、終点の偏角]の区間に置き換えると、「ある区間の集合が与えられる。任意の区間についていずれかの要素を含むような偏角の集合のうち、最小の要素のものを…

問題ページ レベルが のときの答え、レベルが のときに2点を結ぶ方法、レベルが のときに同じ点を2回通るパターンを各レベルについて計算していく。それぞれ と表す。 各三角形内で完結するパターン + 三角形をまたぐパターン 三角形を2つ使うパターン + 三…

問題ページ まず答えの一番上の行を適当に定める。このとき入力の1~n-1行目までが正しく生成されるように、答えの2~n行目までを定めると一意に定まる。入力のn行目についても正しく生成されるような、一番上の行を探したい。 通りを全列挙することは不可能な…

問題ページ ビットごとに独立 ビットごとの論理和・論理積について考えているため、ビットごとに独立に考えることができる。したがって要素が0か1の の行列を構築できるか？の問題に帰着できた。 容易に決定できる要素 まず、0か1か確定させられる要素を決め…

問題ページ 文字列の長さは についてフィボナッチ数列になっている。したがって については一意に定まる。また、フィボナッチ数列で20000以下となるのは22番目までなので、 である。文字列は高々 個程度しか存在しないので、 を全列挙し、 と一致するか判定…

黄色difficultyあたりの適正難易度帯を昔やって忘れてるのもったいないので2周目 D - Connectivity UF2本もって(道路のufの根,鉄道のufの根)のペアをkeyにまとめる D - Ears 0, 偶数, 奇数, 偶数, 0 の5個の領域のどこにいるか？をDPのkeyに持つ 耳DP，DFAの…

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

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

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

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

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

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

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

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

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

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

問題ページ 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…

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

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

問題ページ と にクエリを飛ばしてRBと返ってきた場合，『x 「n-1個』 y」 で２つの区間でRBの数の変動に影響するのはxとyの高々2個しかない．n-1個の部分でRとBの数が異なる場合は不可能．よって の範囲内にはRBが 個ずつ存在する． このような範囲 + 1個 …

問題ページ 最短路問題+の条件なので dist[マスi][k] = 最短経路 というような拡張dijkstraをすればよさそう． 個の各頂点を始点として拡張dijkstra コンクリートのマスの数を とすると 止まる頂点はコンクリートとゴールのマスのみ 拡張dijkstraの頂点数，…

問題ページ ある列の高さを変更する場合，隣の高さに合わせる以外の中途半端な高さにして解が改善されることはない．よって前からDPを行うとき，番目を変更するならば番目の高さに揃えるとしてよい．番目の高さをのどれに揃えたか？という情報を持っておけば…

問題ページ 自分のコンテスト中の思考過程に沿って書きますが，公式解説の方がシンプルで高速に解けると思います．というか未証明です． まず， のペアを並び替えて が昇順になるようにする．この操作をしても一般性を失わない． 最も大きい に着目する． を…

問題ページ で0である桁について， を1にしたとしても と のビットカウントが1ずつ増加するだけである． が増えて損するだけなので， で1にする桁は も1の桁だけである． 下の桁から順に を0にするか1にするかを決定していくdpを行う． のうち を0/1のどちら…