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

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

問題 提出コード 方針がたってから遷移をバグなく求めるまでになんと半日かかりました！ 解法 桁DPです。 というのも、2進数になおした2つの数字のペアについて、それぞれの桁についてありうる桁の組み合わせは、 の3種類のみです。 そして、これらの組み合…

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

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

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

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

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

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

今回もバチャコンで解いたC問題とD問題のメモです。 C - AtCoderプログラミング講座 提出コード まずは動画のレートを降順でソートします。 そうしたら、大きい方から動画を見る個数だけ持ってきて、それを小さい順に見ます。 動画を見るたびに現在のレート…