狠狠撸

狠狠撸Share a Scribd company logo

AtCoder Beginner Contest 009 解説

?
?
A
AtCoder Inc.

AtCoder Beginner Contest 009 解説

1 of 106
Downloaded 14 times
AtCoder Beginner Contest 009? 解説
はじめに ?競技プログラミングが初めての人? ?まだまだ競技プログラミングに慣れていない人 最も基礎的なことは過去の解説に載っています！? 特に ABC004 の解説が詳しいです。? http://www.slideshare.net/chokudai/abc004 AtCoder の練習用コンテストも活用しましょう！? http://practice.contest.atcoder.jp/
A問題 引越し作業
A - 問題概要 問題? N 個のダンボールを運びたい。? 1 往復で最大 2 個のダンボールを運ぶことができる。? 最低でも何往復する必要があるか？ 制限? 1 ≦ N ≦ 1,000
A - プログラムの流れ 入力、出力でつまずく場合? →入出力について復習！? http://www.slideshare.net/chokudai/abc004? http://practice.contest.atcoder.jp/ N を入力する 答えを計算する 答えを出力する
A - プログラムの流れ 入力、出力でつまずく場合? →入出力について復習！? http://www.slideshare.net/chokudai/abc004? http://practice.contest.atcoder.jp/ N を入力する 答えを計算する 答えを出力する 残りは答えの計算? ↓? 答えを計算する方法（＝アルゴリズム）を考えよう！
A - 解き方 重要な事実? ?ダンボールが 2 個以上残っているときは? ?1 回の往復で 2 個運んでしまうほうがよい。 当たり前のようなことですが、? プログラムを書いて計算させるにあたっては? こういった事実をきちんと確認するのが大事です！
A - 解き方 この事実を使えば、次のように運ぶのが最適: ?ダンボールが 1 個しかないなら、それを運ぶ。? ?ダンボールが 2 個以上あれば、2 個運ぶ。 これをダンボールがなくなるまで繰り返して、? そのときの回数が答えになる。
A - プログラム 擬似コードで表現すると、こんな感じ: count ← 0 # while N > 0: # if N == 1 # N ← N - 1 # else # N ← N - 2 # count ← count + 1 # 往復回数を初期化 ダンボールがまだある間 残りが 1 個のとき その 1 個を運ぶ 2 個以上残っているとき 2 個まとめて運ぶ 往復回数を 1 増やす
A - さらに考えると ダンボールの個数 N が…… 偶数なら? ?毎回 2 個運べば、N / 2 回の往復で運びきれる。 奇数なら? ?はじめの (N - 1) / 2 回では 2 個運び、? ?残った 1 個を最後の 1 回で運べばいい。
A - さらに考えると ダンボールの個数 N が…… 偶数なら? ?毎回 2 個運べば、N / 2 回の往復で運びきれる。 奇数なら? ?はじめの (N - 1) / 2 回では 2 個運び、? ?残った 1 個を最後の 1 回で運べばいい。
A - さらに考えると ダンボールの個数 N が…… 偶数なら? ?毎回 2 個運べば、N / 2 回の往復で運びきれる。 奇数なら? ?はじめの (N - 1) / 2 回では 2 個運び、? ?残った 1 個を最後の 1 回で運べばいい。 つまり、往復回数は N / 2 の切り上げ！
A - 計算量について ?はじめに考えたアルゴリズムは O(N) 時間? ?N / 2 の切り上げを計算するだけなら O(1) 時間 今回は N が小さいのでどちらを用いても解けます。? ? より難しい問題に挑戦するときには、自分の考えたアルゴリズムの? 計算量を見積もれるようになっていないと厳しいです。? 少しずつ慣れていき、計算量を常に考える癖をつけていきましょう。
B問題 心配性な富豪、? ファミリーレストランに行く。
B - 問題概要 問題? ファミレスのメニューに N 種類の料理があり、? それぞれの料理の値段がわかっている。? 2 番目に高い料理の値段はいくらか？ 制限? 1 ≦ N ≦ 100? すべての料理の値段が同じであることはない。
B - 解く前に確認 この問題で必要なこと? ??配列、リスト等の基本的な取り扱い? ??ソート（整列）の方法 配列の基礎については、? またもや過去スライドをチェック！? http://www.slideshare.net/chokudai/abc004
B - ソート（整列） ソートとは……? ?配列などの要素を、ある順番に従って並び替える たとえば [51, 39, 66, 42, 10] という配列を? ?昇順（小さい方から順番）にソート? ??→?[10, 39, 42, 51, 66]? ?降順（大きい方から順番）にソート? ??→?[66, 51, 42, 39, 10]
B - ソートアルゴリズム アルゴリズムやプログラミングの本では? たくさんのソートアルゴリズムが紹介されている? ?挿入ソート、選択ソート、バブルソート、クイックソート、マージソート、…
B - ソートアルゴリズム アルゴリズムやプログラミングの本では? たくさんのソートアルゴリズムが紹介されている? ?挿入ソート、選択ソート、バブルソート、クイックソート、マージソート、… しかし実際にソートをしたいときにこれらを? 自分で実装する必要は（ふつうは）ない。なぜか？? →言語の標準ライブラリに入っていることが多い！ もちろん、ソートアルゴリズムを学んだり、同じ目的のアルゴリズムでも手法に よって計算量などの特徴が違うことを理解したりするために、自分で色んなソー トアルゴリズムを調べて実装してみるのはよいこと。
B - ソートアルゴリズム 各言語のライブラリまで全部説明はできないので…… ! ! ! ! 各自で調べましょう！ Python?ソート
B - 本題、解き方 値段が高い順にソートして、? その 2 番目を見るだけでは？
B - 注意 値段が 100 円、200 円、300 円、300 円のとき? 2 番目に高いのは 200 円（300 円ではない）? 問題文にもちゃんと書かれていました 値段が高い順にソートして、? その 2 番目を見るだけでは？ ダメです
B - 解き方 値段の配列を ! 10 50 90 50 80 90 30
B - 解き方 値段の配列を ! とりあえず降順にソートして 10 50 90 50 80 90 30 90 90 80 50 50 30 10
B - 解き方 値段の配列を ! とりあえず降順にソートして 10 50 90 50 80 90 30 90 90 80 50 50 30 10 1番高い料理たち 2 番目に高い料理? これが知りたい
B - 解き方 値段の配列を ! とりあえず降順にソートして 10 50 90 50 80 90 30 90 90 80 50 50 30 10 1番高い料理たち 2 番目に高い料理? これが知りたい 1番高い料理たちの次に出てくるものを求めればいい！
B - プログラム 今回も擬似コードにしてみると、こんな感じ: # N # A ? X ← sort(A) # A for i = 0 to N - 1 # if X[i] != X[0] # answer ← X[i] # break # は料理の種類数 は値段の配列 を降順にソートする 先頭から順に見ていく 1 番高い料理でないなら それを答えにして ループを抜け出す
B - 解き方その2 この考えはそのままではダメだった。 値段が高い順にソートして、? その 2 番目を見るだけでは？
B - 解き方その2 この考えはそのままではダメだった。 しかし、? 同じ値段の料理がない時にはこれでもうまくいく！ 値段が高い順にソートして、? その 2 番目を見るだけでは？
B - 解き方その2 なら、同じ値段の料理をなくしてしまえばいい！ ! ! ? 先にこういった処理を行っておけば、? 降順ソートして 2 番目を見るだけで OK 10 50 90 50 80 90 30 10 50 80 90 30
B - 重複削除アルゴリズム 標準ライブラリにある言語も多いはず ! ! ! ! Ruby?重複?削除
C問題 辞書式順序ふたたび
C - 問題概要 問題? 文字列 S を並び替えて文字列 T を作る。? ただし動いた文字の個数が K 以下でなければダメ。? そのような制限のもとで、辞書順最小の T は？ 制限? 1 ≦ N (S の文字数) ≦ 100? 1 ≦ K ≦ N
C - 辞書順最小のアイデア 基本は、問題文にあったヒントのように実装? ?読んでない場合は http://abc009.contest.atcoder.jp/tasks/abc009_3 ヒントの繰り返しですが、重要なのは? ??最初のほうに小さいアルファベットを持ってくる? ??あるアルファベットを持ってきたときに、? ??制限を満たせるかどうかを判定する? の 2 点です。
C - プログラムのイメージ 今回も擬似コードでイメージを掴みましょう: ! ! T ← “” for i = 0 to N - 1 for c in (まだ使える文字を小さい順に)? if (T + c にして大丈夫なら) T ← T + c break
C - プログラムのイメージ 今回も擬似コードでイメージを掴みましょう: ! ! ! ? 括弧書きでごまかした部分をちゃんと考える！ T ← “” for i = 0 to N - 1 for c in (まだ使える文字を小さい順に)? if (T + c にして大丈夫なら) T ← T + c break
C - まだ使える文字を小さい順に T を先頭から 1 文字ずつ決めていくが、? その途中で「まだ使える文字」とは何か？ S = “program” で? T = “aro” と最初の 3 文字だけ決まっているとき
C - まだ使える文字を小さい順に T を先頭から 1 文字ずつ決めていくが、? その途中で「まだ使える文字」とは何か？ S = “program” で? T = “aro” と最初の 3 文字だけ決まっているとき p, g, m は T にまだ入ってないので使える
C - まだ使える文字を小さい順に T を先頭から 1 文字ずつ決めていくが、? その途中で「まだ使える文字」とは何か？ S = “program” で? T = “aro” と最初の 3 文字だけ決まっているとき p, g, m は T にまだ入ってないので使える a, o は T に入っているのでもう使えない
C - まだ使える文字を小さい順に T を先頭から 1 文字ずつ決めていくが、? その途中で「まだ使える文字」とは何か？ S = “program” で? T = “aro” と最初の 3 文字だけ決まっているとき p, g, m は T にまだ入ってないので使える a, o は T に入っているのでもう使えない r は S に 2 回出てきており、? T には 1 回しか出てきていないのでまだ使える
C - まだ使える文字を小さい順に T を先頭から 1 文字ずつ決めていくが、? その途中で「まだ使える文字」とは何か？ S = “program” で? T = “aro” と最初の 3 文字だけ決まっているとき p, g, m は T にまだ入ってないので使える a, o は T に入っているのでもう使えない r は S に 2 回出てきており、? T には 1 回しか出てきていないのでまだ使える 4 文字目の候補は p, g, m, r の 4 通り！
C - T + c にして大丈夫？ つまり、T の次の文字を c にしてしまった結果、? このあとどう頑張っても動いた文字の個数が K を? 超えてしまう……、ということにならないだろうか？
C - T + c にして大丈夫？ つまり、T の次の文字を c にしてしまった結果、? このあとどう頑張っても動いた文字の個数が K を? 超えてしまう……、ということにならないだろうか？ ↓ 残りの部分でできるだけ頑張って、? 動いた文字が少なくなるようにしてみる！? その結果動いた文字の個数が K 以下にできれば OK
C - T + c にして大丈夫？ S = “program”、K = 3 で、? T = “aro” と最初の 3 文字だけ決まっているとき? T = “arog” にしても大丈夫か？
C - T + c にして大丈夫？ S = “program”、K = 3 で、? T = “aro” と最初の 3 文字だけ決まっているとき? T = “arog” にしても大丈夫か？ S p r o g r a m T a r o g * * * すでに決まっている部分 （不一致 1 文字） ここを不一致数が? 少なくなるように? 決めたい
C - T + c にして大丈夫？ S = “program”、K = 3 で、? T = “aro” と最初の 3 文字だけ決まっているとき? T = “arog” にしても大丈夫か？ S p r o g r a m T a r o g * * * すでに決まっている部分 （不一致 1 文字） ここを不一致数が? 少なくなるように? 決めたい ここに? 使えるのは? m, p, r
C - T + c にして大丈夫？ S = “program”、K = 3 で、? T = “aro” と最初の 3 文字だけ決まっているとき? T = “arog” にしても大丈夫か？ S p r o g r a m T a r o g * * * すでに決まっている部分 （不一致 1 文字） ここを不一致数が? 少なくなるように? 決めたい m, p, r をうまく? 並び替えて? “ram” との? 不一致数を? 最小にすればよい！
C - 結局のところ 問題? ?同じ長さの文字列 s, t が与えられる。? ?t を並び替えて、s との不一致の数をどれだけ? ?少なくできるか？ これが解ければいい。? 前ページまでの例だと s = “ram”, t = “mpr”
C - 具体例で s = “pipeline”, t = “eppstein” の場合を考える s p i p e l i n e t’ t e p p s t e i n t’ は並び替え後の t を表すとする
C - 直感的には 同じ文字のところに持ってくれば不一致は減りそう s p i p e l i n e t’ p p e i n e t e p p s t e i n
C - 直感的には 残りの文字はどう並び替えても不一致になる s p i p e l i n e t’ p s p e t i n e t e p p s t e i n
C - 実は 今の直感的な方法が最適になる ?t の文字を順に見ていき、? ??s に同じ文字がありそこが空いてれば持っていく? ??なければ後回し? ?残った t の文字を適当な空いた場所に持っていく で OK
C - なぜか？ s に ‘a’ が n 個、t に ‘a’ が m 個あるとする。 このとき、min(n, m) 個の ‘a’ は? 並び替えによって一致させられるが、? 残りの ‘a’ はどうやっても不一致になる。 さっきの直感的な方法では、? min(n, m) 個ぴったり一致させることができる！
C - ということは この問題には意外と? 簡単に答えられる → min(s にある a の数, t にある a の数)? ?+ min(s にある b の数, t にある b の数)? ?+ …? ?+ min(s にある z の数, t にある z の数) が答え！ 同じ長さの文字列 s, t が与えられる。? t を並び替えて、s との不一致の数をどれだけ? 少なくできるか？
C - お疲れ様でした 以上で、はじめの擬似コードでごまかした部分を? きちんとプログラムで計算できるようになった。 これで C 問題が解ける。 N の値を小さめにしてあるので、多少の実装方針の差 異で計算量が違っても時間には余裕があると思います。
D問題 漸化式
D - 問題概要 問題? 整数列 A は最初の K 項が与えられ、? それ以降の項は与えられた漸化式で決まる。? A の M 項目の値を求めよ。 制限? 1 ≦ K ≦ 100? 1 ≦ M ≦ 1,000,000,000 (=109)
D - 漸化式 そもそも漸化式とは？? ?数列の各項の値が、それ以前の項の値によって? ?決められるとき、その決め方を表す等式 例: フィボナッチ数列 Fn+2 = Fn+1 + Fn F0 = 0 F1 = 1 漸化式 初期値
D - 漸化式の計算 漸化式はそのまま簡単にプログラムにできる? （フィボナッチ数列の例） # 初期値を入れる F[0] ← 0 F[1] ← 1 ! # 漸化式に従って前から順に計算 for k = 2 to N F[k] ← F[k-1] + F[k-2]
D - 漸化式の計算 漸化式はそのまま簡単にプログラムにできる? （フィボナッチ数列の例） # 初期値を入れる F[0] ← 0 F[1] ← 1 ! # 漸化式に従って前から順に計算 for k = 2 to N F[k] ← F[k-1] + F[k-2] N 項目を計算するには? 漸化式に従った計算を ? N 回ぐらいしないといけない
D - 今回の場合 漸化式 AN+K = (C1 AND AN+K 1) XOR · · · XOR (CK AND AN )
D - 今回の場合 漸化式 ! 長いので、AND と XOR をこう書き換えます↓ AN+K = (C1 AND AN+K 1) XOR · · · XOR (CK AND AN ) AN+K = (C1 · AN+K 1) · · · (CK · AN )
D - 今回の場合 漸化式? 漸化式に従って次の項を計算するときに? AND や XOR を K 回ぐらい計算する必要がある AN+K = (C1 · AN+K 1) · · · (CK · AN )
D - 今回の場合 漸化式? 漸化式に従って次の項を計算するときに? AND や XOR を K 回ぐらい計算する必要がある つまり、M 項目を計算するためには? M × K (≦ 1011) 回ぐらいの計算が必要になる！? とてもじゃないけど 2 秒では…… AN+K = (C1 · AN+K 1) · · · (CK · AN )
D - 高速な漸化式の計算 高速に M 項目を求めるために……
D - 高速な漸化式の計算 高速に M 項目を求めるために…… ! ? が使えます！ 行列 ? 1 2 3 4 ◆ 0 @ 1 0 3 4 1 5 2 2 1 1 A ←こういうやつ
D - 行列について 今回使うのは? ?行列とベクトルの積? ?行列と行列の積? です。 行列?積 ここで頑張って説明するよりも、? ネットにたくさんある分かりやすい解説を? 見たほうがよいと思うので……
D - 高速な漸化式の計算 フィボナッチ数列を例にして考えます ! ! フィボナッチ数列は Fn と Fn+1 の? 2 個だけわかっていれば、Fn+2 の値もわかる！ Fn+2 = Fn+1 + Fn F0 = 0 F1 = 1
D - 高速な漸化式の計算 はじめは F0, F1 の値を知っている?
D - 高速な漸化式の計算 はじめは F0, F1 の値を知っている? → F2 が計算できるので、F1, F2 の値がわかる?
D - 高速な漸化式の計算 はじめは F0, F1 の値を知っている? → F2 が計算できるので、F1, F2 の値がわかる? → F3 が計算できるので、F2, F3 の値がわかる?
D - 高速な漸化式の計算 はじめは F0, F1 の値を知っている? → F2 が計算できるので、F1, F2 の値がわかる? → F3 が計算できるので、F2, F3 の値がわかる? → F4 が……
D - 高速な漸化式の計算 はじめは F0, F1 の値を知っている? → F2 が計算できるので、F1, F2 の値がわかる? → F3 が計算できるので、F2, F3 の値がわかる? → F4 が…… 漸化式の計算を 2 個まとまりで考えよう ? F1 F0 ◆ ? F2 F1 ◆ ? F3 F2 ◆ ? F4 F3 ◆ ……
D - 高速な漸化式の計算 ! この矢印は結局何をしているのか？ ? Fn+1 Fn ◆ ? Fn+2 Fn+1 ◆
D - 高速な漸化式の計算 ! この矢印は結局何をしているのか？ ? 実は、行列を掛けている！ ? 1 1 1 0 ◆ ? Fn+1 Fn ◆ = ? Fn+1 + Fn Fn+1 ◆ = ? Fn+2 Fn+1 ◆ ? Fn+1 Fn ◆ ? Fn+2 Fn+1 ◆
D - 高速な漸化式の計算 ! この行列を 1 回かけると、添字が 1 つ進む ? 1 1 1 0 ◆
D - 高速な漸化式の計算 ! この行列を 1 回かけると、添字が 1 つ進む なら、n 回かけると、添字が n 進む！！ ? 1 1 1 0 ◆ ? Fn+1 Fn ◆ = ? 1 1 1 0 ◆ ? 1 1 1 0 ◆ · · · ? 1 1 1 0 ◆ ? F1 F0 ◆ n 個
D - 高速な漸化式の計算 Fn を求めるためには ! を計算すればいい（行列の累乗）ことが分かった 普通だと行列の掛け算を n 回しないといけない? ?＝全然早くなってない！ ? 1 1 1 0 ◆n
D - 高速な累乗の計算 ある行列 A の n 乗を求めたいとする? （例として n = 100 の場合を考える） A100
D - 高速な累乗の計算 100 を 2 進数で表すと 1100100 になる ! ! ? つまり 100 = 64 + 32 + 4 と書ける A100 100 = = 64 32 16 8 4 2 1
D - 高速な累乗の計算 ????????と同じように分解できる！ ! ! ? A の (2 の累乗) 乗が求められればよさそう A100 100 = = 64 32 16 8 4 2 1 A100 = A64 A32 A4 A64 A32 A16 A8 A2 A1 A4
D - 高速な累乗の計算 これは A を次々に 2 乗していけば計算できる ! ! ? A を 2 乗していきながら、n のビットが立っている? 場所のものだけを掛け算していけばいい！ A100 100 = = 64 32 16 8 4 2 1 A64 A32 A16 A8 A2 A1 A4 2乗2乗2乗2乗2乗2乗
D - 高速な累乗の計算 ! ! ! ? 必要な行列の掛け算の回数は、? n を 2 進数で表したときの桁数 = O(log n) A100 100 = = 64 32 16 8 4 2 1 A64 A32 A16 A8 A2 A1 A4 2乗2乗2乗2乗2乗2乗
D - ようやく解き方 O(log n) 回の行列の掛け算で漸化式の? n 項目が計算できるようになった！? これを使えば D 問題が解けるのでは？
D - ようやく解き方 O(log n) 回の行列の掛け算で漸化式の? n 項目が計算できるようになった！? これを使えば D 問題が解けるのでは？ ん？ちょっと待てよ……
D - ようやく解き方 今回の漸化式 ? 行列の累乗では、? 掛け算や足し算で表される漸化式が対象だった → AND や XOR はどうすればいいのか？？？ AN+K = (C1 · AN+K 1) · · · (CK · AN )
D - ようやく解き方 今回の漸化式 ? 行列の累乗では、? 掛け算や足し算で表される漸化式が対象だった → AND や XOR はどうすればいいのか？？？ AN+K = (C1 · AN+K 1) · · · (CK · AN ) 実は大丈夫！行列累乗が使える！！
D - ようやく解き方 ?AND を掛け算のようなもの? ?XOR を足し算のようなもの と思って行列の累乗を計算すればいい！? （つまり、普通の行列の計算をするときの + を XOR に置き換えて、× を AND に置き換える）
D - ようやく解き方 ?AND を掛け算のようなもの? ?XOR を足し算のようなもの と思って行列の累乗を計算すればいい！? （つまり、普通の行列の計算をするときの + を AND に置き換えて、× を XOR に置き換える） なんでそんなことをしても大丈夫なの？? 「掛け算のようなもの」ってどういうこと？
D - 行列積?累乗に必要なこと 行列の要素は必ずしも? ??普通の数? ??普通の足し算? ??普通の掛け算? である必要はない！ とはいえ、足し算や掛け算のかわりに? 何でも好きな演算をいれていいわけでもない。? 足し算と掛け算っぽいものじゃないとダメ
D - 行列積?累乗に必要なこと 足し算と掛け算っぽさとは……？ ?足し算ならこれが成り立ってほしいよね? ?掛け算ならこれが成り立ってほしいよね という性質。 今からその性質を挙げますが、結構数が多いので? 覚えるというよりは「こういう感じなのかー」と? 理解してもらえればいいと思います。
D - 行列積?累乗に必要なこと 以下の性質を満たしていれば行列積ができる！ a + (b + c) = (a + b) + c a + 0 = 0 + a = a a + b = b + a a ? (b ? c) = (a ? b) ? c a ? 1 = 1 ? a = 1 a ? (b + c) = (a ? b) + (a ? c) (a + b) ? c = (a ? c) + (b ? c) a ? 0 = 0 ? a = 0
D - 行列積?累乗に必要なこと 以下の性質を満たしていれば行列積ができる！ a + (b + c) = (a + b) + c a + 0 = 0 + a = a a + b = b + a a ? (b ? c) = (a ? b) ? c a ? 1 = 1 ? a = 1 a ? (b + c) = (a ? b) + (a ? c) (a + b) ? c = (a ? c) + (b ? c) a ? 0 = 0 ? a = 0 足し算は好きな順に? 計算してもいい
D - 行列積?累乗に必要なこと 以下の性質を満たしていれば行列積ができる！ a + (b + c) = (a + b) + c a + 0 = 0 + a = a a + b = b + a a ? (b ? c) = (a ? b) ? c a ? 1 = 1 ? a = 1 a ? (b + c) = (a ? b) + (a ? c) (a + b) ? c = (a ? c) + (b ? c) a ? 0 = 0 ? a = 0 足し算しても変わらない ような値(0)が存在する
D - 行列積?累乗に必要なこと 以下の性質を満たしていれば行列積ができる！ a + (b + c) = (a + b) + c a + 0 = 0 + a = a a + b = b + a a ? (b ? c) = (a ? b) ? c a ? 1 = 1 ? a = 1 a ? (b + c) = (a ? b) + (a ? c) (a + b) ? c = (a ? c) + (b ? c) a ? 0 = 0 ? a = 0 足し算は左右を? 入れ替えても結果が同じ
D - 行列積?累乗に必要なこと 以下の性質を満たしていれば行列積ができる！ a + (b + c) = (a + b) + c a + 0 = 0 + a = a a + b = b + a a ? (b ? c) = (a ? b) ? c a ? 1 = 1 ? a = 1 a ? (b + c) = (a ? b) + (a ? c) (a + b) ? c = (a ? c) + (b ? c) a ? 0 = 0 ? a = 0 掛け算は好きな順に? 計算してもいい
D - 行列積?累乗に必要なこと 以下の性質を満たしていれば行列積ができる！ a + (b + c) = (a + b) + c a + 0 = 0 + a = a a + b = b + a a ? (b ? c) = (a ? b) ? c a ? 1 = 1 ? a = 1 a ? (b + c) = (a ? b) + (a ? c) (a + b) ? c = (a ? c) + (b ? c) a ? 0 = 0 ? a = 0 掛け算しても変わらない? ような値(1)がある
D - 行列積?累乗に必要なこと 以下の性質を満たしていれば行列積ができる！ a + (b + c) = (a + b) + c a + 0 = 0 + a = a a + b = b + a a ? (b ? c) = (a ? b) ? c a ? 1 = 1 ? a = 1 a ? (b + c) = (a ? b) + (a ? c) (a + b) ? c = (a ? c) + (b ? c) a ? 0 = 0 ? a = 0 足し算と掛け算の間に? 分配法則がなりたつ
D - 行列積?累乗に必要なこと 以下の性質を満たしていれば行列積ができる！ a + (b + c) = (a + b) + c a + 0 = 0 + a = a a + b = b + a a ? (b ? c) = (a ? b) ? c a ? 1 = 1 ? a = 1 a ? (b + c) = (a ? b) + (a ? c) (a + b) ? c = (a ? c) + (b ? c) a ? 0 = 0 ? a = 0 足し算しても変わらない? ような値(0)と掛け算すると? 0になる
D - 半環 いま挙げた性質を満たすものを半環といいます。 足し算を XOR、掛け算を AND だと思っても? いま挙げた性質が全部成り立つことが確かめられる！? →行列の累乗で漸化式の計算ができる！！ 実際に性質を満たすことを確かめるのは省略しますが、余裕があればトライして みてください。? また、今回のように非負整数に対して「足し算を XOR」「掛け算を AND」とす れば性質を満たすことを「非負整数は XOR と AND に関して半環をなす」と 言ったりします。
D - 解き方に戻りまして XOR, AND からなる漸化式でも行列累乗が? 使えることが無事に確認できた！ あとは、今回の漸化式を進めるような行列を? 実際に作って累乗すればいい！
D - 行列の構成 こういう行列になります 0 B B B B B @ C1 C2 · · · CK 1 CK 1 0 · · · 0 0 0 1 · · · 0 0 ... ... ... ... ... 0 0 · · · 1 0 1 C C C C C A
D - 行列のイメージ 1 行目は、掛け算したときに漸化式が出てくるように 0 B B B B B @ AN+K 1 AN+K 2 AN+K 3 ... AN 1 C C C C C A 0 B B B B B @ C1 C2 · · · CK 1 CK 1 0 · · · 0 0 0 1 · · · 0 0 ... ... ... ... ... 0 0 · · · 1 0 1 C C C C C A ? → 掛け算の結果、漸化式が出てくる? → 結果の 1 個目が AN+K になる
D - 行列のイメージ 2 行目以降は、項をずらしていくイメージ 0 B B B B B @ AN+K 1 AN+K 2 AN+K 3 ... AN 1 C C C C C A 0 B B B B B @ C1 C2 · · · CK 1 CK 1 0 · · · 0 0 0 1 · · · 0 0 ... ... ... ... ... 0 0 · · · 1 0 1 C C C C C A ? たとえば、2 行目に注目すると? 掛け算の結果 2 個目には AN+K-1 が出てくる
D - まとめ ?漸化式は行列の累乗を使って早く進められる? ?足し算、掛け算のかわりに XOR, AND を使う 先ほどの行列を M-1 乗して A1 から AK までが入った? 初期値のベクトルに掛け算すると AM が求まる！ 行列の掛け算は定義通りに計算して O(K3) なので、? 全体での計算量は O(K3 log M) になる。
D - 注意 どんな漸化式でも行列累乗が使えるわけではない！ ? 以前の項どうしの間で掛け算があったりするとダメ ? こういう (定数) (以前の項) の足し算の形ならOK? ただし、足し算や掛け算が普通のものじゃなくても? 半環なら OK というのが今回のポイントだった Xn+2 = Xn+1 ? X2 n Xn+2 = aXn+1 + bXn

More Related Content

AtCoder Beginner Contest 009 解説