ツバサの備忘録

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

mod N

ABC133 C - Remainder Minimization 2019

問題 提出コード 解法 基本的には、区間から2つ数字を選び、の最小値を求めていけばよいです。 が、このままだと 回の計算が必要になってしまうので、この制約では間に合いません。 ここで、の長さに注目すると、この長さが以上の際は、確実にがとなるような…

M-SOLUTIONS プロコンオープン C - Best-of-(2n-1)

問題 提出コード 解法 引きわけがネックなので、どうにか別処理できないか、を考えてみます。すると、 回勝負がつくまでにかかるゲームの回数の期待値 とすると、 から、 と計算することができます。 この計算により、回でゲーム全体が終了する場合について…

ABC127 E - Cell Distance

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

エクサウィザーズ 2019 D - Modulo Operations

問題 提出コード 解法 (現在黒板に書かれている数字に影響があるような数字を取り除くことをここでは”使う”、ないような数字を取り除くことを”使わない”と表現します) まず、回目に取り除いた数字よりも大きい数字を、回目以降で取り除いても、黒板に書かれ…

AOJ 3052 - Milk (RUPC2019 Day2 B)

問題 提出コード 解法 まず、の際は答えがになるのは自明なので、それ以外の場合について考えます。 個の空き瓶を個の新品と交換したとき、手元にある瓶の個数は個減ります。この減る個数は一定です。 よって、個の瓶が個未満になるまで交換することができる…

ABC071 D - Coloring Dominoes

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

ABC050 D - Xor Sum

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

ARC077 D - 11

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

ABC113 D - Number of Amidakuji

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

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

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

AGC028 B - Removing Blocks

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

CODE FESTIVAL 2018 qual A D - 通勤

問題 提出コード 解法 後ろの方から見ていくと見通しが良くなるのかな、と思いきやそうでもありませんでした。 番目のガソリンスタンドで燃料を補給する場合の、~番目のガソリンスタンドの建て替え方 とします。 仮に今燃料が満タンの状態で番目のガソリンス…

CODE FESTIVAL 2018 qual A C - 半分

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

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色以下で塗り分ける場合の数を、の余りで出力しなさい、というものです。 条件が、任意の頂点と同じ色の別の頂点は、ほかの同じ色の頂点のみをたどってそこ…

AOJ 2372 - IkaNumber

問題 提出コード 自力でなんとか解けました!時間は4時間くらいかかりました… くコ:彡 くコ:彡 くコ:彡 くコ:彡 解法 問題を読んだだけではかなり自由度が高いので、一つ一つ見ていくことにします。 まず、Taroの家の位置を固定します。 Taroの家、にんじん…

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

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

ABC041

バチャコン3回目です。初めてbitDPの問題に触れました。 A - 添字 提出コード 今回のA~Cはかなりシンプルでした。 A問題は、素直に文字列sのi番目の文字を出力すれば良いです。配列の最初が0になっていることだけ気を付ければ大丈夫です。 B - 直方体 提出コ…

ABC104

unratedでよかった… 人生初のABCunratedでした。爆死しました A - Rated for Me 提出コード 最初の問題からなんかとっつきにくいなぁって思いました。 少し思考が停止しましたがきちんと3つの場合分けをしてなんとかACでした。 以下と未満に惑わされないよう…

AGC26

二回目のAGCでした。 A - Colorful Slimes 2 提出コード まず入力時に、どの色のスライムがいるかを調べます。前から順番にスライムをチェックしていって、一個前のスライムと色が同じだったらその都度色を現時点で使ってない色に変えていけば、最短手数で合…