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

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

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

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

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

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

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

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

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

問題はこちら 問題概要 解説 形式的冪級数 提出プログラム 感想 問題概要全てのの組を以下のルールでソートしたときの番目の値を求めよ．上の方が優先度が高い． の昇順． の昇順． の昇順． 解説さすがに全部列挙するのは無理．の昇順に並んでいるので，全…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要爆弾が個あり，番目の爆弾は座標にあってのときオフ，のときオンになっている．本のコードがあり，番目のコードを切ると，座標が以上以下のすべての爆弾の電源のオン・オフが切り替わる．切るコード…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要人にのつの能力値がある．この中から3人選んだときのの最大値を求めよ．解説最初に思いつくのは人の選び方の全探索．これはなので間に合わない．人決めたときにもう人を高速に決められたら解けそう…

別解です．ほぼ一緒なので丁寧には書きません．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要を並び替えてできる数列で，以下の条件を満たすものの数を求めよ． を満たす全ての数列について，の中に以下の数は個以下しか存在しない． 解説公式解…

問題はこちら 問題概要 問題概要2 解説 別解 提出プログラム 感想 問題概要頂点辺の単純無向グラフの各頂点を赤，緑，青で塗り分ける方法で隣接する頂点が異なる色で塗られているようなものは何通りあるか．問題概要2グラフ理論っぽく書かれていますが，同じ…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要 を満たす整数の組全てについて の総和を求めよ．解説 形式的冪級数で解きます．とすると よってとしてが答え．を偶奇で分けると したがってBostan–Moriのアルゴリズムを用いたり，線形漸化式に直し…

そもそも回転の列挙が難しい．以下，厳密性を欠くので注意．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要正六面体のつの面に正整数を書き込んだとき，正整数の和がとなるような物の数を求めよ．ただし，正六面体を回転して一致する書き込み方は…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要歩でちょうど距離歩けるとき，原点からまで最短何歩で行けるか．解説 とします．歩歩くとするとなら到達できないことがわかりますが，なら到達できるでしょうか？到達できそうですがのときには注意…

Mo's algorithmを用いた方法を説明します．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列に関して「番目から番目までに含まれる数の種類を求めよ」という個のクエリに答えよ．解説 Range Set Queryという名前とか数列の区間に対するク…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要頂点辺の連結無向グラフの各辺に英小文字がつ書かれている．頂点から頂点までのウォークのうち，通った辺に書かれた文字を順に並べると回文となるようなものの回文の長さの最小値を求めよ．解説 回…

解法，解法，？解法について解説します．問題はこちら 問題概要 解説 O(√N)解法 O(logN)解法 O(1)？解法 提出プログラム 感想 問題概要以上以下の整数のうち，先頭に余分な0をつけない十進表記で偶数桁であり，前半と後半が文字列として一致するようなものは…

問題はこちら 問題概要 解説 に整数を追加する場合 から整数を削除する場合 のmexを求める ほかにも 提出プログラム 感想 問題概要長さの整数列が与えられる．の連続する長さの区間すべてについてのmexのうち最小値を求めよ．解説 最初の区間についてmexを求…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要のマス目が白か黒に塗られており，塗られていないマスもある．塗られていないマスを白か黒で塗るとき，隣り合ったマスが異なる色で塗られているようなマスの組の数の最大値を求めよ．解説 隣り合っ…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要整数に対し，正の約数の個数をとする．を求めよ．思考の流れ 正の約数の個数は，素因数分解や約数を列挙することによってで求まる．からに対してこれを行うとかかる． 実際に約数の分布をみて…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要縦横マスのマス目の一番上のマスから1つを選んで右か下に1マスずつ移動する. ただし, 行目のマスから下に移動することはできない. のについて, 行目のいずれかのマスに移動するための最小移動…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要以上以下の要素からなる長さの数列のうち, 以下の条件を満たすものの数を求めよ. 数列の要素はすべて異なる. 思考の流れ制約がそこそこ大きいのでDPとかじゃなさそう.制約が不一致条件のみな…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要 頂点の木が与えられる. に対してが以下のように定義される時, を求めよ. 以上以下の頂点からなる誘導部分グラフの連結成分数 思考の流れ 式通り素直にしようとしても間に合わない. となるの…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要 頂点の木と, 各頂点にの値が与えられる. 全ての頂点に対して, 頂点1から頂点までのパスを頂点1から見た数列ととらえて狭義最長増加部分列の長さを求めよ. 思考の流れ ある数列Sが与えられた…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要 0,1からなる長さの2つの数列に対し, 関数を以下のように定める. に対し以下の操作を繰り返してと等しくすることを考える. このとき行う操作のコストの和として考えられる最小の値がである. …

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要 頂点辺の閉路のない有向グラフ(=DAG)が与えられる. 頂点から辺をたどって頂点Nに行くことを考える. 各頂点から出ている辺から等確率でランダムに選び進む. このグラフから一つだけ辺を取り除…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要 個の都市からなる辺の連結グラフが与えられる. また, 各頂点について枚の銀貨を得るために必要な時間, 各辺について移動にかかる銀貨枚と時間が与えられる. 都市1から各都市に行くために必要…