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

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

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

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

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

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

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

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

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

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

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

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

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

問題はこちら 問題概要 解説 アルゴリズム 提出プログラム 感想 問題概要を並び替えて得られる数列であって以下の条件を満たすもののうち，辞書順最初のものを求めよ． に対し，においてはよりも先に現れる． 解説ポイント 辞書順最小は前から貪欲 要素の追…

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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