![別解
? まず?と?の最大公約数gcd(?, ?)をユークリッドの互除法で求める．
? そして?と?の最小公倍数lcm ?, ? =
a?
gcd(?,?)
を求めてから，
lcm ?, ? ?
?
lcm ?, ?
を切り上げたもの
? を計算するとそれが答え．
? この方法だとn,a,bが大きくても解けるが今回は必要ない．
5
[余談]
一般に
?
?
の切り上げは，
?+??1
?
を整数で計算すると求まる](https://image.slidesharecdn.com/random-160109140206/85/abc032-5-320.jpg)
![考察
[数列に1つでも0という値が含まれているケース]
? 答えはN
[それ以外のケース]
? ありうる部分列の左端を全通り試すことを考える．
? その上で右端を全通り試していたら間に合わなさそう…?
? 右端を少しずつ伸ばし要素の積がKを超えた時点で打ち切れば良い?
? 全ての要素が2以上だったら右端の候補としてありうるのはlog2 ?通りくらい
? なぜなら1つ要素が増えるごとに2倍以上になっていき，すぐKを超えるから
? しかし，連続した1があると右端の候補数がO(N)になってしまう．
? 連続した1を圧縮すれば良さそう！
12](https://image.slidesharecdn.com/random-160109140206/85/abc032-12-320.jpg)
![考察＆解法 (B)荷物の価値が1000以下
? ? ??? = 1000とおくと，価値の総和は高々 ? ? ? ???(= 20万) 以下．
? 価値に対して重みを最小化するDPができる．
? ??[?][?] ∶= ?番目のアイテム(? = 1. . ?)まで使って，価値の和jを達成す
る重みの和の最小値
と定義すると，以下の漸化式を計算すれば解ける
? ??[0][0] = 0, ??[0][1. . ?? ???] = ∞
? ??[?][?] = min(??[? ? 1][?], ??[? ? 1][? ? ??] + ??(但し? ? ?? ≧ 0の時) )
? この漸化式を? = 0. . ?に対して計算した後，重みの和が ? 以下となる
最大の価値をテーブルを参照して求めれば良い．
41](https://image.slidesharecdn.com/random-160109140206/85/abc032-41-320.jpg)
![考察＆解法 (B)荷物の価値が1000以下
? 実は，価値の逆順に更新ループを行うと，テーブルのサイズが
?(?? ???)で済み，添字iについて考慮しなくてよくなる．実装も軽い．
? 時間計算量は ?(?2
? ???) 空間計算量は ? ?? ???
配列??[0. . ?][0. . ?? ???]を用意
??? ? = 1. . ?? ???
?? 0 ? = ∞
??[0][0] = 0
??? ? = 1. . ?
??? ? = 0 . . (?? ? 1)
??[?][?] = ??[? ? 1][?];
??? ? = ?? . . ?? ???
??[?][?] = min(??[? ? 1][?], ??[? ? 1][? ? ??] + ??)
配列??[0. . ?? ???]を用意
??? ? = 1. . ?? ???
??[?] = ∞
??[0] = 0
??? ? = 1. . ?
??? ? = ?? ??? . . ?? (※逆順)
??[?] = min(??[?], ??[? ? ??] + ??)
省メモリ
実装が楽
42](https://image.slidesharecdn.com/random-160109140206/85/abc032-42-320.jpg)
![考察＆解法 (C)荷物の重みが1000以下
? これが一番お馴染みかも知れない．
? ? ??? = 1000とおくと，重みの総和は高々 ? ? ? ???(= 20万) 以下．
? 重みに対して価値を最大化するDPができる．
? ??[?][?] ∶= ?番目のアイテム(? = 1. . ?)まで使って，重みの和jを達成す
る価値の和の最大値
と定義すると，以下の漸化式を二重ループで計算すれば解ける
? ?? 0 0 = 0, ?? 0 1. . ?? ??? = ?∞
? ??[?][?] = m??(??[? ? 1][?], ??[? ? 1][? ? ??] + ??(但し? ? ?? ≧ 0の時) )
? 後は重みW以下で価値が最大のものを求めれば良い．
? さっきのスライドで説明した価値のDPとやり方はほぼ同じ
43](https://image.slidesharecdn.com/random-160109140206/85/abc032-43-320.jpg)
abc032
- 3. 問題概要 ? 整数 ?, ?, ?(1 ≦ ?, ? ≦ 100, ? ≦ 20000) が与えられる． ? aとbの公倍数で，n以上で最小のものを求めよ． ? 例) a=2,b=3,n=8 → 12 (n以上で最小の，2と3の公倍数は12) 3
- 4. 解法 ? 与えられたnを，aとbの両方で割り切れるようになるまで愚直にイン クリメントして，割り切れたらそれを出力． ? 高々a*b-1回インクリメントすればそのような数は見つかるので， 時間計算量は O(ab) で間に合う． 4
- 5. 別解 ? まず?と?の最大公約数gcd(?, ?)をユークリッドの互除法で求める． ? そして?と?の最小公倍数lcm ?, ? = a? gcd(?,?) を求めてから， lcm ?, ? ? ? lcm ?, ? を切り上げたもの ? を計算するとそれが答え． ? この方法だとn,a,bが大きくても解けるが今回は必要ない． 5 [余談] 一般に ? ? の切り上げは， ?+??1 ? を整数で計算すると求まる
- 7. 問題概要 ? 文字列sに含まれる長さkの部分文字列で相異なるものの数を数えよ． ? 1≦|s|,k≦300 ? 例) s=“abcabc”,k=2→ 答え3 (∵ {”ab”,”bc”,”ca”}の3通りがありうる) 7
- 8. 解法 ? 存在する長さkの部分文字列をすべて列挙したリストを作ってから， 重複を取り除き，その個数を出力する． ? 重複を取り除く方法はいろいろあるが，多くの言語に存在するset型など の集合型を用いると，簡単に重複を取り除くことができる． ? 計算量は集合型の実装方法に依存する． ? 平衡二分木による実装の場合 ?( ? 2 log |?|) ? 平衡二分木による実装の場合 ? ? 2 ※文字列比較のオーダーはO(|?|)なことに注意 ? 集合型を用わず，列挙したリストに対して二重ループで愚直に重複除去 を行っても，?( ? 3 )程度の計算量で解ける． 8
- 9. C – 列 9
- 10. C - 列 ? 長さNの非負整数列? = ?1, ?2, … , ? ?と整数Kが与えられる． ? Sの連続する部分列??, ??+1, … , ??のうち，条件 ?=? ? ? ? ≤ ? を満たす部分列で最長のものの長さを求めよ． ? 条件を満たす部分列が存在しない時は0を出力 ? 1 ≦ N ≦ 105 , 0 ≦ ??, ? ≦ 109 10
- 11. 例 ? S={4,3,1,1,2,10},K=6 → 答え 4 ? S={10,10,10,10,0,10},K=10 → 答え 6 ? S={10,10,10,10,10,10},K=9 → 答え 0 ? S={1,2,3,4},K=0 → 答え 0
- 12. 考察 [数列に1つでも0という値が含まれているケース] ? 答えはN [それ以外のケース] ? ありうる部分列の左端を全通り試すことを考える． ? その上で右端を全通り試していたら間に合わなさそう…? ? 右端を少しずつ伸ばし要素の積がKを超えた時点で打ち切れば良い? ? 全ての要素が2以上だったら右端の候補としてありうるのはlog2 ?通りくらい ? なぜなら1つ要素が増えるごとに2倍以上になっていき，すぐKを超えるから ? しかし，連続した1があると右端の候補数がO(N)になってしまう． ? 連続した1を圧縮すれば良さそう！ 12
- 13. 考察 - 連続した1を圧縮する ? 圧縮例 S = {2,3,3,1,1,1,1,2,1,1,1} → {2,3,3,(1が4コ),2,(1が3コ)} ? このようにすると，右端を少しずつ伸ばしていく際，連続した1の部分 は一気に伸ばすことができる． ? 最悪ケースはS={1,2,1,2,1,2,1…}というふうなケースだが， しかしこの場合でも各左端から高々 2 log2 ? コ程度しか候補が無い． 13
- 14. 解法 ? 数列を圧縮する ? 圧縮後の数列に対し，全左端から要素の積がKを超えない範囲で右 端を少しずつ伸ばしていくという方法で全通り試す． ? 時間計算量 O(N log K) ? しかしもっと汎用的で計算量も少ない解法がある 14
- 15. 別解① – 尺取法 ? この問題は尺取法で解くことができる． ? 尺取法とは一次元配列に対して，左端と右端の2つのインデックスを持って片方を 進めたりして解を求める手法． ? 以下のように尺取法を行うと，”全体で”O(N)の時間計算量で解ける． 1. 今の左端(初期は1番目)に対して，要素の積がK以下の間，出来るだけ右端を伸 ばす． 2. 今の区間の長さが解より大きければ解を更新 3. 伸ばせなくなったら1つ左端を右に動かす(=縮める)．ただし左端を動かせないな ら終了． 4. 1に戻る ? 左端が右端を追い越さないように注意して実装すること． ? 実装は開区間で持つのが良いと思われる 15
- 32. 別解② – logを取って和の問題に帰着 ? 入力の対数を取ると，和の問題に帰着できるので，累積和と二分探 索を用いて解ける． ? ただし，誤差に気をつける必要がある． ? 詳細は省略 32
- 33. D –ナップサック問題 33
- 34. 問題概要 ? 以下のような0/1ナップサック問題を解いてください． ? N個の荷物があって，それぞれの荷物には価値と重さが割り当てられている． ? 重さの総和がW以下となるように荷物を選ぶとき，価値を最大化してください． ? ただし， A) Nが30以下のケース B) 全ての荷物の価値が1000以下のケース C) 全ての荷物の重みが1000以下のケース ? の少なくともの1つが成り立つケースしかデータセットに存在しない． ? 1 ≦ ? ≦ 200 ? 1 ≦ 荷物の価値??, 荷物の重み?? ≦ 109 ? 1 ≦ ? ≦ 109 34
- 35. はじめに ? ナップサック問題は，動的計画法(DP)を用いる例題としてとても有名 ? 聞いたことがない人は，本やインターネットに図解が溢れかえっているので 是非調べてみましょう ? 今回は文章だけです． ? ナップサック問題は， ? 重さの和や価値の和に関して上限がないとき →NP困難問題として有名で，多項式時間では解けない ? 重さの和や価値の和に制約があるとき →計算量がそれらの値に依存する擬多項式時間アルゴリズムがある (よくあるDPのことです) 35
- 36. 考察 ? 各データセット毎に場合分けして解く他ない． A) Nが30以下のケース → DPは困難∧愚直な全列挙は難しい(枝刈り探索なら通るかも..?) B) 全ての荷物の価値が1000以下のケース → DPできる C)全ての荷物の重みが1000以下のケース →DPできる ? それぞれについて考える 36
- 37. 考察＆解法 (A) Nが30以下のケース ? 価値?重みに制約が無いため動的計画法は困難 ? ?(2 ?)で全列挙は間に合わなさそう． ? 与えられた荷物の集合を半分ずつの集合A,Bに分けて，それぞれの 集合で組み合わせを全列挙し，それらの結果をうまくマージすると， ?(2 ? 2 ? log ?)程度の計算量で解ける(? = 2 ? 2 とする)． ? そのために，まず集合Aに対して，重さの和?以下で達成できる最大価値を ?(log ?)程度で求めれるようにしておく必要がある． ? S通りある(重みの和,価値の和)のペアを辞書順ソートして，重みに対して価 値が単調増加するようにリストを作っておけば二分探索できる． ? その後，集合Bのある組み合わせを試して，その組み合わせを使った後余る 重みを集合Aに割り振る．この時達成できる最大価値を先ほどのリストに対 する二分探索等で高速に求める． 37
- 38. アルゴリズムの流れ (A) Nが30以下のケース ① 荷物を2つの集合に分ける (?1 = 5, ?1 = 2) (?2 = 4, ?2 = 3) (?3 = 1, ?3 = 1) (?4 = 2, ?4 = 2) (?1 = 5, ?1 = 2) (?2 = 4, ?2 = 3) (?3 = 1, ?3 = 1) (?4 = 2, ?4 = 2) A B 全体 38
- 39. アルゴリズムの流れ (A) Nが30以下のケース ② Aの全組み合わせを計算してリストを作り，明らかに損するもの(そ れ未満の重みで，それ以上の価値を達成するものがある組み合わ せ)を取り除く． (?1 = 5, ?1 = 2) (?2 = 4, ?2 = 3) A (v=0,w=0) (v=5,w=2) (v=4,w=3) (v=9,w=5) 重みでソート済みのリスト この例では 全4通り計算 (v=0,w=0) (v=5,w=2) (v=9,w=5) 要らないものを削除 得られたリスト 39
- 40. アルゴリズムの流れ (A) Nが30以下のケース ③ Bの全組み合わせに対して，先ほど計算したリストのどの要素と くっつければ良いかを，重みに対する二分探索で計算し，マージする 例)ナップサックのサイズが5の場合を考えると以下のようになる (v=0,w=0) (v=1,w=1) (v=2,w=2) (v=3,w=3) この例では 全4通り計算 (v=0,w=0) (v=5,w=2) (v=9,w=5) (?3 = 1, ?3 = 1) (?4 = 2, ?4 = 2) B 集合Aから得たリスト 40
- 41. 考察＆解法 (B)荷物の価値が1000以下 ? ? ??? = 1000とおくと，価値の総和は高々 ? ? ? ???(= 20万) 以下． ? 価値に対して重みを最小化するDPができる． ? ??[?][?] ∶= ?番目のアイテム(? = 1. . ?)まで使って，価値の和jを達成す る重みの和の最小値 と定義すると，以下の漸化式を計算すれば解ける ? ??[0][0] = 0, ??[0][1. . ?? ???] = ∞ ? ??[?][?] = min(??[? ? 1][?], ??[? ? 1][? ? ??] + ??(但し? ? ?? ≧ 0の時) ) ? この漸化式を? = 0. . ?に対して計算した後，重みの和が ? 以下となる 最大の価値をテーブルを参照して求めれば良い． 41
- 42. 考察＆解法 (B)荷物の価値が1000以下 ? 実は，価値の逆順に更新ループを行うと，テーブルのサイズが ?(?? ???)で済み，添字iについて考慮しなくてよくなる．実装も軽い． ? 時間計算量は ?(?2 ? ???) 空間計算量は ? ?? ??? 配列??[0. . ?][0. . ?? ???]を用意 ??? ? = 1. . ?? ??? ?? 0 ? = ∞ ??[0][0] = 0 ??? ? = 1. . ? ??? ? = 0 . . (?? ? 1) ??[?][?] = ??[? ? 1][?]; ??? ? = ?? . . ?? ??? ??[?][?] = min(??[? ? 1][?], ??[? ? 1][? ? ??] + ??) 配列??[0. . ?? ???]を用意 ??? ? = 1. . ?? ??? ??[?] = ∞ ??[0] = 0 ??? ? = 1. . ? ??? ? = ?? ??? . . ?? (※逆順) ??[?] = min(??[?], ??[? ? ??] + ??) 省メモリ 実装が楽 42
- 43. 考察＆解法 (C)荷物の重みが1000以下 ? これが一番お馴染みかも知れない． ? ? ??? = 1000とおくと，重みの総和は高々 ? ? ? ???(= 20万) 以下． ? 重みに対して価値を最大化するDPができる． ? ??[?][?] ∶= ?番目のアイテム(? = 1. . ?)まで使って，重みの和jを達成す る価値の和の最大値 と定義すると，以下の漸化式を二重ループで計算すれば解ける ? ?? 0 0 = 0, ?? 0 1. . ?? ??? = ?∞ ? ??[?][?] = m??(??[? ? 1][?], ??[? ? 1][? ? ??] + ??(但し? ? ?? ≧ 0の時) ) ? 後は重みW以下で価値が最大のものを求めれば良い． ? さっきのスライドで説明した価値のDPとやり方はほぼ同じ 43
- 44. 考察＆解法 (C)荷物の重みが1000以下 ? これも重みの逆順に更新すれば， 時間計算量は ?(?2 ? ???) 空間計算量は ? ?? ??? 44