AOJ 1194:バンパイア

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1194&lang=jp

解法

二分探索。

ビルのx座標が整数値でしかも絶対値が20以下なので

H[i] = 区間[i,i+1]のビルの最大値

とおいてt秒あとの区間[a,a+1]の太陽の高さを求めてかぶってるかどうかを判定すれば良い。

SRM Div2Med ProblemSetsEasy

div1easyと同じだった(div2の方が制約が簡単)

問題

easy用に使える問題がE個

easyもしくはmed用に使える問題がEM個

med用に使える問題がM個

medもしくはhard用に使える問題がMH個

hard用に使える問題がH個

ある。

これらからeasy問題、med問題、hard問題の問題セットをいくつ作ることができるか

解法

二分探索。なぜか落ちてて悲しかった。

TCO 15 1B Med The Tips

問題

n個の宝を探す宝探しゲームをする。
ノーヒントで宝iを探せる確率はp[i]
G[i][j]=Yならばi番目の宝が見つかればi番目の宝にj番目の宝の場所も記されているのでj番目の宝も見つけられる。

見つけられる宝の個数の期待値を求める問題。

解法

i番目の宝が見つかる確率をp[i]とおく。

G'[i][j]を「iからjまで連結しているならば1」として隣接行列を作る。

この時p[i]は「1- (iに到達できるnodeがどれも見つからない)」なので余事象で簡単に計算できる。

yukicoder No168. ものさし

問題

http://yukicoder.me/problems/296
頂点1から頂点nまでの任意のパスに含まれる全ての辺の中での最小の長さを10単位で切り上げする問題。

解法

ダイクストラっぽくやりました。
精度が怖いのでlong longで距離をとって平方根は二分探索でとりました

CF 534D. Handshakes

問題

http://codeforces.com/problemset/problem/534/D
n人の人がいて、適当な順番で部屋に入る。部屋に3人以上いたら、適当な3人組は部屋の外に出て行ってよい(出て行ったら二度と部屋に来ない)(出て行かなくても良い)
どの人も、部屋にx人いたらx人全員と握手をする。
さて、それぞれの人が「何人と握手したいか」という希望を入力として与えられるとき、全員の希望を満たすような部屋の入り方の順番はあるかどうか。あったらその順番を出力せよ。

解法

「希望人数が多い人」から握手させていけば良い。

CF 534C. Polycarpus' Dice

問題

http://codeforces.com/problemset/problem/534/C
n個のサイコロがあってサイコロiの目は1〜diのいずれかが出る。
このn個のサイコロをふって出た目の総和がAだとする。
このとき、各iに対して「サイコロiの出た目の数としてあり得ない目の数」の種類数を求める問題。
例えば、普通の6面のサイコロを2個ふってその目の和が8だったら、どちらのサイコロも1の目が出ることはあり得ないため、答えは{1,1}となる。

解法

各サイコロiに対してその目の出うる目の数の下限と上限を考える。
「サイコロiがxを出して他のサイコロが全部本気出してもAには届かないよなぁ」
というxのうち最大のもの+1が下限で、これをx1
「サイコロiが本気出してyの目が出たとき他のサイコロが全部1の目になってもAより大きいなぁ」
というyのうち最小のもの-1が上限(の候補の一つ)で、これをy1
とおくと、
サイコロiのでうる目の値は
[max(1,x1) , min(y1,di)]
となる。あとはdiからこの区間内の整数の個数を引けば良い。

ただしn=1の時はA=出たサイコロの目のはずなので、di-1を出力すれば良い。

GCJ Qualification Round 2015 Problem C. Dijkstra

問題

i,j,kのみで構成されたL文字の文字列sをX個連結した文字列を適当に3つに分割して、
「分割した部分文字列の各要素を四元数として見て積をとると順にi,j,kとすることが出来るかどうか」
を判定する問題。
例えば、
L=2,X=6,s="ji"のとき、連結して出来た文字列は
jijijijijiji
であるが、これを
jij | iji | jijiji
と分割することによってそれぞれの積をとるとi,j,kになるので答えはYESとなる。

制限

テストケース数<=100

L<=10000
L*X<=10000(small)
L*X<=10^16(large) , X<=10^12(large)

解法(small)

以下の性質を利用する。
・a,b,cが四元数のとき(a*b)*c=a*(b*c) (四元数の結合則)
連結して出来た文字列をtとしたとき、
t = ○ | △ | □
と分割してそれぞれの積が順にi,j,kとなっているならば
○*△=(○の積)*(△の積)=i*j=k
○*△*□ = (○*△)*(□の積) = k*k = -1
となるはず.
よって、連結して出来た文字列を順に掛けて行って途中でi,kが出てかつ全部掛けたら-1になっていれば良いのでO(L*X)で出来る。

解法(large)

