かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

典型

yukicoder No.2264 Gear Coloring

問題はこちら 目次 問題概要 解説 提出プログラム 感想 問題概要歯車が個あり,歯車は枚の歯を持つ.歯車と歯車が噛み合っている.これらの歯車の歯に色の色を塗る方法は何通りあるか.ただし,回転によって一致する色の塗り方を同一視する. 解説ポリアの数…

ABC285 E - Work or Rest

問題はこちら 目次 問題概要 解説 提出プログラム 感想 問題概要曜日からなる一週間の各曜日に「平日」か「休日」のどちらかを割り当てる.このとき,曜日の生産量は以下のように表される. 曜日が「休日」である場合は 曜日が「平日」のとき,直前の休日が…

ABC284 G - Only Once

問題はこちら 目次 問題概要 解説 提出プログラム 感想 問題概要以上以下の整数からなる長さの整数について,,という数列にちょうど一度だけ現れる数の種類をとする. として考えられる個の数列全てにおいてを求め,その総和をで割った余りを求めよ. 解説…

ABC284 F - ABCBAC

問題はこちら 目次 問題概要 解説 提出プログラム 感想 問題概要長さの文字列が与えられる.長さの文字列であって,となるようなものを求めよ. 解説で文字列の文字目から文字目までの文字列とします. で文字列を反転させた文字列とします.すべてので以下…

EDPC S - Digit Sum

問題はこちら目次 問題概要 解説 未満フラグを持つDP 未満フラグを持たない方法 メモ化再帰 場合分け オートマトンDP 問題概要以上以下の整数のうち,十進表記における各桁の数字の総和がの倍数であるようなものはいくつか. 解説桁DPというものを用いると解…

燃やす埋める纏める

燃やす埋める問題の解説記事です

燃やす埋める練習問題3

燃やす埋める(Project Selection Problem)の練習問題についての解説です。問題はこちら ポイント 問題概要 解説 提出プログラム 感想 ポイント 負のコスト 複数の選択肢 機械的なグラフの構築 問題概要人の人が数直線上に家を建てようとしています。番目の人…

燃やす埋める練習問題2

燃やす埋める(Project Selection Problem)の練習問題についての解説です。問題はこちら ポイント 問題概要 解説 提出プログラム 感想 ポイント 最大化を最小化へ言い換える グラフ表現可能なコストの性質 2部グラフの性質を用いたの選択肢の順序変更 問題概…

燃やす埋める練習問題1

