ツバサの備忘録

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

累積和

AGC009 C - Division into Two

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

ABC164 D - Multiple of 2019

問題 提出コード 解法 ここでは、について下から桁目の数字をと表記します。また、の文字列の長さ、すなわちをとします。 加えて、をで割った余りをと表記します。 まず、について、桁ごとに分解して表現してみると、 となります。 は、次のように書くことも…

AOJ 1176 - 輪番停電計画

問題 提出コード 解法 はじめに、2次元累積和を用いて、ある長方形の範囲の需要の合計をで求めることができるようにしておきます。 ここから、DPを行います。 長方形の左上が,右下がとなるような範囲のグループの分け方の最適解 とします。最適解、なのでグ…

ABC127 C - Prison

問題 提出コード 解法 枚目のカードを用いて通ることができるゲートの個数 とすると、となるようなの個数が答えになります。 ということで、各ゲートについて与えられる区間について、に1を追加する、という操作をしてあげれば、枚目のカードを用いて通るこ…

CPSCO2019 Session3 E - Enumerate Xor Sum

問題 提出コード 解法 のときの答えを求めてみます。 については、の累積xorをとっておくことでで求めることができるので割愛します。 とのxorを取った値をとすると、xorの定義から、それぞれの桁について、の立ってるビットの個数が1ならばのその桁は1、そ…

ABC102 D - Equal Cut

問題 提出コード 解法 パッと見とっつきにくい問題。 まずは、3つのうち、どこか1つの仕切りを固定して考えるとして、どの仕切りを固定すると見通しがよくなるかを調べます。 まず、右端の仕切りを固定することと、左端の仕切りを固定することによる見通しの…

九州大学プログラミングコンテスト2018 E - Treeone

問題 提出コード 解法 まず、を変える、としたとき、どんな数字に変えればよいか、ということを考えてみます。 このとき、部分列の総和に影響がでるのは、もちろんを部分列に含むものについてのみで、含まないものは総和が変化することはありません。 さて、…

ABC092 C - Traveling Plan

問題 提出コード 解法 毎回愚直に計算するともちろん間に合わないので何か工夫をする必要があります。そこで登場するのが累積和です。 まず、始点と終点も観光スポットとみなし、としておきます。 観光スポットからまで順番に行ったときにかかる金額の総和 …

WUPC2019のお話(解法編)

ということで、今回は各問題についての簡単な解法と、その感想です。 まだ解けていない問題もいくつかあるので、ご容赦ください… 運営側としてどんなことをしたか、についてはこちらの記事をご覧ください。 emtubasa.hateblo.jp 各問題の方針と感想 A - WAse…

ABC080 D - Recording

問題 提出コード 解法 まずは、同一チャンネル内で区間が連続するもの、つまりとをまとめてのようにしてしまいます。これは、それぞれのチャンネルについて区間をわけ、そして開始時間の昇順でソートをして前から見ていき、今見ている区間の終わりの時間と次…

ABC072 C - Together

問題 提出コード 解法 それぞれの数字の出現回数を配列上でメモします。そして、長さが3の区間の和を順番に見ていき、その和の最大値が答えになります。 長さが3しかないので、3つの数字の和を愚直に足していってもいいのですが、 memo[i] = i-1,i,i+1の個数…

ABC017 D - サプリメント

問題 提出コード 解法 番目までのサプリメントを飲む方法数 とします。 番目のサプリメントを飲むときは、 番目のみを1日で飲む 番目と番目の2つを1日で飲む 番目から番目の3つを1日で飲む というように、同時に飲むこともできます。 しかし、番目から番目の…

第5回 ドワンゴからの挑戦状 予選 C - k-DMC

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

ABC077 C - Snuke Festival

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

codeFlyer (bitFlyer Programming Contest)予選 D - ハンコ

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

ABC018 C - 菱型カウント

問題 提出コード 解法 ある地点で×な部分があると、その×を中心として作成したひし形の範囲内の任意のマス(x,y)について、(x,y)を中心とするひし形は作成できません。 ということで、 memo[i][j] = (i,j)を中心としてひし形を作成したとき、その範囲内に存在…

ABC017 C - ハイスコア

