かんプリンの学習記録

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

ABC333 F - Bomb Game 2

問題はこちら 目次 問題概要 解説 提出プログラム 感想 問題概要人の人が一列に並んでいる.先頭の人をの確率で列から取り除き,の確率で列の末尾に移す.人が最後の1人になる確率を求めよ. 解説人の列で先頭から番目の人が最後に残る確率をとします. 先頭…

競プロ用のツールを作ってみた

この記事は競プロ Advent Calendar 2023 16日目 のために作成されました。目次 ランダム生成ツール 使い方 グラフ可視化ツール 使い方 開発者募集 ランダム生成ツール作ったものはこちらです。 https://kanpurin.github.io/RandomGenerator/使用する場面とし…

ABC299 G - Minimum Permutation

問題はこちら 目次 問題概要 解説 提出プログラム 感想 問題概要以上以下の整数からなる長さの数列の長さ部分列であってが回ずつ登場するもののうち,辞書順最小のものを答えよ. 解説辞書順最小と言えば,前から貪欲に置けるもののうち最も小さいものを順に…

yukicoder No.2264 Gear Coloring

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

ランダム生成まとめ

メモ用なので適当に書く.目次 1以上M以下の整数からなる長さNの数列 重複あり 重複なし N個からM個選ぶ組み合わせ 1以上M以下の整数からなる長さNの単調増加数列 総和がMとなる非負整数からなる長さNの数列 括弧列 二分木 ラベル付き木 次数列を持つグラフ …

ABC287 G - Balance Update Query

問題はこちら 目次 問題概要 解説 提出プログラム 感想 問題概要種類のカードがあり,最初,種類目のカードの得点は,枚数は枚である.以下の形式の個のクエリを順に処理せよ. 種類目のカードの得点をに変更 種類目のカードの枚数をに変更 枚のカードを選ぶ…

ABC285 E - Work or Rest

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

ABC284 G - Only Once

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

ABC284 F - ABCBAC

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

EDPC S - Digit Sum

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

ABC275 F - Erase Subarrays

問題はこちら 目次 問題概要 解説 提出プログラム 解説 問題概要正整数列に対して次の操作を回以上行う. から連続部分列を選び,削除する. に対し,の要素の総和をちょうどにするために必要な操作回数の最小値を求めよ. 解説操作も制約も明らかにDPの気配…

燃やす埋める纏める

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

ABC186 E - Throne

Baby-step Giant-stepを用いた別解です。問題はこちら 問題概要 解説 提出プログラム 感想 問題概要円状に並べられた個の椅子があり,そのうちつは玉座である。玉座の個右にある椅子から始めて,回につき右にある椅子に移動していく行動を繰り返すとき何回目…

燃やす埋める練習問題4

燃やす埋める(Project Selection Problem)の練習問題についての解説です。問題はこちら ポイント 問題概要 解説 操作1のみしか行わない場合 操作2も行う場合 提出プログラム 感想 ポイント (論理包含)タイプの制約 問題概要頂点辺の有向グラフが与えられます…

ABC259 G - Grid Card Game

問題はこちら 問題概要 解説 グラフの構築 提出プログラム 感想 問題概要枚のカードがグリッド上に並んでおり,にあるカードにはが書かれている.行からいくつか選び,選んだカードの上に赤いトークンを置く.列からいくつか選び,選んだカードの上に青いト…

燃やす埋める練習問題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.2013 Can we meet?

ほとんど公式解説と同じなので簡単に書きます。問題はこちら 問題概要 解説 提出プログラム 感想 問題概要2点がそれぞれ上下左右に移動することを回繰り返す.移動は左右にはの確率で,上下にはの確率で移動するとき、2点が回目の移動直後に初めて重なる確率…

yukicoder No.2002 Range Swap Query

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

ABC256 D - Union of Interval

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

yukicoder No.1964 sum = length

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの正整数列のうち以下の条件を満たすもの数を求めよ. ただし,はを10進表記したものを文字列として見たときの長さ. 解説要素をとしたときの(スペースを含めた)長さとの差は となる. が答え.…

ABC240 G - Teleporting Takahashi

形式的冪級数を用いた解法です.問題はこちら 問題概要 解説 提出プログラム 感想 問題概要三次元グリッドのマスから隣り合う6つのマスのうち,いずれかのマスへの移動をちょうど回行った後にマスにいるような移動経路数を求めよ. 解説移動の仕方は対称なの…

ABC238 G - Cubic?

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列が与えられる.以下の個のクエリを処理せよ. が与えられる.は立方数か答えよ. 解説この問題はMo's algorithmを用いて解くことができます.が立方数であるということは,を素因数分解し…

ABC234 D - Prefix K-th Max

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要の順列および正整数が与えられる.について以下の値を求めよ. の先頭項のうち,番目に大きい値 解説公式解説にもある通り優先度付きキューで解けますが,BinaryTrieでも解くことができます.Binary…

トップページ

競技プログラミング 典型問題メモ 線形計画問題・整数計画問題に帰着される問題 Python高速化まとめ 数学メモ グリッドの最短経路の数え上げまとめ 特殊な形式的冪級数 燃やす埋める纏める ランダム生成まとめ

ABC231 C - Counting 2

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

ABC232 G - Modulo Shortest Path

問題はこちら 問題概要 解説 例 提出プログラム 感想 問題概要頂点のグラフがあり,頂点から頂点に重みの有向辺が張られている.頂点から頂点までの最短距離を求めよ.解説であるからは なら なら となります.頂点をでソートすると,各についてとなるやとな…

ABC212 C - Min Difference

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