燃やす埋める(Project Selection Problem)の練習問題についての解説です。問題はこちら ポイント 問題概要 解説 提出プログラム 感想 ポイント 選択に対するコストからグラフを構築する 問題概要からなる文字列が与えられます。円支払うことにより、を(なら…

yukicoder No.2023 Tiling is Fun

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要平面上の を頂点とする六角形を考えます。 この六角形に次の3種類の図形を敷き詰めます。 yukicoder No.2023問題文中の画像これらの図形を回転・反転を許さずに、隙間も重なりもないように敷き詰め…

yukicoder No.2002 Range Swap Query

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列と個の操作があり,操作はとを入れ替える. 以下の個のクエリを処理せよ. 操作をこの順に行ったときのを求めよ. 解説このクエリはオフラインで処理できるのでMo's algorithmが使えない…

ABC256 D - Union of Interval

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要個の半開区間の和集合を求めよ. 解説以下のように半開区間の集合に新たに半開区間を追加することを考えます.このような追加を高速に行うことができれば解くことができそうです. 既に集合に含まれ…

ABC231 C - Counting 2

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列について以下の個のクエリに答えよ. が与えられる.となるの数を答えよ. 解説これはBinaryTrieで解くことができます.BinaryTrieは整数の(多重)集合を管理することができるデータ構造で…

ABC212 C - Min Difference

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列と長さの数列がある.を求めよ.解説愚直に実装するとになります.各毎にが最小になるようなを求めます.もちろんこのままだと毎にかかるのでダメですがをソートすることで以下の性質をも…

ABC230 E - Fraction Floor Sum

有名問題問題はこちら 問題概要 解説1 解説2 提出プログラム 感想 問題概要を求めよ.解説1答えはの領域内の格子点の数となります.(上の格子点の数はになるため) N=10の例この領域はに関して対称であるための領域内の格子点を数えて2倍します.とします.領…

TDPC T - フィボナッチ

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要少し変えてます. で定義される数列の第項を求めよ.解説の母関数をとする.は形式的冪級数を用いてと表される. なので, のときは のときはしたがってBostan–Moriのアルゴリズムを用いるとで解け…

yukicoder No.1100 Boxes

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要個の互いに区別できるボールを個の互いに区別できる箱に入れる入れ方であって,ボールが1個も入っていない箱の個数が奇数であるようなものの数を求めよ.解説 が答えとなる(回の選択のうち,を選ぶ…

yukicoder No.269 見栄っ張りの募金活動

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列であって,以下の条件を満たすものの数を求めよ. 数列の総和が 解説とし,とすると, となるの組の数が答えとなる.したがってDPによりで求められる. で求めることもできる.kanpurin.h…

ABC221 H - Count Multiset

形式的冪級数を用いた解法です.問題はこちら 問題概要 解説 提出プログラム 感想 問題概要について以下の値を求めよ. 個の正整数から多重集合のうち,以下の2つの条件をすべて満たすものの個数 要素の総和が 任意の正整数を高々個しか含まない 解説多重集…

ABC217 G - Groups

問題はこちら 問題概要 解説 包除原理 さらなる高速化 提出プログラム 感想 問題概要以上以下のについて以下の問題を解け. からまで番号が付いた人を空でない個の集合に分ける.で割った余りが等しい人は同じ集合に含まれないような分け方の総数を求めよ. …

ABC216 D - Pair of Balls

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要個のボールがあり,各ボールにはから以下の整数が書かれたボールはちょうど2個ずつ存在する.本の筒があり,各筒にはボールが個入っている.異なる本の筒の一番上にあるボールの色が同じ場合それら…

ABC215 D - Coprime 2

問題はこちら 問題概要 解説1 解説2 提出プログラム 感想 問題概要長さの正整数列が与えられる.以下の条件を満たすをすべて求めよ. すべてのを満たす整数について,である. 解説1となるのは,がの任意の素因数を持たないことと同じです.のすべての素因数…

ABC214 H - Collecting

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要頂点辺の有向グラフがあり,人が人ずつ頂点から辺を辿って任意の回数繰り返す.人が人以上通った頂点のの値の総和の最大値を求めよ.解説ある強連結成分を通るときはその強連結成分の全頂点を通るべ…

ABC214 C - Distribution

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要人が円周上に並んでいる.番目の人は時刻に宝石をもらうと時間後にその宝石を番目の人に渡す.ただし,とする.また,高橋君は時刻に番目の人に宝石を渡す.すべてのについて,番目の人が初めて宝石…

【競プロ】数学メモ

競プロにおける数学関連のメモ

yukicoder No.1640 簡単な色塗り

公式解説とは別の解法です. 問題はこちら 問題概要 解説1:最大二部マッチング 解説2:2-SAT 提出プログラム 感想 問題概要と番号付けされた個の白い球がある.球または球を選んで黒く塗ることができるという操作を回行う.すべての球を黒で塗ることが可能…

ABC210 D - National Railway

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要行列のグリッド上の異なるマスを選ぶ,の最小値を求めよ.解説式の中に絶対値があって面倒なのでと決めることで絶対値を外す.グリッド全体を反転させれば他の場合も表せるので,の場合で求められれ…

ABC209 F - Deforestation

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列に対して以下の操作を行うことでの任意の要素をにするときのコストが最小となるような操作列の数を求めよ. を選びをにする.このとき,この操作を行う前の分だけコストがかかる. また,…

yukicoder No.555 世界史のレポート

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要最初紙に文字書いてある.コピーとペーストを行うことにより,紙に文字以上書いてあるようにしたい.コピーには,ペーストにはのコストがかかる.最小でいくらのコストがかかるか.解説連続でコピー…

yukicoder No.612 Move on grid

形式的冪級数を用いた解法です.問題はこちら 問題概要 解説 提出プログラム 感想 問題概要次元グリッド上のからマンハッタン距離がの格子点に移動することを回繰り返すしたあとにいるとして,となる確率にをかけた値を求めよ.各格子点への移動確率はである…