以下の性質を利用する。
・四元数の要素である1,-1,i,-i,j,-j,k,-kはどれも4乗すると1になる。
sをX個連結した後に3分割するので、各分割の中にはsがそれぞれ幾つか含まれていなければならない。その個数をそれぞれa,b,cとする。また、sの文字を全て掛けたものをhとおく。この時、
・最初の分割の積=h^a * (sの途中までの積) = i
・真ん中の分割の積=h^b * (sの途中から別のsの途中までの積) = j
・最後の分割の積=h^c * (sの途中からsの最後までの積) = k
みたいな感じになる(厳密にはa+b+c=X-2やa+b+c=X-1の場合等がありえる)
そしてh^4=1なので、a,b,cは4で剰余をとってよかったりする。
そう考えると考えるべき状態数は
a,b,cが0,1,2,3のそれぞれの場合について考えれば良いのだから、
X = min(X, 12+X%12)
として良い。こうするとX<24だから十分間に合う。

SRM636 Div2 Hard : ChocolateDividingHard

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13388

h×wのグリッドが与えられる。各グリッドには0~9の文字が欠かれている。このグリッドを、切り込みを入れて4×4に分割する。

それぞれのブロックの中のグリッドの数字の和の最小値を最大にする問題。

制約：h,w<=75

解法

上手く切り込み入れて和の最小値をk以上にすることが出来るかを判別。

縦の切り込みを全通り試して、k以上に出来るかを貪欲にやる。
判定は、累積和やったりして多分O(75^4logN)くらいで危ない気がしたけどなんか通った。

n項間線形漸化式を持った数列の一般項

体K上の数列{x_i}がp=0,1,2,...に対して

の関係を満たすとき、線形回帰数列と言います。例えば加算個の状態を持ったマルコフモデルとかでの定常分布でこういう式が出てきて一般項を求めたい、もしくは三重対角行列の行列式を求めるときにこういう感じの漸化式が出てくると思いますが、今回はそれを解決したいと思います。
なお、本記事は
斎藤正彦著『線形代数入門』『線形代数演習』(東京大学出版会)
を参考にさせて頂いております。ちなみにこの本はとても良い本です。

出来るだけ事前知識を必要としないように書くつもりですが、やはり線形代数の基礎的な知識(次元や基底の定義とか)は必要だと思います。

目標

さて、まずは「体K上の数列の集合」を考えます。(大体KはRもしくはCです)
この集合の部分集合として上の漸化式を満たすものの全体をVとします。今回はこの空間Vが実は線形空間でしかもその次元がnであることを示した後、n個の基底の構成方法を述べることによってVの任意の元すなわち上の漸化式を満たす数列がこれらの基底の線形結合で表せる、ということを述べます。

まず、二つの数列{a_i},{b_i}に対して加法とスカラー乗法を定義しますがこれは簡単で
{a_i}+{b_i} = {a_i+b_i}
k*{a_i} = {k*a_i}
と定義します(普通のやつです)

Vが線形空間かどうか

そして数列{x_i},{y_i}∈Vの時、{x_i}+{y_i}及びk*{x_i}は明らかにVの要素になっている(実際に計算すれば確かめられます)ので、Vはこれらの演算で閉じていて、Vの零元を{0,0,...}と定義すれば確かに零元になっていて結合則とかもろもろは体K上の数列であることから実際に計算してみれば明らかですので、Vは線形空間となっています。

Vの次元は?

VからK^nへの写像Tを「数列の最初のn項を取り出す写像」つまり

と定義します。これはT(ax+by)=aT(x)+bT(y)より明らかに線形写像で、任意のK^nの要素に対してそのn個の数を最初のn項にした数列がV内に存在するため全射で、違う数列は違う値に移されるため、全単射である。従って同型写像である。

同型写像が存在する時、どちらの空間も次元が等しいため、

dimV = dim(K^n) = n

です。これはV内のn個の線形独立な数列を見つけたらVの任意の要素がこれらの線形結合で表されることに他なりません。

解

1.特性多項式

ここが一番大事なところです。そのためにまずVからVへ移す写像DとIを考えます。

Iは恒等写像で、Dはずらし変換、即ち

と定義します。DがVからVへ移すことはDによって数列のn項間の関係が変化しないことから明らかです。また、写像f,gの加法と乗法及びスカラー乗法を

(f+g)(x) = f(x)+g(x)

(fg)(x) = f(g(x))

(k*f)(x) = k*f(x)

と定義すると、Iは当然ながらDも

D(ax+by) = aD(x)+bD(y)

となります。そしてDの冪乗D^nもDをn回合成した写像として定義することが出来ます。

この定義に基づくとこの画像で確かめている通り

(aD+bI)と(cD+dI)は交換可能(AB=BA)であることが分かります。

最初の漸化式の左辺をpに関する一般項とする数列{0_p}は、恒等的に0、即ち零元だから

0_p = (D^n(x))_p + (a_1*D^(n-1)(x))_p + ... + (a_{n-1}*D(x))_p + (a_n*I(x))p = 0

写像の和算の定義より右辺は

となり、これがどのpに対しても0だから

となります。この()内のDをスカラーuに変えて多項式にしたものを特性多項式と呼びます。これをΦ(u)で表すことにします。すると上の式はΦ(D)x=0と表記できます。注意してほしいのはこれの左辺は数列を表すものであって、スカラーではないということです。

