ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

逆元

ABC050 D - Xor Sum

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

ARC077 D - 11

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

ABC042 D - いろはちゃんとマス目 / Iroha and a Grid

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

AGC028 B - Removing Blocks

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

ABC110 D - Factorization

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

AOJ 3042 - Aizu Competitive Programming Camp 2018 Day 2 D Gridgedge

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

SnackDown 2016 - Coloring A Tree

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

ABC003 C - AtCoderプログラミング講座,D - AtCoder社の冬

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