ツバサの備忘録

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

いもす法

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の範囲を…

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

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

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人を誘うことができるようになっていますので、この条…