問題 提出コード すんなり考察&実装がいったので結構好きです。 解法 1つも入手しない宝石の種類を1つ決めると、それ以外の全ての宝石は獲得しても問題ありません。これについて考えるとき、2種類目以降の獲得しない宝石が存在しようがしまいが関係ありませ…

AOJ 2600 - Koto Distance

問題 提出コード 解法 サンプルの図がわかりやすいのですが、ある座標(x,y)から距離w以内に効果がある場合、 (x-w,p)~(x+w,p)および(p,y-w)~(p,y+w)の範囲に効果があることになります。ここで、pは任意の数字になります。これは、横についてx-w~x+wの範囲を…

AGC027 B - Garbage Collector

問題 提出コード 解法 ゴミを回収しに行く回数(=ゴミを捨てる回数)を回と決め打ちし、そのときの最小値を求めます。 そして、最後にについて全探索して答えを求めることを考えます。 回ゴミを回収しに行くとき、ゴミを拾う回数は回、捨てる回数は回なので、…

CODE FESTIVAL 2018 qual A D - 通勤

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

AOJ 1148 - ログイン/ログアウト記録の解析

問題 提出コード 解法 時刻tに学生mがログインしているかどうかだけが知りたいため、実はPCの何番目がログインされているかどうか、という情報は特に必要ありません。 まずはいもす法を用いて下準備をします。 memo[i][j] = 学生iが時刻jに何台のPCでログイ…

ABC087 C - Candies

問題 提出コード 問題の制限をきちんと見れば、全探索で間に合うということがわかります。 が、特に何も考えていなかったので累積和をとりました。 この問題では、下に1回、右に回移動する操作を行うだけなので、回右に移動して下に移動、そして最後に残りの…

ABC086 D - Checker

問題 提出コード 解法 散らばっている情報を、まずはK×Kマスの中に押し込みます。 例えば、(x,y)がWという希望は、(x+K,y)、もしくは(x,y+K)がBという希望と同じであり、また(x+K,y+K)がWであるという希望とも同じです。 これを利用すると、白を0、黒を1と表…

ABC014 C - AtColor

C - AtColor 提出コード 知ってはいたものの使ったことがなかったいもす法を初めて使用しました。 i番の絵の具を必要している人の人数をmemo[i]とします。そのときに、 memo[a]に+1、memo[b+1]に-1を加えて、memo[0]から累積和をとっていきます。 これで、そ…

AOJ 2331 - 友だちの誘い方

友だちの誘い方 提出コード まずは脳死でいもす法を書いてみます。それぞれの入力に対し、 memo[a]に1を、memo[b+1]に-1を足して、memo[0]から累積和をとっていきます。 すると、i<=memo[i]+1のとき、i-1人を誘うことができるようになっていますので、この条…

AOJ 2015 - Square Route

Square Route 提出コード まずは累積和で、上端から、および左端からi番目の道路までの距離を求めておきます(s[i]とします)。 すると、ある道路からある道路までの幅が、累積和の引き算s[i]-s[j]等で求められるので、ありうるすべての取り方を記録します。 …

ABC005 D - おいしいたこ焼きの焼き方

D - おいしいたこ焼きの焼き方 提出コード mp[i][j] = からまでの、長方形の部分の美味しさの総和 (ただし、添え字が0以下のときは0) として、入力と同時に累積和をとっていきます。 すると、ある長方形をl,r,u,d(それぞれ長方形の左、右、上、下の辺の番号)…

ABC004 C - 入れ替え,D - マーブル

C - 入れ替え 提出コード これは実験をある程度すると法則性が見えてきます。 重要なのはNを5で割った数と、そのあまりです。 この操作は5回で1セットになっていて、1セット完全に行うことで、当時先頭にいた数字が一番後ろまで移動します。 このセットが完…

ABC106

なんだかんだまだARC出たことないので出てみたいですね A - Garden 提出コード (a-1)*(b-1)をすればよいです。 道の部分を無視して畑をくっつけると、実際に上の式のように、a-1とb-1の辺の長方形になります。 B - 105 提出コード 1からnまでの数字について…

ABC084

バチャコン5回目です(4回目は復習回でした)。 A - New Year 提出コード 12月30日のn時から年が明けるまでにどれくらい時間がかかるか、という問題です。 12/31の一日分まるまる24時間+今日の残り時間(24-n)を出力します。 12/31の分は、問題を読み間違えてい…