問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列が与えられる．この数列の要素を一つ選びを加えるという操作を回まで行うことができるとき，の全要素のgcdの最大値を求めよ．解説となるための最小操作回数が以下であるかが分かればいい(…

公式解説より効率の良いアルゴリズムの説明です．問題はこちら 問題概要 解説 関連問題 問題概要頂点辺の有向グラフが与えられる．各について，辺のみ通れないときの頂点から頂点までの最短距離を求めよ．解説頂点から頂点までの最短経路を一つ求めます．明…

問題はこちら 問題概要 解説 Pythonでの解法 感想 問題概要長さの木材がある．以下の個のクエリを処理せよ．番目のクエリはで与えられる． のとき：木材の左端からの地点で木材を切る． のとき：木材の左端からの地点を含む木材の長さを出力する． 解説現在…

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

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

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

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

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

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

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

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要頂点の完全無向グラフから辺取り除く．このグラフの頂点から本の辺を辿るパス(一つの辺を複数回辿ってもいい)のうち終点が頂点であるようなパスの数を求めよ．解説頂点から頂点への長さのパス(厳密…

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

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

計算量は良くないですがすぐ思いつくので．あと，誤差におびえずに済む．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要二次元平面上の頂点集合とが与えられる．のすべて頂点に対して同様に，原点中心の回転と平行移動を行ってと一致させられるか…

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

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

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの正整数列が与えられる．としてを求めよ．解説 できるだけ大きなを使いたい．であるから，貪欲で大丈夫．との比較はとを比較すればよい．もしくは，二分探索でも解ける．基本的には，https://a…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要整数が与えられるので，以下の条件を満たす整数組の数を求めよ． をの最大公約数とすると，以下が成立する． かつかつ 解説またはのときは条件を満たさないので，以下とする．各に対して，条件を満…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの正整数列が与えられる．以下の個のクエリに答えよ． 正整数が与えられる．のいずれとも異なる正整数のうち，小さい方から数えて番目のものを求めよ． 解説クエリを先読みすることで二分探索を…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要白いボール個と黒いボール個を一列に並べるとき，各について左から個のボールのうち白いものの個数を，黒いものの個数をとおいたとき，すべてのについてが成り立つような並べ方の数を求めよ．解説結…

Pythonを使っている人に需要がありそうなので書きます． ※この記事は解法ではなく実装の解説を行います．解法が知りたい場合は別の記事を読んでください． A問題 B問題 C問題 D問題 感想 E以降は需要ありそうだったら書きます．A問題入力を受け取って計算結…

問題はこちら 問題概要 解説 おまけ おまけ2 提出プログラム 感想 問題概要個の料理があり，それぞれ作るためにオーブンを使う時間はである．つのオーブンを用いてすべての料理を作るのにかかる時間は最短何分か．解説つのオーブンのみを用いることを考える…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要のチェス盤があり，に白のポーンがある．他にも個の黒のポーンが置かれている．白のポーンはの方向に進むとき，白のポーンがに到達できるようなの数はいくつか．解説を「に到達できるか」とするよう…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要以上以下の整数をランダムに選ぶという操作を回行うとき，選ばれた整数の種類数の期待値にをかけた値を求めよ．解説種類数をとする. 求めるものはで, は包除原理とかで求められそうだが面倒なので別…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要がいて，左から番目は人である．以下の種類の操作を繰り返し，人を昇順に並び替えるときのコストの最小値を求めよ． コストを払い，人を好きな位置に移動させる． コストを払い，人を左端に移動させ…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要頂点の根付き木について以下の個のクエリに答えよ．整数が与えられる．次の条件を満たす頂点の個数を求めよ． から根への最短パス上に頂点が存在する． から根への最短パスに含まれる辺の数がちょう…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列があり，の末尾の要素をとして，末尾の要素を以上未満の整数に変えてになった要素は消すという操作を人のプレーヤーが交互に行う．操作ができなくなる(自分の操作開始時にが空)と負けとな…

公式解説と同じになってしまいましたが，せっかく書いたので公開します．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要頂点の木の任意の頂点についての総和を求めよ．ただし，とはからへの最短パスに含まれる辺全ての重みのXORと定める．解説も…

形式的冪級数を用いた解法です．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要次元グリッド上でからまでの最短経路の個数をとする．を求めよ．解説である．これは高校数学なので，分からない場合は復習が必要．次元累積和の典型みたいに考えると…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要個の正整数からなる数列が与えられる．とを満たす異なる数列であってを満たすものが存在するか判定し，存在するならばつ出力せよ．解説の要素を「に振り分ける」，「に振り分ける」，「どちらにも振…