mod N
問題 提出コード 解法 基本的には、区間から2つ数字を選び、の最小値を求めていけばよいです。 が、このままだと 回の計算が必要になってしまうので、この制約では間に合いません。 ここで、の長さに注目すると、この長さが以上の際は、確実にがとなるような…
問題 提出コード 解法 引きわけがネックなので、どうにか別処理できないか、を考えてみます。すると、 回勝負がつくまでにかかるゲームの回数の期待値 とすると、 から、 と計算することができます。 この計算により、回でゲーム全体が終了する場合について…
問題 提出コード 解法 ある位置に置かれた2つの駒のマンハッタン距離が何回加算されるかを考えると、個の残りの駒を配置する種類数そのものになります。ということで、これは回です。任意の位置にある2つの駒について、同じ回数だけ加算されるので、あとは任…
問題 提出コード 解法 (現在黒板に書かれている数字に影響があるような数字を取り除くことをここでは”使う”、ないような数字を取り除くことを”使わない”と表現します) まず、回目に取り除いた数字よりも大きい数字を、回目以降で取り除いても、黒板に書かれ…
問題 提出コード 解法 まず、の際は答えがになるのは自明なので、それ以外の場合について考えます。 個の空き瓶を個の新品と交換したとき、手元にある瓶の個数は個減ります。この減る個数は一定です。 よって、個の瓶が個未満になるまで交換することができる…
問題 提出コード 解法 縦になっているドミノ1本と、横になっているドミノ2本をそれぞれ1セットとして考えていきます。これは、文字目の上下が一致しているかどうかを調べるだけで簡単に判断できます。横になっているセットについては、次のセットに行くとき…
問題 提出コード 方針がたってから遷移をバグなく求めるまでになんと半日かかりました！ 解法 桁DPです。 というのも、2進数になおした2つの数字のペアについて、それぞれの桁についてありうる桁の組み合わせは、 の3種類のみです。 そして、これらの組み合…
問題 提出コード 解法 ダブっている数字は数列に1つ必ず存在します。 ダブってる数字のうち左側にあるものを,右側にあるものをとしたとき、数列は次のようになっています。 ここで、はそれぞれ0個以上の要素を持っている数列です。 長さの部分列を数え上げる…
問題 提出コード DPをします。 まずは、下準備をします。 ある高さについて、幅がのとき(つまり、本の棒があるとき)に、横線の置き方がいくつあるかを計算します。 これをとします。 のとき、横線はおけないのでです。 のとき、横線を置くか置かないかの2通…
問題 提出コード 解法 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色以下で塗り分ける場合の数を、の余りで出力しなさい、というものです。 条件が、任意の頂点と同じ色の別の頂点は、ほかの同じ色の頂点のみをたどってそこ…
問題 提出コード 自力でなんとか解けました！時間は4時間くらいかかりました… くコ:彡 くコ:彡 くコ:彡 くコ:彡 解法 問題を読んだだけではかなり自由度が高いので、一つ一つ見ていくことにします。 まず、Taroの家の位置を固定します。 Taroの家、にんじん…
今回もバチャコンで解いたC問題とD問題のメモです。 C - AtCoderプログラミング講座 提出コード まずは動画のレートを降順でソートします。 そうしたら、大きい方から動画を見る個数だけ持ってきて、それを小さい順に見ます。 動画を見るたびに現在のレート…
バチャコン3回目です。初めてbitDPの問題に触れました。 A - 添字 提出コード 今回のA~Cはかなりシンプルでした。 A問題は、素直に文字列sのi番目の文字を出力すれば良いです。配列の最初が0になっていることだけ気を付ければ大丈夫です。 B - 直方体 提出コ…
unratedでよかった… 人生初のABCunratedでした。爆死しました A - Rated for Me 提出コード 最初の問題からなんかとっつきにくいなぁって思いました。 少し思考が停止しましたがきちんと3つの場合分けをしてなんとかACでした。 以下と未満に惑わされないよう…
二回目のAGCでした。 A - Colorful Slimes 2 提出コード まず入力時に、どの色のスライムがいるかを調べます。前から順番にスライムをチェックしていって、一個前のスライムと色が同じだったらその都度色を現時点で使ってない色に変えていけば、最短手数で合…
