アルゴリズム忘備録

競技プログラミングとかデータ分析とか

B: Moderate Differences - AtCoder Grand Contest 017

agc017.contest.atcoder.jp

 

長さNの数列を構成したい。最初と最後の要素がA, Bで与えられる。また、隣り合う要素同士の差はC以上D以下になるようにしたい。このような構成は可能か?

 

最初の要素を除くN-1個の要素について、k個が前の要素以上、N-1-k個が前の要素以下と仮定してもよい。その時、kを固定すると、最後の要素Bとして可能な値の範囲は次のようになる。

A + kC - (N-1-k)D <= B <= A + kD - (N-1-k)C

与えられたBがこの条件を満たすなら構成が可能。O(N)。

A: Biscuits - AtCoder Grand Contest 017

agc017.contest.atcoder.jp

 

数列A[i]が与えられるので、部分列をとってその和の余りを0または1にしたい。そのような部分列は何通りあるか?

 

k番目までの数列の部分列をとったときにあまりが0または1になる組み合わせをa[0][k], a[1][k]とおく。A[k + 1]が奇数または偶数によって場合分けし、dpを更新していく。O(N)。

C: 節約生活 - AtCoder Regular Contest 007

arc007.contest.atcoder.jp

 

最大10の周期でxoxooxoxxという並びが繰り返す。この周期と同じ周期を幾つか用いて、それぞれ任意の数だけずらして重ねたときに少なくとも1個の○が存在するようにしたい。最小でこの周期を何個使えばいいか。

 

周期の長さを持つ01bitでoxを表現する。これを幾つかローテーションしてandをとったときに0になる最小の個数を求めればよい。周期は最大10個なので、全探索で十分に間に合う。O(N*2^N)。

C: THE☆たこ焼き祭り2012 - AtCoder Regular Contest 008

arc008.contest.atcoder.jp

 

N人の人が(x[i], y[i])にいる。それぞれ最大t[i]の速度でたこ焼きを投げられ、また最大r[i]までの速度で投げられたたこ焼きをキャッチできる。一人目の人が1秒おきにたこ焼きを投げ、その他の人もたこ焼きを受け取ったらそれを更に別の人に投げることができる。これを繰り返すことで全員にたこ焼きを行き渡らせる時、最小で何秒かかるか?

 

すべての人のペアについて、min(投げられる最大速度、受け取れる最大速度) の速度でたこ焼きを投げるとして、そのペアについてたこ焼きを投げるのにかかる時間をエッジの長さとしてグラフを構成する。

 

双方向だがそれぞれのエッジの長さが異なる完全グラフになる。完全グラフなので隣接行列で、最初の人からダイクストラで全員までの距離を計算する。この距離を降順ソートし、順に一秒おきにたこ焼きをその人に向かって投げるという戦略が最適。この時、min(たこ焼きを投げる時間+距離)が最小の時間になる。O(N^2)。

E: guruguru - AtCoder Regular Contest 077

arc077.contest.atcoder.jp

 

整数xを一つ決める。ある数a[i]に対して、a[i] + 1 またはxに遷移する、という操作を行い、a[1]~a[n]までの遷移を実現する。この操作の回数が最小になるようにxを決めた時、その最小回数を求めよ。

 

素直にやるとO(NM)の問題で当然間に合わない。そこでx=kのときの操作回数f_k(x)を考えると、xの不連続点が存在する高々1次関数の組み合わせになっていることがわかる。例えばa[i] < a[i + 1]であれば、a[i] < x <= a[i + 1]のときはxに遷移したほうが操作回数が最小になる。この場合はxの1次関数になる。それ以外のときは+1を繰り返したほうが最小になる。この場合はxの0次関数(定数関数)になる。

 

そこで、[f_1(x), f_2(x), ... , f_m(x)] という数列を構成することを考えると、この数列に1次関数を一気に足す、という操作がO(1)やO(logN)程度でできれば解決である。

 

そこでimos法を用いる。具体的には、n次関数の係数ごとにimos法を用いて、最後にx^nを書けながらf_k(x)を復元する、という操作になる。O(N)。

 

n次関数の和はそれぞれの次数の係数の和をとった関数に等しい、つまり

(ax + b) + (cx + d) = (a + c)x + (b + d)

という当たり前のロジックを使うものだけど慣れてないと思いつくのは難しい気がした。

 

D: 11 - AtCoder Regular Contest 077

arc077.contest.atcoder.jp

 

1~nの数で構成された、n+1個の数列が与えられる。この数列の中で、1~nはそれぞれ少なくとも1回以上は登場する。この時、長さ1~n+1の部分列で、異なる個数の総和を求めよ。

 

要はある数が一つだけダブっており、それ以外は全部1個づつ現れる数列である。これを以下の3パターンに分けてカウントする。(以下、長さkの部分列とする)

  1. ダブりの数を含まない場合 n-2Ck 通り
  2. ダブりの数を1個含む場合 n-2Ck-1通り * ダブリの数の選び方2通り
  3. ダブりの数を2個含む場合 n-2Ck-2 通り

ただし、2番については次のような場合をダブルカウントしている。

 

xxxxxxxxxx11yyyyyyyyyyyyyy

 

そこで、この数を引く。これは、ダブっている数の両側にある数列の個数をmとおくとmCk-1通りであり、この数を引けばよい。mは愚直に数えてもO(N)である。

全体で計算量はO(N)になる。

C: pushpush - AtCoder Regular Contest 077

arc077.contest.atcoder.jp

 

数列a[i]が与えられる。このa[i]とある空の別の数列b[j]について、bの末尾にa[i]を加え、bをreverseする、という操作をすべてのa[i]について繰り返す。最後にできる数列を求めよ。

 

毎回Reverseするのではなく、Nが偶数なら最後に一回Reverseすればよい。あとはa[i]の要素を順に末尾、先頭、末尾、先頭と追加していく。O(N)。