問題 提出コード 解法 の総和を求めて、最後に全パターン数で割れば答えです。総和の求め方について考えていきます。 は、個の箱にあるボール個からそれぞれ1個ずつ選ぶパターン数と一致します。 ということです。 個目の箱にあるボールからボールを選ぶパタ…

問題 提出コード 解法 いろいろな数列を試していると、4つ以上の連続する区間が単調減少することはありません。 この原因を考えてみると、長さ3の数列を作成しているため、4つ単調減少させようとすると、1つの長さ3の数列 + どこか1か所別の値が選ばれる必要…

問題 提出コード 解法 集合を、集合0、集合1とし、をとします。 番目の要素まで見て、番目の要素を集合に入れるような振り分け方のパターン数 を数えます。 という区間が集合に入り、その前後はもう片方の集合に振り分けられるパターンを考えます。このよう…

問題 提出コード 解法 縦方向が、横方向がとします(多分問題と逆…？) 移動は必ず全体で回になります。 縦に回、横に回寄り道すると決めた時、上記の移動のうち、縦方向に移動するのが回、横方向が回になるので、先にその方向を決め打つと、 通りになります。…

自分の大学にあるサークルが主催するコンテストに参加しました。 自分のコードはまとめてここに上げてあります。問題の前から順番にa,b,...と振ってあります。自分のコードを動かすことができるeの入力データも添えました。 長いのでかなり端折る部分があり…

ここであまり得意でないパターンの問題が出てきたのでメモです。DEGwerさんの数え上げPDFなんかにはいろんな種類が載っているので、また出てきたら追加します。数式をごちゃごちゃいじるとできるパターンもそのうち載せたいです。 について計算をしたい、と…

問題 提出コード 解法 のうち、をある値に決めた際にペアの相手となりうるの個数がいくらか、を高速で求めることができれば、について全探索をして数え上げれば良いです。 の値を決め打ったときに、の末尾の値と先頭の値は固定されてしまいます。 前者はの先…

問題 提出コード 解法 頂点1が距離0でない場合や、頂点1以外が距離0である場合は、明らかに答えが0になるので処理しておきます。 それ以外のグラフについて考えます。 あらかじめ、距離がの頂点の個数をそれぞれカウントしておきます。 距離がである頂点は、…