2.特性多項式の根から解を生成する

代数学の基本定理より、特性多項式の根はn個あります。これらのn個の根をそれぞれb1,b2,...,bnとします。

この時、Φ(u)=(u-b1)(u-b2)...(u-bn)

と表され、先ほど確かめた通り、交換可能な者同士の積ならばDとIに関しても展開した結果が普通の展開と結果が同じになるので、Φ(D)=(D-b1I)(D-b2I)...(D-bnI)となります。

ここで、各(D-biI)と(D-bjI)は交換可能だから、あるkに対してxが(D-bkI)x=0となっている時、かけ算の順序で(D-bkI)を最後に持ってきて

Φ(D) = (D-b1I)...(D-bnI)(D-bkI)x = 0

は明らか。

従って、(D-biI)^mi x=0 (miは解biの重複度)

の解を全てのbiに対してmi個ずつ見つけ、これらが線形独立であることを証明すれば、n個の基底が見つかったことになる。

mi=1のとき

(D-bi)x=0よりDx=bi*x

Dxは一項ずらすものなので、これは明らかに公比がbiの等比数列である。つまり例えば

x_k = (bi)^{k}

が解である。

mi>1のとき

(D-bi)^m (x)=0

天下り的だが

x_k = k^j *(bi)^{k-1} (j=0,1,...,mi-1)

を考えると確かにこれらは(D-bi)^mi(x) = 0のmi個の解になっている。

以上より、m1+m2+... = n個の解が構成出来た。

また、これらの解が線形独立であることは実際にこれらの数列の線形結合が0に等しいならば自明な線形関係が成り立つ(係数が全て0である)ことによって示すことが出来る。

最後らへんは結構投げやりだが、これによって線形回帰数列を求めることが出来た。

拡張ユークリッドの互除法

不定方程式の中でも比較的有名なベズー方程式を解くアルゴリズムとして比較的有名な拡張ユークリッドの互除法を、線形代数の視点から考えてみました。
具体的には
・拡張ユークリッドの互除法によって得られるもの
・解空間はどのように構成出来るか
について色々考えました。必要な知識は
・拡張してないユークリッドの互除法
・行基本変形
・線形代数の基礎すぎる知識(各行が線形独立な行列は正則だよとか)
・線形代数の各種すぎる定義(A+B={x+y ; x∈A,y∈B}とか線形独立とか)

です。線形代数が好きでユークリッドの互除法を拡張したい人にはぴったりなトピックだと思います。

問題

零でない整数a,b,cにたいして、

ax+by=c

の解空間を構成せよ。

考察

ベズーの補題より、gcd(a,b)がcを割り切ることが解の存在性の必要充分条件です。

よくよく考えると、gcd(a,b)=dとおくとax+byはdの倍数なので割り切らない時は解が存在しないので対偶をとると解が存在する条件が「dがcを割り切る」ということが分かります。逆に割り切るならば解が存在することも示したいのですが、これは具体的な解の構成方法を示すことによって示します。以下ではcはdを割り切りc=mdというのを前提に話を進めます。

1.拡張ユークリッドの互除法とは？？

(1.1)ax+by=d

(a,b)に対してgcd(a,b)を求める手続きがユークリッドの互除法です。この手続きを行列の行基本変形に拡張して考えることによって(1)を解くことが出来ます。それが拡張ユークリッドの互除法です。要するに方程式(1.1)を解くアルゴリズムです。

(1 0) (a) = (a)

(0 1) (b) = (b)

に対して、(a,b)に対して行われるユークリッドの互除法は

・片方から片方の定数倍引く

・入れ替える

なのでどちらの操作も同等な基本行列が存在します。そして有限回で終了するのでその有限個の行列を左から掛けていくことによって最終的には右辺のベクトルが(d,0)になってその時の係数行列の１行目の2つの要素が方程式(1.1)の解になっているという訳です。なお、2行目の2つの要素は(ax+by=0)の解となっています。

2.方程式(1.1)の解空間はどんな空間？？

まず(1.1)の解空間を考えます。色々知っている人は斉次なんちゃらと似てると思いますがその通りです。色々しっていなくても必要な知識さえあれば証明できますが、結論から言うと

(x0,y0)を(1.1)の非ゼロな要素,(z0,w0)をax+by=0の非ゼロな解

とすると(1.1)の任意の解は任意の整数kで

(x0 + k*z0 , y0 + k*w0)

と表すことが出来ます。

3.ax+by=c=mdの解空間は？？

結論から言えば

(m*x0 + k*z0, m*y0 + k*w0)

と表すことが出来ます。証明は2と同じ感じでした。

解

入力されたa,b,cに対して,

拡張ユークリッドの互除法によって得られた係数行列の成分を

(x,y)

(z,w)

とする。また、この時d=gcd(a,b)である。

・dがcを割り切らない時は解なし、つまり空集合

・dがcを割り切る時は、m=c/dとして

{ (m*x + k*z , (m*y + k*w) ; k∈整数 }

が解であり、従って割り切るときは必ず解が存在するのでベズーの補題が示されたことになります。