有名問題問題はこちら 問題概要 解説1 解説2 提出プログラム 感想 問題概要を求めよ．解説1答えはの領域内の格子点の数となります．(上の格子点の数はになるため) N=10の例この領域はに関して対称であるための領域内の格子点を数えて2倍します．とします．領…
形式的冪級数を用いた解法です．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要ある路線には駅から駅までの個の駅がある．準急は駅に止まり，{駅駅 }の部分集合に止まり，駅に止まる．連続する個以上の駅に止まると，客が飽きてしまうので，その…
メモがてら書きます．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列を作る．各には個の選択肢があり，を選ぶとのコストがかかる．さらに，各についてのコストが追加でかかる．コストの総和の最小値を求めよ．解説複数の選択間にコスト…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要少し変えてます． で定義される数列の第項を求めよ．解説の母関数をとする．は形式的冪級数を用いてと表される． なので， のときは のときはしたがってBostan–Moriのアルゴリズムを用いるとで解け…
問題はこちら 問題概要 解説 アルゴリズム 提出プログラム 感想 問題概要を並び替えて得られる数列であって以下の条件を満たすもののうち，辞書順最初のものを求めよ． に対し，においてはよりも先に現れる． 解説ポイント 辞書順最小は前から貪欲 要素の追…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要個の互いに区別できるボールを個の互いに区別できる箱に入れる入れ方であって，ボールが1個も入っていない箱の個数が奇数であるようなものの数を求めよ．解説 が答えとなる(回の選択のうち，を選ぶ…
形式的冪級数を用いた珍しい(と思った)解き方がある問題集 (解けなかったやつも載せる)厳密には形式的冪級数ではないもの(有理数の指数が出るもの)も載せてる．ABC221 H 解説とする． なのでDP遷移がわかって解ける．ABC222 H 解説であるので はの逆関数とな…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列であって，以下の条件を満たすものの数を求めよ． 数列の総和が 解説とし，とすると， となるの組の数が答えとなる．したがってDPによりで求められる． で求めることもできる．kanpurin.h…
形式的冪級数を用いた解法です．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要について以下の値を求めよ． 個の正整数から多重集合のうち，以下の2つの条件をすべて満たすものの個数 要素の総和が 任意の正整数を高々個しか含まない 解説多重集…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列が与えられる．この数列の要素を一つ選びを加えるという操作を回まで行うことができるとき，の全要素のgcdの最大値を求めよ．解説となるための最小操作回数が以下であるかが分かればいい(…
グリッドの最短経路(North-East lattice path)の数え上げの例を解説していきます．よくある書き込み(動的計画法)による解法は扱いません．目次 最短経路の数え上げとは 一般的な最短経路 ある点を通る最短経路 ある点を通らない最短経路 ある長方形領域を通…
公式解説より効率の良いアルゴリズムの説明です．問題はこちら 問題概要 解説 関連問題 問題概要頂点辺の有向グラフが与えられる．各について，辺のみ通れないときの頂点から頂点までの最短距離を求めよ．解説頂点から頂点までの最短経路を一つ求めます．明…
問題はこちら 問題概要 解説 Pythonでの解法 感想 問題概要長さの木材がある．以下の個のクエリを処理せよ．番目のクエリはで与えられる． のとき：木材の左端からの地点で木材を切る． のとき：木材の左端からの地点を含む木材の長さを出力する． 解説現在…
問題はこちら 問題概要 解説 包除原理 さらなる高速化 提出プログラム 感想 問題概要以上以下のについて以下の問題を解け． からまで番号が付いた人を空でない個の集合に分ける．で割った余りが等しい人は同じ集合に含まれないような分け方の総数を求めよ． …
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要個のボールがあり，各ボールにはから以下の整数が書かれたボールはちょうど2個ずつ存在する．本の筒があり，各筒にはボールが個入っている．異なる本の筒の一番上にあるボールの色が同じ場合それら…
問題はこちら 問題概要 解説1 解説2 提出プログラム 感想 問題概要長さの正整数列が与えられる．以下の条件を満たすをすべて求めよ． すべてのを満たす整数について，である． 解説1となるのは，がの任意の素因数を持たないことと同じです．のすべての素因数…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要頂点辺の有向グラフがあり，人が人ずつ頂点から辺を辿って任意の回数繰り返す．人が人以上通った頂点のの値の総和の最大値を求めよ．解説ある強連結成分を通るときはその強連結成分の全頂点を通るべ…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要人が円周上に並んでいる．番目の人は時刻に宝石をもらうと時間後にその宝石を番目の人に渡す．ただし，とする．また，高橋君は時刻に番目の人に宝石を渡す．すべてのについて，番目の人が初めて宝石…
競プロにおける数学関連のメモ
公式解説とは別の解法です． 問題はこちら 問題概要 解説1：最大二部マッチング 解説2：2-SAT 提出プログラム 感想 問題概要と番号付けされた個の白い球がある．球または球を選んで黒く塗ることができるという操作を回行う．すべての球を黒で塗ることが可能…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要頂点の完全無向グラフから辺取り除く．このグラフの頂点から本の辺を辿るパス(一つの辺を複数回辿ってもいい)のうち終点が頂点であるようなパスの数を求めよ．解説頂点から頂点への長さのパス(厳密…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要行列のグリッド上の異なるマスを選ぶ，の最小値を求めよ．解説式の中に絶対値があって面倒なのでと決めることで絶対値を外す．グリッド全体を反転させれば他の場合も表せるので，の場合で求められれ…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列に対して以下の操作を行うことでの任意の要素をにするときのコストが最小となるような操作列の数を求めよ． を選びをにする．このとき，この操作を行う前の分だけコストがかかる． また，…
計算量は良くないですがすぐ思いつくので．あと，誤差におびえずに済む．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要二次元平面上の頂点集合とが与えられる．のすべて頂点に対して同様に，原点中心の回転と平行移動を行ってと一致させられるか…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要最初紙に文字書いてある．コピーとペーストを行うことにより，紙に文字以上書いてあるようにしたい．コピーには，ペーストにはのコストがかかる．最小でいくらのコストがかかるか．解説連続でコピー…
形式的冪級数を用いた解法です．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要次元グリッド上のからマンハッタン距離がの格子点に移動することを回繰り返すしたあとにいるとして，となる確率にをかけた値を求めよ．各格子点への移動確率はである…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの正整数列が与えられる．としてを求めよ．解説 できるだけ大きなを使いたい．であるから，貪欲で大丈夫．との比較はとを比較すればよい．もしくは，二分探索でも解ける．基本的には，https://a…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要整数が与えられるので，以下の条件を満たす整数組の数を求めよ． をの最大公約数とすると，以下が成立する． かつかつ 解説またはのときは条件を満たさないので，以下とする．各に対して，条件を満…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの正整数列が与えられる．以下の個のクエリに答えよ． 正整数が与えられる．のいずれとも異なる正整数のうち，小さい方から数えて番目のものを求めよ． 解説クエリを先読みすることで二分探索を…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要白いボール個と黒いボール個を一列に並べるとき，各について左から個のボールのうち白いものの個数を，黒いものの個数をとおいたとき，すべてのについてが成り立つような並べ方の数を求めよ．解説結…