問題 提出コード 解法 まず、最終的な数列の中に奇数が個存在するときについて考えます。は最大でとなります。 すると、残ったに1加算する操作を2つまとめて、に2加算する操作回分に置き換えることができます(もちろん、残った回数が奇数の際は端数が発生す…

問題 提出コード 解法 探索か何かをしつつ、今いる頂点について色を決ようとすると、その頂点から距離2以内で、すでに色が決まっている頂点がいくつあるかを調べる必要があり、とても大変です。 そこで、今いる頂点から行くことができる頂点について、色を決…

問題 提出コード 解法 ABCがBCAになるので、これが連鎖的に続くことを考えると、 AAA...BCがBC...AAAになる、もしくはA...BCBCがBCBC...Aになる、の2通りです。 後者のパターンは、前者のパターンをBCが連続している個数だけ繰り返す、とみなすことができる…

問題 提出コード 解法 ある位置に置かれた2つの駒のマンハッタン距離が何回加算されるかを考えると、個の残りの駒を配置する種類数そのものになります。ということで、これは回です。任意の位置にある2つの駒について、同じ回数だけ加算されるので、あとは任…

問題 提出コード 問題 個の数字が与えられるので、その数字を使って作れる数列のうち、以下のような条件を満たす数列の個数をで割った値を求めてください。 全ての数字について、その数字より左側に自分より大きいものが存在する、もしくは右側に小さいもの…

問題 提出コード 解法 答えの本質となる部分は問題文にすでに書いてあります。 求める数は、となるようなの組み合わせの個数です。 さて、以上以下の数字を個重複を許しつつ抽出すると、それらの数字を利用して作成したの組み合わせは一意に決まります。なぜ…

問題 提出コード バグを生やしやすい問題です。相変わらずこういう問題でバグを生やしてしまいます。 解法 をまずは素因数分解し、それぞれの素因数が何回登場しているかを調べます。 これは、それぞれについてで調べることができるので、全体でになります。…

問題 提出コード 解法 縦になっているドミノ1本と、横になっているドミノ2本をそれぞれ1セットとして考えていきます。これは、文字目の上下が一致しているかどうかを調べるだけで簡単に判断できます。横になっているセットについては、次のセットに行くとき…

問題 提出コード WAしていたコードの冗長な部分をコンパクトに書き直していたら、バグが消えていたのに提出しなかったので、結局時間内にACすることができませんでした…パフォが400ほど変わるのでめちゃくちゃ悔しいです。知らぬ間にバグが消えていたパター…

問題 提出コード 中段について、番目のパーツを使うとしたときに、使うことができる下段のパーツはとなるパーツ番号の場合です。このようなのうち最小のものをもとめれば、それより大きい個のパーツはすべて使用できます。 ということで、まずはそれぞれのパ…

問題 提出コード これを自力で解けなかったのは結構悔しいです…最近思い通りになかなか解けないですね 解法 ,,となるようなの組を探します。 要素が3つ存在するので、まずは真ん中を決め打ちしたときののペアの個数を求めることを考えます。 あるについて、…

問題 提出コード 解法 基本方針は、いもす法を利用して移動したときに黒くなる部分を求めていくことです。 紙の左上にまずはハンコを合わせます。すると、 マスが黒かったとき、右にマス、下にマスの範囲内がすべて黒く塗られることになります。 ということ…

問題 提出コード 解法 ダブっている数字は数列に1つ必ず存在します。 ダブってる数字のうち左側にあるものを,右側にあるものをとしたとき、数列は次のようになっています。 ここで、はそれぞれ0個以上の要素を持っている数列です。 長さの部分列を数え上げる…

問題 提出コード 解法 UnionFind木を貼ると解ける問題です。 鉄道について、辺をそのままUnionFind木に反映させると、根が同じ都市については、連結であることになります。 道路についても同様です。ということで、まずはUnionFind木を2つ用意し、鉄道と道路…

問題 提出コード DPをします。 まずは、下準備をします。 ある高さについて、幅がのとき(つまり、本の棒があるとき)に、横線の置き方がいくつあるかを計算します。 これをとします。 のとき、横線はおけないのでです。 のとき、横線を置くか置かないかの2通…

問題 提出コード 想定解の方がスマートでした。 自分は、mapを使ってごり押しをしました。 解法 素直に全探索することをまず考えてみると、 9マスのうち、左上のマスを決め打ってから9個のマスを確認する、という動作は、左上のマスの候補が となるので、も…

問題 提出コード 解法 modとコンビネーションが出てくるので、例によって逆元の知識を使用します。 例によってけんちょんさんの記事を載せておきます。 qiita.com 問題の条件を図で表すと次のようになります。 Sがスタートの位置、Gがゴールの位置で、黒く塗…

問題 提出コード 解法 サンプル2がすごい実験に使いやすいのでこれを利用していくことで解けました。 まず、は、番目が足される回数に最後に掛け合わせるだけでいいので、これ以降は無視をします。 ということで、番目の数字が何回足されるか、を調べます。 …

問題 提出コード 解法 動的計画法で答えを求めていくことを考えていきます。 まずは特徴についてです。 この問題では、0がとても重要なものになっています。 数列に0が存在していた場合、0は何回2で割っても0になるので、この部分を利用して与えられたの調整…

問題 提出コード 解法 まずは素因数分解をし、それぞれの素因数についていくつ使われているかをカウントします。 こちらの記事と似たようなことをします。 ~までを全探索し、がの約数である限りをで割り続け、その数をカウントしていきます。 探索後に、がま…

問題 解法 縦と横に分けて考えます。 座標aからbに移動するとき、考えられるパターンは3つあり、 そのままaからbに直接いくパターン 座標0に移動してからbにいくパターン 座標r-1(およびc-1)に移動してからbにいくパターン になります。 また、座標をワープ…

問題 N-1本の辺とN個の頂点からなる連結無向グラフが与えられます。それを、ある条件を満たすようにK色以下で塗り分ける場合の数を、の余りで出力しなさい、というものです。 条件が、任意の頂点と同じ色の別の頂点は、ほかの同じ色の頂点のみをたどってそこ…