黄色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にしたとき，数列の先頭以外の部分については， でかかる条件から二択しかありえません． もしくは と…

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