2018-11-10

ABC050 D - Xor Sum

問題
 提出コード
方針がたってから遷移をバグなく求めるまでになんと半日かかりました！

解法

桁DPです。
というのも、2進数になおした2つの数字のペア $(a,b)$ について、それぞれの桁についてありうる桁の組み合わせは、
$(0,0), (0,1), (1,1)$
の3種類のみです。
そして、これらの組み合わせが、そのまま $(v,u)$ の組み合わせになります。
$xor$ については、 $(0,0)$ と $(1,1)$ ではどちらも0になりますが、 $(1,1)$ のパターンは、 $+$ をしたときにくりあがりをするため、 $(0,0)$ とは値が必ず異なります。
ということで、 $(0,0),(0,1),(1,1)$ の3種類の組み合わせを $(a,b)$ のそれぞれの桁に当てはめていったときに、 $a+b$ が $N$ を下回るものの個数を求めれば、答えになります( $a xor b$ はかならず $a + b$ 以下になるので、これ以降は $xor$ について考察をする必要はなくなります)。
ということで、 $(a,b)$ の組み合わせの中で、 $max(a,b)$ が最大となるのは、 $(a,b)=(N,0)$ のときになるので、 $N$ を2進数に直した場合の桁数だけ、3種類のビットの組み合わせを当てはめていきます。
$dp[i][j][k]$ とします。

$i$ :左から今 $i$ 桁目を見ている、という情報です。
$j$ : $i+1$ 桁目でくりあがりが行われたかどうか、という情報です。真なら1、偽なら0です。
$k$ :今作成している $(a,b)$ は、 $a+b \lt N$ となることが確定しているかどうか、という情報です。真なら1、偽なら0です。

初期状態は、
$dp[0][0][0] = dp[0][0][1] = dp[0][1][0] = 1$
となります。これはそれぞれ、 $0$ 桁目で $(0,1)$ を選んだパターン( $1$ 桁目の繰り上がりなし)、 $i$ 桁目で $(0,0)$ を選んだパターン( $1$ 桁目の繰り上がりなし)、 $i$ 桁目で $(0,0)$ を選んだパターン( $1$ 桁目の繰り上がりあり)、の3つのパターンに対応します。

ここからは、0-indexedで考えていきます。例えば、2進数で110という数字は、左から0桁目と1桁目が'1'、2桁目が'0'です。
遷移の個数がかなり多いです。

$N$ の $i$ 桁目が0か1か
$(a,b)$ の $i$ 桁目の組み合わせをどれにするか
$i-1$ 桁目の時点で $j$ がどうだったか
$i$ 桁目の $j$ がどうなるか

によって遷移が決まります。 $N$ の $i$ 桁目が0か1か、についてまずは考えていきます。

$N$ の $i$ 桁目が'1'
$i-1$ の時点で、 $k$ が1ならば $i$ でも $k$ はそのままになります。 $k$ が0のとき、 $a+b$ の $i$ 桁目が'0'になるような計算をしたときに $k$ は1に変化し、'1'になるような計算をした場合は $k$ は0のままです。
$N$ の $i$ 桁目が'0'
$i-1$ の時点で、 $k$ が1ならば $i$ でも $k$ はそのままになります。
$k$ が0のとき、 $a+b$ の $i$ 桁目が'0'になるような計算をしたときに $k$ は0のままですが、'1'になるような計算をした場合はそもそも $N$ を超えてしまうので、遷移ができません。

ということで、 $a+b$ の $i$ 桁目が'0'になるか'1'になるかで、遷移が変わってくることがわかります。あとは、その他の遷移にかかわってくる条件をまとめて場合分けし、 $a+b$ の $i$ 桁目がどうなるかを調べれば、遷移が確定します。

3つの遷移に関わる条件について考え、 $a+b$ の $i$ 桁目がどうなるかを調べる

