解説
グリッドの最短経路(North-East lattice path)の数え上げの例を解説していきます.よくある書き込み(動的計画法)による解法は扱いません.目次 最短経路の数え上げとは 一般的な最短経路 ある点を通る最短経路 ある点を通らない最短経路 ある長方形領域を通…
公式解説より効率の良いアルゴリズムの説明です.問題はこちら 問題概要 解説 関連問題 問題概要頂点辺の有向グラフが与えられる.各について,辺のみ通れないときの頂点から頂点までの最短距離を求めよ.解説頂点から頂点までの最短経路を一つ求めます.明…
問題はこちら 問題概要 解説 Pythonでの解法 感想 問題概要長さの木材がある.以下の個のクエリを処理せよ.番目のクエリはで与えられる. のとき:木材の左端からの地点で木材を切る. のとき:木材の左端からの地点を含む木材の長さを出力する. 解説現在…
問題はこちら 問題概要 解説 包除原理 さらなる高速化 提出プログラム 感想 問題概要以上以下のについて以下の問題を解け. からまで番号が付いた人を空でない個の集合に分ける.で割った余りが等しい人は同じ集合に含まれないような分け方の総数を求めよ. …
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要個のボールがあり,各ボールにはから以下の整数が書かれたボールはちょうど2個ずつ存在する.本の筒があり,各筒にはボールが個入っている.異なる本の筒の一番上にあるボールの色が同じ場合それら…
問題はこちら 問題概要 解説1 解説2 提出プログラム 感想 問題概要長さの正整数列が与えられる.以下の条件を満たすをすべて求めよ. すべてのを満たす整数について,である. 解説1となるのは,がの任意の素因数を持たないことと同じです.のすべての素因数…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要頂点辺の有向グラフがあり,人が人ずつ頂点から辺を辿って任意の回数繰り返す.人が人以上通った頂点のの値の総和の最大値を求めよ.解説ある強連結成分を通るときはその強連結成分の全頂点を通るべ…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要人が円周上に並んでいる.番目の人は時刻に宝石をもらうと時間後にその宝石を番目の人に渡す.ただし,とする.また,高橋君は時刻に番目の人に宝石を渡す.すべてのについて,番目の人が初めて宝石…
公式解説とは別の解法です. 問題はこちら 問題概要 解説1:最大二部マッチング 解説2:2-SAT 提出プログラム 感想 問題概要と番号付けされた個の白い球がある.球または球を選んで黒く塗ることができるという操作を回行う.すべての球を黒で塗ることが可能…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要頂点の完全無向グラフから辺取り除く.このグラフの頂点から本の辺を辿るパス(一つの辺を複数回辿ってもいい)のうち終点が頂点であるようなパスの数を求めよ.解説頂点から頂点への長さのパス(厳密…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要行列のグリッド上の異なるマスを選ぶ,の最小値を求めよ.解説式の中に絶対値があって面倒なのでと決めることで絶対値を外す.グリッド全体を反転させれば他の場合も表せるので,の場合で求められれ…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列に対して以下の操作を行うことでの任意の要素をにするときのコストが最小となるような操作列の数を求めよ. を選びをにする.このとき,この操作を行う前の分だけコストがかかる. また,…
計算量は良くないですがすぐ思いつくので.あと,誤差におびえずに済む.問題はこちら 問題概要 解説 提出プログラム 感想 問題概要二次元平面上の頂点集合とが与えられる.のすべて頂点に対して同様に,原点中心の回転と平行移動を行ってと一致させられるか…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要最初紙に文字書いてある.コピーとペーストを行うことにより,紙に文字以上書いてあるようにしたい.コピーには,ペーストにはのコストがかかる.最小でいくらのコストがかかるか.解説連続でコピー…
形式的冪級数を用いた解法です.問題はこちら 問題概要 解説 提出プログラム 感想 問題概要次元グリッド上のからマンハッタン距離がの格子点に移動することを回繰り返すしたあとにいるとして,となる確率にをかけた値を求めよ.各格子点への移動確率はである…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの正整数列が与えられる.としてを求めよ.解説 できるだけ大きなを使いたい.であるから,貪欲で大丈夫.との比較はとを比較すればよい.もしくは,二分探索でも解ける.基本的には,https://a…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要整数が与えられるので,以下の条件を満たす整数組の数を求めよ. をの最大公約数とすると,以下が成立する. かつかつ 解説またはのときは条件を満たさないので,以下とする.各に対して,条件を満…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの正整数列が与えられる.以下の個のクエリに答えよ. 正整数が与えられる.のいずれとも異なる正整数のうち,小さい方から数えて番目のものを求めよ. 解説クエリを先読みすることで二分探索を…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要白いボール個と黒いボール個を一列に並べるとき,各について左から個のボールのうち白いものの個数を,黒いものの個数をとおいたとき,すべてのについてが成り立つような並べ方の数を求めよ.解説結…
問題はこちら 問題概要 解説 おまけ おまけ2 提出プログラム 感想 問題概要個の料理があり,それぞれ作るためにオーブンを使う時間はである.つのオーブンを用いてすべての料理を作るのにかかる時間は最短何分か.解説つのオーブンのみを用いることを考える…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要のチェス盤があり,に白のポーンがある.他にも個の黒のポーンが置かれている.白のポーンはの方向に進むとき,白のポーンがに到達できるようなの数はいくつか.解説を「に到達できるか」とするよう…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要以上以下の整数をランダムに選ぶという操作を回行うとき,選ばれた整数の種類数の期待値にをかけた値を求めよ.解説種類数をとする. 求めるものはで, は包除原理とかで求められそうだが面倒なので別…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要がいて,左から番目は人である.以下の種類の操作を繰り返し,人を昇順に並び替えるときのコストの最小値を求めよ. コストを払い,人を好きな位置に移動させる. コストを払い,人を左端に移動させ…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要頂点の根付き木について以下の個のクエリに答えよ.整数が与えられる.次の条件を満たす頂点の個数を求めよ. から根への最短パス上に頂点が存在する. から根への最短パスに含まれる辺の数がちょう…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列があり,の末尾の要素をとして,末尾の要素を以上未満の整数に変えてになった要素は消すという操作を人のプレーヤーが交互に行う.操作ができなくなる(自分の操作開始時にが空)と負けとな…
公式解説と同じになってしまいましたが,せっかく書いたので公開します.問題はこちら 問題概要 解説 提出プログラム 感想 問題概要頂点の木の任意の頂点についての総和を求めよ.ただし,とはからへの最短パスに含まれる辺全ての重みのXORと定める.解説も…
形式的冪級数を用いた解法です.問題はこちら 問題概要 解説 提出プログラム 感想 問題概要次元グリッド上でからまでの最短経路の個数をとする.を求めよ.解説である.これは高校数学なので,分からない場合は復習が必要.次元累積和の典型みたいに考えると…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要個の正整数からなる数列が与えられる.とを満たす異なる数列であってを満たすものが存在するか判定し,存在するならばつ出力せよ.解説の要素を「に振り分ける」,「に振り分ける」,「どちらにも振…
問題はこちら 問題概要 解説 形式的冪級数 提出プログラム 感想 問題概要全てのの組を以下のルールでソートしたときの番目の値を求めよ.上の方が優先度が高い. の昇順. の昇順. の昇順. 解説さすがに全部列挙するのは無理.の昇順に並んでいるので,全…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要爆弾が個あり,番目の爆弾は座標にあってのときオフ,のときオンになっている.本のコードがあり,番目のコードを切ると,座標が以上以下のすべての爆弾の電源のオン・オフが切り替わる.切るコード…