典型
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの正整数列が与えられる.としてを求めよ.解説 できるだけ大きなを使いたい.であるから,貪欲で大丈夫.との比較はとを比較すればよい.もしくは,二分探索でも解ける.基本的には,https://a…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要整数が与えられるので,以下の条件を満たす整数組の数を求めよ. をの最大公約数とすると,以下が成立する. かつかつ 解説またはのときは条件を満たさないので,以下とする.各に対して,条件を満…
問題はこちら 問題概要 解説 おまけ おまけ2 提出プログラム 感想 問題概要個の料理があり,それぞれ作るためにオーブンを使う時間はである.つのオーブンを用いてすべての料理を作るのにかかる時間は最短何分か.解説つのオーブンのみを用いることを考える…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要のチェス盤があり,に白のポーンがある.他にも個の黒のポーンが置かれている.白のポーンはの方向に進むとき,白のポーンがに到達できるようなの数はいくつか.解説を「に到達できるか」とするよう…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要以上以下の整数をランダムに選ぶという操作を回行うとき,選ばれた整数の種類数の期待値にをかけた値を求めよ.解説種類数をとする. 求めるものはで, は包除原理とかで求められそうだが面倒なので別…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要がいて,左から番目は人である.以下の種類の操作を繰り返し,人を昇順に並び替えるときのコストの最小値を求めよ. コストを払い,人を好きな位置に移動させる. コストを払い,人を左端に移動させ…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要頂点の根付き木について以下の個のクエリに答えよ.整数が与えられる.次の条件を満たす頂点の個数を求めよ. から根への最短パス上に頂点が存在する. から根への最短パスに含まれる辺の数がちょう…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列があり,の末尾の要素をとして,末尾の要素を以上未満の整数に変えてになった要素は消すという操作を人のプレーヤーが交互に行う.操作ができなくなる(自分の操作開始時にが空)と負けとな…
公式解説と同じになってしまいましたが,せっかく書いたので公開します.問題はこちら 問題概要 解説 提出プログラム 感想 問題概要頂点の木の任意の頂点についての総和を求めよ.ただし,とはからへの最短パスに含まれる辺全ての重みのXORと定める.解説も…
別解です.ほぼ一緒なので丁寧には書きません.問題はこちら 問題概要 解説 提出プログラム 感想 問題概要を並び替えてできる数列で,以下の条件を満たすものの数を求めよ. を満たす全ての数列について,の中に以下の数は個以下しか存在しない. 解説公式解…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要 を満たす整数の組全てについて の総和を求めよ.解説 形式的冪級数で解きます.とすると よってとしてが答え.を偶奇で分けると したがってBostan–Moriのアルゴリズムを用いたり,線形漸化式に直し…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要マスのマス目がある.以下の操作のうちつを選び,マスからマスまで移動するときの操作回数の最小値を求めよ. 操作:マスにいるときマスに移動する. 操作:ワープマスにいるときランダムにワープマ…
そもそも回転の列挙が難しい.以下,厳密性を欠くので注意.問題はこちら 問題概要 解説 提出プログラム 感想 問題概要正六面体のつの面に正整数を書き込んだとき,正整数の和がとなるような物の数を求めよ.ただし,正六面体を回転して一致する書き込み方は…
Mo's algorithmを用いた方法を説明します.問題はこちら 問題概要 解説 提出プログラム 感想 問題概要英小文字からなら長さの文字列について「文字目から文字目までからなる部分文字列を任意に並べ替えたものの中で辞書順最小である文字列の文字目を出力せよ…
Mo's algorithmを用いた方法を説明します.問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列に関して「番目から番目までに含まれる数の種類を求めよ」という個のクエリに答えよ.解説 Range Set Queryという名前とか数列の区間に対するク…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要頂点辺の連結無向グラフの各辺に英小文字がつ書かれている.頂点から頂点までのウォークのうち,通った辺に書かれた文字を順に並べると回文となるようなものの回文の長さの最小値を求めよ.解説 回…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要のマス目が白か黒に塗られており,塗られていないマスもある.塗られていないマスを白か黒で塗るとき,隣り合ったマスが異なる色で塗られているようなマスの組の数の最大値を求めよ.解説 隣り合っ…
問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要整数に対し,正の約数の個数をとする.を求めよ.思考の流れ 正の約数の個数は,素因数分解や約数を列挙することによってで求まる.からに対してこれを行うとかかる. 実際に約数の分布をみて…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要行列のマスのうちいくつかを選ぶ. 行列のマスを選ぶと, 円失う. また, 行目のすべてのマスを選ぶと円得ることができ, 列目のすべてのマスを選ぶと円得ることができる. このとき最大何円得ることがで…
問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要数直線上のの位置にあるゴミを2つ以下の座標に集める. 1回の操作につき, 座標にあるゴミをまとめてかに移動させることができる. 最小の操作回数を求めよ. また, ある座標へのゴミの追加や削除…
問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要座標平面上のの4点を頂点とする正方形がある. この平面上に描かれる, 座標軸に平行な線が本与えられる(軸に平行な線が本, 軸に平行な線が本). すべての線は正方形の少なくとも一辺と交差して…
問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要長さの数列とが与えられる. となるを選んでをに変更する. この操作を何回か行ってにできるとき, 最小操作回数を求めよ.思考の流れ隣り合ったものに対して操作を行う場合, 隣り合ったものの差…
問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要以上以下の要素からなる長さの数列のうち, 以下の条件を満たすものの数を求めよ. 数列の要素はすべて異なる. 思考の流れ制約がそこそこ大きいのでDPとかじゃなさそう.制約が不一致条件のみな…
問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要中心が軸上にあるような円が個与えられる. 平面上の点のある点を内部(円周は内部ではないとする)に持つ円の数の最大値を求めよ.思考の流れ円の内部とかいう条件が幾何っぽくて扱いづらい. ち…
問題はこちらあんまり見てなかったけど本当はここらしい 問題概要 思考の流れ 提出プログラム 感想 問題概要4点があり, 最初にいる. 今いる点から別の点に移動することを回繰り返す. 回の移動の後ににいる移動方法が何通りあるか求めよ.思考の流れ回の移動後…
悩まなかったけど公式解説が出てなかったので書きました.問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要パスカルの三角形で(一番上を0段目として)1段目の数を,とし, 各段の一番左の数を,一番右の数をとする. このときの段目,左から番目の数…
問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要かつとなるが存在するようなで始まりで終わるような長さの数列の数をで割った余りを求めよ.思考の流れに辺を張ったグラフの隣接行列を作る. 蟻本とかにも書いてあるように, この行列を乗した…
問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要が与えられる. 以下の連立漸化式で表される数列の第項を求めよ.思考の流れ蟻本とか見てるとわかるように線形の連立漸化式は行列累乗で高速に解くことができる. に注意 提出プログラムhttps://…
問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要 の異なる番号が書かれた個の箱に種類の色を塗る. このとき種類全ての色を使い, 各箱を何かの色で塗るとき, 塗り方の総数をで割った余りを求めよ. 思考の流れ がそこそこ大きいのでDPとかじゃ…
問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要 長さの文字列と長さの文字列が与えられる. 空文字列を用意して, の先頭か末尾にを挿入していくことを考える. の接頭辞がに等しくなるような挿入の仕方の総数を998244353で割った余りを求めよ…