$(a,b,c,d)= \left\{ \begin{array}{} a,b: (a,b)のi桁目の組み合わせ、(0,0),(0,1),(1,1)の3通り\\ c: i-1桁目のjがどうであったか、0もしくは1 \\ d: i桁目のjがどうなるか、0もしくは1 \end{array} \right.$
として、場合分けをしていきます。

$(a,b,c,d)=(a+b)$ の $i$ 桁目
というように表記し、羅列していきます。 $×$ は、そのようになる可能性がないことを示します。
$(0,0,0,0) = 0$
$(0,0,0,1) = 1$
$(0,0,1,0) = ×$
$(0,0,1,1) = ×$
$(0,1,0,0) = 1$
$(0,1,0,1) = ×$
$(0,1,1,0) = ×$
$(0,1,1,1) = 0$
$(1,1,0,0) = ×$
$(1,1,0,1) = ×$
$(1,1,1,0) = 0$
$(1,1,1,1) = 1$
です。あとは、これらと $N$ の $i$ 桁目による遷移の条件をもとに、ひたすら羅列をしていくことで、答えを求めることができます。

2018-11-10

codeFlyer （bitFlyer Programming Contest）予選 C - 徒歩圏内

真ん中に注目二分探索数え上げ包除原理考察系

問題
 提出コード
これを自力で解けなかったのは結構悔しいです…最近思い通りになかなか解けないですね

解法

$X_j - X_i \leqq D$ , $X_k - X_j \leqq D$ , $D \lt X_k - X_i \leqq 2×D$ となるような $(i,j,k)$ の組を探します。
要素が3つ存在するので、まずは真ん中を決め打ちしたときの $(i,k)$ のペアの個数を求めることを考えます。
ある $j$ について、 $X_j - X_i \leqq D$ となるような $i$ および $X_k - X_j \leqq D$ となるような $k$ の個数は、それぞれ二分探索で求めることができます。

$i$ の個数
$X_j - X_i \leqq D$ を満たすことから、式変形をすると $X_j - D \leqq X_i$ を満たす必要があります。ということで、 $j-1$ までで、上の条件をみたすものの個数を調べるため、
$j$ から、 $X_i \lt X_j -D$ となる $i$ の個数を引けばよいです。
これは、二分探索を利用することで求められます。
$k$ の個数
$X_k - X_j \leqq D$ を満たすことから、 $X_k \leqq X_j + D$ を満たす必要があります。
ということで、 $j+1$ 以降でこの条件を満たす区間の個数を求めるため、
$X_k \leqq X_j + D$ となる $k$ の個数から、 $j$ を引けばよいです。

ということで、 $i$ と $k$ の個数を求められたので、 $(i,k)$ のペアの個数は、それぞれの個数の積になります。
ただし、このままだと $D \lt X_k - X_i$ を満たさないものが存在しています。
ということで、最後にこうならないものを全体から引けば、答えが求まります。

$D \geqq X_k - X_i$ となる $(i,j,k)$ の組の個数を求める
$D \geqq X_k - X_i$ となる $(i,k)$ のペアを決めたとき、ありうる $j$ は $i+1$ ～ $k-1$ です。
今回は、 $k$ を決め打ったときに、上の $D \geqq X_k - X_i$ をみたす $(i,j)$ のペアの個数を求めていきます。
$D \geqq X_k - X_i$ となる $i$ の中で、最も遠いような $i$ をまず探します。
これは、二分探索で求めることができます。これを仮に $l$ とします。
すると、 $(i,j)$ のペアは、今求めた $l$ ～今求めた $k-1$ の中から2つの数字を選ぶ方法と同じになります。
このとき、すべての $(i,j,k)$ について $D \geqq X_k - X_i$ を満たしています。なぜなら、 $l$ がこの条件を満たす $i$ の中で最も遠い場所になるので、それより後ろの場所を $i$ としても、 $X_k$ との距離は小さくなるだけです。
ということで、 $k$ から、 $X_i \lt X_k -D$ となる $i$ の個数を $P_k$ としたときに、
$D \geqq X_k - X_i$ となる $(i,j,k)$ の組の個数は、
$\frac{(P_k)(P_k-1)}{2}$
となります。
全ての $k$ についてこれを求め、最初に数えたものから引いていけば、最終的な答えとなります。

2018-11-09

ABC050 C - Lining Up

条件の作成

問題
 提出コード
人生初の嘘解法を通しました！！！割と条件を省いて書いたのですが通ってしまったので、サンプルが弱いと思います(ACしない凡例が存在します)。
例えば、自分のコードだと

5  
0 0 0 2 2

という入力で答えが6になります(本来、このような入力の場合答えは0になるはずです)

解法

解法自体は正しいです(のはずです)
報告が正しいかどうかを判定したら、あとは答えが一意に決まります。
報告の判定方法は、

Nが偶数
報告全てが奇数になっていて、報告された数字はすべて2つずつ存在しています。
また、報告されるべき数字は1,3,5,7...N-1の奇数です。
Nが奇数
報告される数字は偶数になっていて、0を除き報告された数字はすべて2つずつ存在しています。0は1回だけ報告されます。
報告されるべき数字は0,2,4...N-1です。

上の条件を満たさないときは答えが0、満たすときは
$2^{\frac{N}{2}}$ です(Nが奇数の場合は切り捨てをします)。
これを求めるだけで答えとなります。
正しい報告かどうかの判定をする部分の条件をかなり緩めにしたのですが、ACをしてしまいました。よくないです。

2018-11-09

codeFlyer （bitFlyer Programming Contest）予選 D - ハンコ

考察系座標圧縮いもす法累積和数え上げ

問題
 提出コード

解法

基本方針は、いもす法を利用して移動したときに黒くなる部分を求めていくことです。
紙の左上にまずはハンコを合わせます。すると、
$(i,j)$ マスが黒かったとき、右に $w-m$ マス、下に $h-n$ マスの範囲内がすべて黒く塗られることになります。
ということで、これを1次元いもす法を2回適用、もしくは2次元のいもす法を適用することで黒く塗りつぶされている場所がわかります。
ですが、もちろん $O(HW)$ が間に合うわけがないので、効率化します。 f:id:emtubasa:20181110175409p:plain 紙全体を図のように場合分けして考えます。

白い部分
1つ1つの四角は、多くて $10^{6}$ マスなので、そのまま求めてしまって十分です。
オレンジの部分
オレンジの部分は、どちらも $w-2×m$ 列存在します。
元々のハンコの上から $i$ 行目の $m$ マスは、それぞれのオレンジの部分についての上から $i$ 行目のマスを通過します。ということで、元々のハンコについて、 $i$ 行目で1つでも黒い部分が存在していたら、オレンジの部分についての $i$ 行目はすべて黒くなり、そうでなければすべて白くなっています。
全ての $i$ について同じことが言えます。ので、オレンジの部分は1列に圧縮することができます。
そして、最後にオレンジの部分を圧縮した1列の個数を、 $w-2×m$ 倍することで、個数を数え上げることができます。
青の部分
青の部分は、どちらも $h-2×n$ 行存在します。
オレンジの縦横逆バージョンです。なので、1行に圧縮することができ、最後に $h-2×n$ 倍してあげることで、数え上げることができます。
黄色の部分
この部分は、縦が $h-2×n$ 行、横が $w-2×m$ 列になっています。
ハンコの $n×m$ マスはすべてこの黄色の部分を少なくとも1度は通ります。
ので、 $n×m$ マスのうち1つでも黒い部分が存在していれば、黄色の部分はすべて黒になります。
黄色の部分を1マスに圧縮し、最後に $(h-2×n)×(w-2×m)$ 倍してあげると、この部分を数え上げることができます。

ということで、最終的には、
$min(h,2×n+1)$ 行 $min(w,2×m+1)$ 列の長方形についていもす法によって状態をつくりあげ、最後に圧縮している部分を拡大することで、答えを求めることができます。

2018-11-09

AGC024 B - Colorful Slimes

貪欲法考察系 Range Minimum Query(RMQ)

問題
 提出コード

解法

スライムを好きなタイミングで捕まえることができ、捕まえる、魔法を唱える、捕まえる魔法を唱える…といったような順番で操作を行うことができます。ので、魔法を唱えるを唱える回数 $k$ をまずは固定してしまって、捕まえるスライムの種類を決めてから、最後に $k×x$ を追加します。
これを $k$ について全探索して最小値を求めることで答えを求めていきます。
$k$ 回魔法を唱えることにすると、 $0~k$ 回のうち好きな回数変色ができます。
ということで、魔法を唱える回数が決まってしまっているので、 $i$ 番目のスライムを入手したいとき、 $i-k$ ～ $i$ のスライムのうち一番入手時間が短いものを選んでくると、 $i$ 番目のスライムを入手するために必要な時間を最小にすることができます。
区間についての最小値を求めたいので、RMQを使ってごり押しをします。
$i-k$ が負になる場合を考慮するために、RMQは要素数を $2×N$ にし、 $a_1$ ～ $a_N$ を2つ並べます。すると、 $i+k-n$ は負になることがない(魔法を唱える回数が $N$ より大きくなったときに答えとなることは絶対にありません)ので、配列外を参照することはなくなります。
ということで、あとは全ての $i$ について、区間 $[i-k,i+1)$ の最小値をRMQで求めて加算していき、最後に $k×x$ を追加すれば $k$ 回魔法を唱える場合の最小値になります。
これを $k$ について全探索することで、答えが求まります。

2018-11-09

ARC077 D - 11

包除原理数え上げ考察系逆元 mod N

問題
 提出コード

解法

ダブっている数字は数列に1つ必ず存在します。
ダブってる数字のうち左側にあるものを $x$ ,右側にあるものを $y$ としたとき、数列は次のようになっています。
$l, x, m, y, r$
ここで、 $l,m,r$ はそれぞれ0個以上の要素を持っている数列です。
長さ $k$ の部分列を数え上げる方針としては、まず
$l, x, m, r$ という $y$ を除いたパターンを数え、その後 $y$ が存在した場合に新しく作成できるパターンを計算して合算します。

$y$ を無視した場合
$l, x, m, r$
という数列には、 $1$ ～ $n$ の数字がすべて1つずつ含まれています。ので、全ての数字について、使うか使わないかの2通りを考えればよく、これは
$_nC_k$
となります。
$y$ を考慮した場合
新しく増えるパターンは、必ず $y$ を使用します。なぜなら、使用しないパターンはすでに前の段階で数えているからです。
ここは、さらに2つに場合分けします。 $x$ を部分列に含むか含まないか、です。

$x$ を含む場合
$x,y$ を使用することが確定しているので、残った $l,m,r$ の部分から $k-2$ 個を選びます。ということで
$_{(n-1)}C_{(k-2)}$
となります。
$x$ を含まない場合
$x$ と $y$ が同じ数字であるので、被りがないように数え上げなければなりません。
ここで、どのように部分列を選んだらまだ数えられてない部分列(ここで数えるべき部分列)になるかというと、
$m$ の中から少なくとも1つの要素を選んだ場合
です。
$l$ の要素は、 $x$ を使用した場合でも $y$ を使用した場合でも、その数字より左側に、 $r$ はどちらの場合でも右側に存在します。
ですが、 $m$ にある要素は、 $x$ を使用した場合は $x$ の右側に、 $y$ を使用した場合では $y$ の左側に並ぶことになりますので、かならずまだ数えられてない、新しい部分列を作成できます。
$m$ の中から少なくとも1つの要素を選ぶことについて考えると、
$l,m,r$ 全て使うパターン、 $m,r$ を使うパターン、 $l,m$ を使うパターン、 $m$ のみ使うパターンの4通りです。
これをそれぞれ求めるのは難しいので、 $l,m,r$ の中から自由に選ぶパターンから、余分なパターンを引く、包除原理の考え方を使うことにします。
$l,m,r$ の中から自由に選ぶパターンの計算式をたてます。すでに決まっているのは $y$ のみなので、 $l,m,r$ から残りの $k-1$ 個を選択します。 $l,m,r$ の個数をその文字で表現したとき、
$_{(l+m+r)}C_{(k-1)}$ となります。
そして、余分なパターンは、 $m$ を使用しないパターンです。これは言い換えると、 $l,r$ のみから選んだパターン、となります。
$l,r$ から自由に選ぶパターンは、簡単に計算することができ、
$_{(l+r)}C_{(k-1)}$ です。あとは、上の式から下の式を引くだけでよく、
$_{(l+m+r)}C_{(k-1)} - _{(l+r)}C_{(k-1)}$ となります。

ということで、最終的な式は次のようになります。
$_nC_k + _{(n-1)}C_{(k-2)} + _{(l+m+r)}C_{(k-1)} - _{(l+r)}C_{(k-1)}$
あとは、それぞれの $k$ についてこれを求めれば、答えとなります。

2018-11-09

ABC018 C - 菱型カウント

累積和いもす法

問題
 提出コード

解法

ある地点で×な部分があると、その×を中心として作成したひし形の範囲内の任意のマス(x,y)について、(x,y)を中心とするひし形は作成できません。　ということで、
memo[i][j] = (i,j)を中心としてひし形を作成したとき、その範囲内に存在する×印の個数
とすると、ということで、全ての×印のマスについて、その範囲内のマス目(x,y)についてmemo[x][[y]に1追加すれば、memoが完成します。
あとは、中心としてありうる(i,j)について、memo[i][j]=0となっているマス目を調べればよいです。
ここで、単純にmemo[x][y]に1を追加していたのでは間に合わないので、いもす法を用います。
(x,y)が×印だったとき、
memo[i + l][max(0, j - k + 1 + l)]には1を追加、memo[i + l][min(c, j + k - l)]からは1を減らす、という操作をしていけばよいです。
ここで、lは0~k-1になります。
あとは、横方向について累積和をとると、memoを完成させることができます。

ツバサの備忘録

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

ABC050 D - Xor Sum

解法

codeFlyer （bitFlyer Programming Contest）予選 C - 徒歩圏内

解法

ABC050 C - Lining Up

解法

codeFlyer （bitFlyer Programming Contest）予選 D - ハンコ

解法

AGC024 B - Colorful Slimes

解法

ARC077 D - 11

解法

ABC018 C - 菱型カウント

解法