ツバサの備忘録

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

累積和

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の分は、問題を読み間違えてい…

ABC105

今回もunratedでした!(結局全体でunratedになったみたいです) A - AtCoder Crackers 提出コード nがkで割り切れるとき、最大と最小が1ずれるので1を出力します。割り切れないとき、n人に均等に配ることができるので0を出力します。 トランプのカードを全員…

Mujin Programming Challenge 2018

目標は200位でした。レート順400位ぐらいだったので運次第、と思ってました A - コンテスト名 提出コード 頭が真っ白になったので素直に全部書き出しました。与えられる文字の長さがそもそも5に満たない場合の条件を途中まですっかり書き忘れていたので危な…

ABC099

ABC100の一歩手前になりました。自分はABC88から参加し始めたのでまだ日は浅いですが、100回になっても今まで通り頑張っていこうと思います。 さて、前回のABCですが、久しぶりにD問題が解けてかなり嬉しかったです。ただ噂のC問題が解けず全完には至ってな…

ABC098

すごく今更ながら前回のABCの結果を。 先に言ってしまうと、前々回に続き二回連続でレートが落ちました。ただ、自分の中ではいいところまでD問題が解けていたのであと一歩かなぁ、と。Aから一応見ていきたいと思います。 A - Add Sub Mul 素直にといて問題な…