文字列 DP (応用編) - 文字列を華麗に扱おう

スライド内のリンクを見たい方はこちら：https://hcpc-hokudai.github.io/archive/dynamic_programming_string_dp.pdf

Transcript

1. จࣈྻ DP (Ԡ༻ฤ) จࣈྻΛ՚ྷʹѻ͓͏ tsutaj (@tsutaj) Hokkaido University M1 July 27, 2018 tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 1 / 36
2. 1 LCSɾฤूڑ཭ͷྨ୊ ManageSubsequences YahooYahooYahoo 2 ېࢭจࣈྻ ېࢭจࣈྻ (୯Ұ ver.) ېࢭจࣈྻ (ෳ਺ ver.) Genetic engineering 3 ࿅श໰୊ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 2 / 36
3. ManageSubsequences ManageSubsequences จࣈྻ S, A, B ͕༩͑ΒΕΔɻS ʹରͯ͠ɺ(࿈ଓͱ͸ݶΒͳ͍) ෦෼ྻͱ ͯ͠ A ΛؚΉ͕ B Λؚ·ͳ͍Α͏ʹɺ͍͔ͭ͘จࣈΛૠೖ͍ͨ͠ɻ͜ͷ ৚݅Λຬͨ͢จࣈૠೖݸ਺ͷ࠷খ஋ΛٻΊΑɻෆՄೳͳ৔߹͸ -1 Λग़ྗ ͤΑɻ 1 ≤ |S|, |A|, |B| ≤ 300 ग़య: TopCoder SRM 727 Div2 Hard Link αϯϓϧ ೖྗ 1 : JT1 ग़ྗ: JT1 ೖྗ 2 : JT1 ग़ྗ: JT1 tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 3 / 36
4. ManageSubsequences ͍ͬͨΜ B ͷ͜ͱΛແࢹ͢Δ S தʹ෦෼ྻͱͯ͠ A ΛؚΉͨΊͷɺ࠷খͷจࣈૠೖݸ਺͸ʁ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 4 / 36
5. ManageSubsequences ͍ͬͨΜ B ͷ͜ͱΛແࢹ͢Δ S தʹ෦෼ྻͱͯ͠ A ΛؚΉͨΊͷɺ࠷খͷจࣈૠೖݸ਺͸ʁ ͜Ε͸ LCS ͱ΄΅ಉ͡ߟ͑Ͱղ͚Δ dp[i][j] := S ͷ i จࣈ໨·ͰΛ࢖ͬͯɺA ͷ j จࣈ໨·ͰΛؚΉΑ͏ ʹ͢ΔͨΊʹඞཁͳจࣈૠೖݸ਺ͷ࠷খ ભҠ͸࣍ͷ 2 ௨Γ 1 S ͷ࣍ͷจࣈΛී௨ʹೖΕΔ 2 A ͷ j จࣈ໨ʹ૬౰͢ΔจࣈΛೖΕΔ ܭࢉྔ O(|S||A|) ͜Εʹ B ͕ՃΘΔͱͲ͏ͳΔ͔ʁ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 4 / 36
6. ManageSubsequences ͍ͬͨΜ B ͷ͜ͱΛແࢹ͢Δ S தʹ෦෼ྻͱͯ͠ A ΛؚΉͨΊͷɺ࠷খͷจࣈૠೖݸ਺͸ʁ ͜Ε͸ LCS ͱ΄΅ಉ͡ߟ͑Ͱղ͚Δ dp[i][j] := S ͷ i จࣈ໨·ͰΛ࢖ͬͯɺA ͷ j จࣈ໨·ͰΛؚΉΑ͏ ʹ͢ΔͨΊʹඞཁͳจࣈૠೖݸ਺ͷ࠷খ ભҠ͸࣍ͷ 2 ௨Γ 1 S ͷ࣍ͷจࣈΛී௨ʹೖΕΔ 2 A ͷ j จࣈ໨ʹ૬౰͢ΔจࣈΛೖΕΔ ܭࢉྔ O(|S||A|) ͜Εʹ B ͕ՃΘΔͱͲ͏ͳΔ͔ʁ A ΛؚΉ͕ B ͸ؚ·ͳ͍ ˠ B ͱ࠷ޙ·ͰҰக͢ΔલʹɺS ͱ A ʹ ͍ͭͯ࠷ޙ·ͰҰக ্ͷ DP ͷ࣍ݩΛ૿΍͠ɺҎԼͷΑ͏ʹղ͚͹Α͍ʂ dp[i][j][k] := S ͷ i จࣈ໨·ͰΛ࢖ͬͯɺA ͷ j จࣈ໨·ͰɺB ͷ k จࣈ໨·ͰΛؚΉΑ͏ʹ͢ΔͨΊʹඞཁͳจࣈૠೖݸ਺ͷ࠷খ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 4 / 36
7. ManageSubsequences ࣮૷ (B Λແࢹ͠ɺS ʹ A Λؚ·ͤΔ DP) tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 5 / 36
8. ManageSubsequences ࣮૷ (ݩʑͷ໰୊ͷ DP) tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 6 / 36
9. YahooYahooYahoo YahooYahooYahoo จࣈྻ S ͕༩͑ΒΕΔɻS ͱɺ ʮyahoo Λ 0 ճҎ্܁Γ͔͑ͯ͠Ͱ͖ͨ จࣈྻʯͱͷฤूڑ཭ͷதͰ࠷খͷ΋ͷΛٻΊΑɻ 1 ≤ |S| ≤ 105 ग़య: ʮΈΜͳͷϓϩίϯʯຊઓ A Link αϯϓϧ ೖྗ 1 : JT1 ग़ྗ: JT1 ೖྗ 2 : JT1 ग़ྗ: JT1 ೖྗ 3 : JT1 ग़ྗ: JT1 tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 7 / 36
10. YahooYahooYahoo yahoo Λ܁Γฦͯ͠Ͱ͖ͨจࣈྻΛ yahoo จࣈྻ ͱশ͢Δ S ͷઌ಄͔Βɺyahoo จࣈྻͷ j mod 5 จࣈ໨·ͰҰகͤ͞ΔͨΊʹ ίετ͕͍ͭ͘ඞཁ͔ߟ͑Α͏ dp[i][j] := S ͷ i จࣈ໨·ͰΛɺyahoo จࣈྻͷ j mod 5 จࣈ໨·Ͱ Ұகͤ͞ΔͨΊʹඞཁͳίετͷ࠷খ஋ ͱͯ͠ղ͚͹ྑ͍ جຊతʹ͸ී௨ͷฤूڑ཭ DP Θ͔Βͳ͍ਓ͸લճͷ DP εϥΠυΛݟΑ͏ʂ yahoo ͸ 5 จࣈ͔͠ͳ͍ͷͰɺ5 Λఆ਺ͱͯ͠ΈΔͱܭࢉྔ O(|S|) tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 8 / 36
11. YahooYahooYahoo جຊతʹ͸ɺ͜ͷදΛߋ৽͍ͯ͘͜͠ͱΛߟ͑Ε͹ྑ͍ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 9 / 36
12. YahooYahooYahoo ߋ৽࣌ʹࢀর͢Δ৔ॴ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 10 / 36
13. YahooYahooYahoo ͱ͜ΖͰɺී௨ʹߋ৽͢ΔͱҎԼͷΑ͏ͳ໰୊఺͕͋Δ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 11 / 36
14. YahooYahooYahoo DP Λߋ৽͢Δͱ͖͸ɺϧʔϓΛ 2 ճ·Θͦ͏ʂ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 12 / 36
15. YahooYahooYahoo උߟ (2 पͷϧʔϓͰ࠷దੑ͕อূ͞ΕΔ͜ͱͷূ໌) ʮจࣈஔ׵ʯͱʮจࣈ࡟আʯͷಈ࡞ʹؔͯ͠ɺطʹ஋͕֬ఆ͍ͯ͠Δͱ ͜Ζ͔Βঢ়ଶભҠ͕ൃੜ͢ΔͷͰɺ͜ΕΒͷૢ࡞ʹΑΔ࠷దੑ͸อূ ͞Ε͍ͯΔ ҎԼɺ ʮจࣈ௥Ճʯͷ࠷దੑʹ͍ͭͯٞ࿦͠Α͏ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 13 / 36
16. YahooYahooYahoo උߟ (2 पͷϧʔϓͰ࠷దੑ͕อূ͞ΕΔ͜ͱͷূ໌) ʮจࣈஔ׵ʯͱʮจࣈ࡟আʯͷಈ࡞ʹؔͯ͠ɺطʹ஋͕֬ఆ͍ͯ͠Δͱ ͜Ζ͔Βঢ়ଶભҠ͕ൃੜ͢ΔͷͰɺ͜ΕΒͷૢ࡞ʹΑΔ࠷దੑ͸อূ ͞Ε͍ͯΔ ҎԼɺ ʮจࣈ௥Ճʯͷ࠷దੑʹ͍ͭͯٞ࿦͠Α͏ yahoo จࣈྻ ͸ 5 จࣈ 1 पظͳͷͰɺ5 จࣈҎ্ͷจࣈૠೖ͕࠷ద ʹͳΔύλʔϯ͸ଘࡏ͠ͳ͍ʂ Αͬͯɺ0 ʙ 4 จࣈͷૠೖ͕࠷దʹͳΔՄೳੑ͕͋Δ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 13 / 36
17. YahooYahooYahoo උߟ (2 पͷϧʔϓͰ࠷దੑ͕อূ͞ΕΔ͜ͱͷূ໌) ʮจࣈஔ׵ʯͱʮจࣈ࡟আʯͷಈ࡞ʹؔͯ͠ɺطʹ஋͕֬ఆ͍ͯ͠Δͱ ͜Ζ͔Βঢ়ଶભҠ͕ൃੜ͢ΔͷͰɺ͜ΕΒͷૢ࡞ʹΑΔ࠷దੑ͸อূ ͞Ε͍ͯΔ ҎԼɺ ʮจࣈ௥Ճʯͷ࠷దੑʹ͍ͭͯٞ࿦͠Α͏ yahoo จࣈྻ ͸ 5 จࣈ 1 पظͳͷͰɺ5 จࣈҎ্ͷจࣈૠೖ͕࠷ద ʹͳΔύλʔϯ͸ଘࡏ͠ͳ͍ʂ Αͬͯɺ0 ʙ 4 จࣈͷૠೖ͕࠷దʹͳΔՄೳੑ͕͋Δ ঢ়ଶ͸ ...yahoo, ...y, ...ya, ...yah, ...yaho ͷ 5 ௨Γଘࡏ͢Δͷ ͔ͩΒɺ͜ͷ͏ͪͷ͍ͣΕ͔͸ 0 จࣈૠೖ͕࠷దͰ͋Δ͸ͣ ͕ͨͬͯ͠ɺ1 प໨ͷϧʔϓͰ͍ͣΕ͔ͷঢ়ଶʹ͍ͭͯ࠷దੑ͕อূ ͞ΕΔͷͰɺ2 पճ͢͜ͱͰશͯͷঢ়ଶʹ͍ͭͯ࠷దੑ͕อূ͞ΕΔ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 13 / 36
18. YahooYahooYahoo ࣮૷͸ҎԼͷ௨Γ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 14 / 36
19. ༻ޠઆ໌ ېࢭจࣈྻͷղઆͷલʹɺ͍͔ͭ͘༻ޠͷઆ໌ Prex (઀಄ࣙ) จࣈྻͷઌ಄͔Β਺จࣈͱ͖ͬͯͯͰ͖ͨจࣈྻ akemihomura ͷ prex ͷྫ , ak, akem, akemihom, akemihomura ͳͲ ͜ͷεϥΠυͰ͸ɺۭͰ΋ྑ͍͠จࣈྻશମͰ΋ྑ͍ͱ͍ͯ͠·͢ Sux (઀ඌࣙ) จࣈྻͷޙඌ͔Β਺จࣈͱ͖ͬͯͯͰ͖ͨจࣈྻ kanamemadoka ͷ sux ͷྫ , oka, madoka, memadoka, kanamemadoka ͳͲ ͜ͷεϥΠυͰ͸ɺۭͰ΋ྑ͍͠จࣈྻશମͰ΋ྑ͍ͱ͍ͯ͠·͢ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 15 / 36
20. ېࢭจࣈྻ (୯Ұ ver.) ېࢭจࣈྻ (୯Ұ ver.) `A', `G', `C', `T' ͷ 4 छྨͷจࣈͷΈؚ͕·ΕΔจࣈྻΛ DNA จࣈྻͱশ ͢ΔɻK จࣈͷจࣈྻ S ͕༩͑ΒΕΔͷͰɺN จࣈ͔ΒͳΔ DNA จࣈ ྻͰ͋ͬͯ S Λؚ·ͳ͍จࣈྻͷݸ਺ mod10, 009 ΛٻΊΑɻ 1 ≤ K ≤ 102 1 ≤ N ≤ 104 ग़య: ٜຊ P.327 αϯϓϧ ೖྗ : JT1 ग़ྗ: JT1 ৚݅Λຬͨ͢จࣈྻͷྫ: JT1 ৚݅Λຬͨ͞ͳ͍จࣈྻͷྫ: JT1 ԿΛঢ়ଶͱͯ࣋ͭ͠΂͖ʁ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 16 / 36
21. ېࢭจࣈྻ (୯Ұ ver.) ԿΛঢ়ଶͱͯ࣋ͭ͠΂͖ʁ S Λؚ·ͳ͍ ˠ S ͱ N จࣈ໨·ͰҰகͯ͠͸͍͚ͳ͍ ݱࡏͷจࣈྻͷ sux ͕ S ͱͲΕ͚ͩҰக͍ͯ͠Δ͔Θ͔Ε͹ OK tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 17 / 36
22. ېࢭจࣈྻ (୯Ұ ver.) ԿΛঢ়ଶͱͯ࣋ͭ͠΂͖ʁ S Λؚ·ͳ͍ ˠ S ͱ N จࣈ໨·ͰҰகͯ͠͸͍͚ͳ͍ ݱࡏͷจࣈྻͷ sux ͕ S ͱͲΕ͚ͩҰக͍ͯ͠Δ͔Θ͔Ε͹ OK dp[i][j] := ࡞੒͍ͯ͠Δ DNA จࣈྻ͕ i จࣈͰ͋ͬͯɺͦͷ sux ͕ S ͷઌ಄ j จࣈͱҰக͍ͯ͠Δঢ়ଶͷ૯਺ ͱ͢Δ ద౰ʹ΍ΔͱϋϚΔͷͰ஫ҙʂ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 17 / 36
23. ېࢭจࣈྻ (୯Ұ ver.) ԿΛঢ়ଶͱͯ࣋ͭ͠΂͖ʁ S Λؚ·ͳ͍ ˠ S ͱ N จࣈ໨·ͰҰகͯ͠͸͍͚ͳ͍ ݱࡏͷจࣈྻͷ sux ͕ S ͱͲΕ͚ͩҰக͍ͯ͠Δ͔Θ͔Ε͹ OK dp[i][j] := ࡞੒͍ͯ͠Δ DNA จࣈྻ͕ i จࣈͰ͋ͬͯɺͦͷ sux ͕ S ͷઌ಄ j จࣈͱҰக͍ͯ͠Δঢ়ଶͷ૯਺ ͱ͢Δ ద౰ʹ΍ΔͱϋϚΔͷͰ஫ҙʂ S = AGCAGTG ͰɺS ͷ 5 จࣈ໨·ͰҰக (AGCAG) ͢Δ৔߹ ࣍ͷจࣈͱͯ͠ `C' Λ࠾༻ ˠ ͜Ε͸ɺS ͷઌ಄Կจࣈ໨·ͰͱҰகʁ S = AGCAGTG, ࡞ͬͨจࣈྻ = ...AGCAGC ˠ ઌ಄ 3 จࣈ ʮS ͷઌ಄ x จࣈ໨·ͰҰக͍ͯͯ͠ɺͦΕʹจࣈ c Λ຤ඌʹૠೖ͠ ͨ৔߹ʹɺઌ಄Կจࣈ໨·ͰҰக͢Δ͔ʁʯͷ৘ใ͕ඞཁ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 17 / 36
24. ېࢭจࣈྻ (୯Ұ ver.) ҎԼͷલॲཧΛߟ͑Δ next[x][c] := S ͷઌ಄ x จࣈ໨·ͰҰகɺͦΕʹจࣈ c Λ຤ඌʹૠೖ ͨ͠৔߹ʹɺઌ಄Կจࣈ໨·ͰҰக͢Δ͔ʁ O(K3) ͰߏஙՄೳ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 18 / 36
25. ېࢭจࣈྻ (୯Ұ ver.) ͜ͷલॲཧ͕ऴΘΕ͹ɺ͋ͱ͸ૉ௚ͳ DP ʹ dp[i][j] := ࡞੒͍ͯ͠Δ DNA จࣈྻ͕ i จࣈͰ͋ͬͯɺͦͷ sux ͕ S ͷઌ಄ j จࣈͱҰக͍ͯ͠Δঢ়ଶͷ૯਺ dp[i][j] ͷঢ়ଶʹର͠ɺ຤ඌʹจࣈ c Λ௥Ճ͢Δͱ͖ ࣍ͷঢ়ଶʹ͓͍ͯɺS ͷઌ಄ԿจࣈͱҰகʁ ˠ nj = next[j][c] จࣈ nj = Kɺͭ·Γ S શମͱҰகͯ͠͠·͏ͳΒ͹ແࢹ ͦ͏Ͱͳ͍ͳΒ͹ɺdp[i + 1][nj] ʹ dp[i][j] Λ଍ͦ͏ ౴͑ ˠ ∑ K−1 i=0 dp[N][i] શମͰ O(K3 + NK) tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 19 / 36
26. ېࢭจࣈྻ (୯Ұ ver.) ࣮૷͸ҎԼͷ௨Γ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 20 / 36
27. ېࢭจࣈྻ (୯Ұ ver.) ࣮૷͸ҎԼͷ௨Γ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 20 / 36
28. ېࢭจࣈྻ (ෳ਺ ver.) ېࢭจࣈྻ (ෳ਺ ver.) `A', `G', `C', `T' ͷ 4 छྨͷจࣈͷΈؚ͕·ΕΔจࣈྻΛ DNA จࣈྻͱশ ͢ΔɻݩͱͳΔ DNA จࣈྻ S ͱɺېࢭύλʔϯͱͳΔ N ݸͷ DNA จࣈ ྻ P1, · · · , PN ͕༩͑ΒΕΔͷͰɺS தͷจࣈΛগͳ͘ͱ΋͍ͭ͘มߋ͢ Ε͹ېࢭύλʔϯ͕શؚ͘·Εͳ͍จࣈྻʹͰ͖Δ͔ʁ (ෆՄೳ ˠ -1) 1 ≤ |S| ≤ 103 1 ≤ N ≤ 50 1 ≤ |Pi | ≤ 20 ग़య: ٜຊ P.329 αϯϓϧ ೖྗ 1: JT1 ग़ྗ 1: JT1 ೖྗ 2: JT1 ग़ྗ 2: JT1 ೖྗ 3: JT1 ग़ྗ 3: JT1 ԿΛঢ়ଶͱͯ࣋ͭ͠΂͖ʁ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 21 / 36
29. ېࢭจࣈྻ (ෳ਺ ver.) ࣮͸୯Ұ ver. ͱ΄΅ಉ͡ղ๏Ͱղ͚Δʂ S Λલ͔ΒݟͯɺจࣈΛॻ͖׵͍͑ͯ͘͜ͱΛߟ͑Α͏ ୯Ұจࣈྻͷ৔߹͸ɺύλʔϯจࣈྻͷ prex Λঢ়ଶͱ͍ͯ͠ ͕ͨɾɾɾ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 22 / 36
30. ېࢭจࣈྻ (ෳ਺ ver.) ࣮͸୯Ұ ver. ͱ΄΅ಉ͡ղ๏Ͱղ͚Δʂ S Λલ͔ΒݟͯɺจࣈΛॻ͖׵͍͑ͯ͘͜ͱΛߟ͑Α͏ ୯Ұจࣈྻͷ৔߹͸ɺύλʔϯจࣈྻͷ prex Λঢ়ଶͱ͍ͯ͠ ͕ͨɾɾɾ ෳ਺จࣈྻͰ͋Ε͹ɺ֤จࣈྻͷ prex Λྻڍͯ͠ɺͦΕΒΛ͢΂ͯঢ় ଶͱ͠Α͏ʂ P = {AAA, AAG, T, TCA, TG} ͷ৔߹ɺ͋ΓಘΔঢ়ଶ͸ A, AA, AAA, AAG, T, TC, TCA, TG ͜ͷঢ়ଶؒͷભҠ͕೺ѲͰ͖Ε͹ɺઌ΄Ͳͱಉ༷ʹղ͚Δʂ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 22 / 36
31. ېࢭจࣈྻ (ෳ਺ ver.) ࣮͸୯Ұ ver. ͱ΄΅ಉ͡ղ๏Ͱղ͚Δʂ S Λલ͔ΒݟͯɺจࣈΛॻ͖׵͍͑ͯ͘͜ͱΛߟ͑Α͏ ୯Ұจࣈྻͷ৔߹͸ɺύλʔϯจࣈྻͷ prex Λঢ়ଶͱ͍ͯ͠ ͕ͨɾɾɾ ෳ਺จࣈྻͰ͋Ε͹ɺ֤จࣈྻͷ prex Λྻڍͯ͠ɺͦΕΒΛ͢΂ͯঢ় ଶͱ͠Α͏ʂ P = {AAA, AAG, T, TCA, TG} ͷ৔߹ɺ͋ΓಘΔঢ়ଶ͸ A, AA, AAA, AAG, T, TC, TCA, TG ͜ͷঢ়ଶؒͷભҠ͕೺ѲͰ͖Ε͹ɺઌ΄Ͳͱಉ༷ʹղ͚Δʂ dp[i][j] := S Λ i จࣈ໨·Ͱݟͨͱ͖ɺͦͷ sux ͕ j ൪໨ͷঢ়ଶͱ Ұக͍ͯ͠ΔΑ͏ʹ͢ΔͨΊʹඞཁͳૢ࡞ճ਺ͷ࠷খ஋ next ഑ྻΛಘΔલॲཧ: O(N2L2 + NL3 log(NL)), DP O(NL|S|) L ͸ Pi ͷ௕্͞ݶ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 22 / 36
32. ېࢭจࣈྻ (ෳ਺ ver.) Trie ໦ͷ֤ϊʔυΛঢ়ଶͱղऍͰ͖Δ (ͭ·Γ Trie ໦্Ͱ DP ͍ͯ͠Δ) ֤ϊʔυʹ͍ͭͯɺ࣍ʹԿͷจࣈ͕དྷͨΒͲͷϊʔυʹҠಈ͢Δ͔Λલॲཧ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 23 / 36
33. ېࢭจࣈྻ (ෳ਺ ver.) ࣮૷͸ҎԼͷ௨Γ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 24 / 36
34. ېࢭจࣈྻ (ෳ਺ ver.) ࣮૷͸ҎԼͷ௨Γ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 24 / 36
35. ېࢭจࣈྻ (ෳ਺ ver.) ࣮૷͸ҎԼͷ௨Γ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 24 / 36
36. Genetic engineering Genetic engineering `A', `G', `C', `T' ͷ 4 छྨͷจࣈͷΈؚ͕·ΕΔจࣈྻΛ DNA จࣈྻͱশ ͢ΔɻM ݸͷ DNA จࣈྻ P = {p1, · · · , pM } ͕༩͑ΒΕΔͷͰɺ͜ͷύ λʔϯΛ (۠ؒඃΓ͋ΓͰ) ࿈݁ͤͯ͞ N จࣈͷจࣈྻΛ࡞Γ͍ͨɻੜ੒ Մೳͳ N จࣈͷจࣈྻ͸Կ௨Γ͋Δ͔ʁ 1 ≤ N ≤ 103 1 ≤ M ≤ 10 1 ≤ |pi | ≤ 10, ύλʔϯจࣈྻ͸૬ҟͳΔ ग़య: Yandex. Algorithm 2011 Round 2: C Link αϯϓϧ ೖྗ 1: JT1 ग़ྗ 1: JT1 ೖྗ 2: JT1 ग़ྗ 2: JT1 (ೖྗ 2 ͸ɺCATCAT, CATACT ͷ 2 ௨Γ) tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 25 / 36
37. Genetic engineering ύλʔϯจࣈྻͷ௕͕͞ߴʑ 10 ͳͷͰɺޙΖ 10 จࣈ͚֮ͩ͑ͯ DP Ͱ͖Δ͔ʁ ͜Ε͸ແཧ (DP ͷঢ়ଶ਺͚ͩͰ 109 ݸ͘Β͍͋Δ) Trie ໦্ͷ DP ʹམͱ͠ࠐΊͳ͍͔ʁ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 26 / 36
38. Genetic engineering ύλʔϯจࣈྻͷ௕͕͞ߴʑ 10 ͳͷͰɺޙΖ 10 จࣈ͚֮ͩ͑ͯ DP Ͱ͖Δ͔ʁ ͜Ε͸ແཧ (DP ͷঢ়ଶ਺͚ͩͰ 109 ݸ͘Β͍͋Δ) Trie ໦্ͷ DP ʹམͱ͠ࠐΊͳ͍͔ʁ ݁࿦͔Βݴ͏ͱɺͰ͖Δ ঢ়ଶ͸ͲͷΑ͏ʹ͔࣋ͭʁ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 26 / 36
39. Genetic engineering ύλʔϯจࣈྻͷ௕͕͞ߴʑ 10 ͳͷͰɺޙΖ 10 จࣈ͚֮ͩ͑ͯ DP Ͱ͖Δ͔ʁ ͜Ε͸ແཧ (DP ͷঢ়ଶ਺͚ͩͰ 109 ݸ͘Β͍͋Δ) Trie ໦্ͷ DP ʹམͱ͠ࠐΊͳ͍͔ʁ ݁࿦͔Βݴ͏ͱɺͰ͖Δ ঢ়ଶ͸ͲͷΑ͏ʹ͔࣋ͭʁ dp[i][j][k] := i จࣈ໨·ͰจࣈྻΛ࡞੒ɾTrie ໦্ͷ k ൪໨ͷঢ়ଶɾύ λʔϯจࣈྻͷ͍ͣΕ͔ͱ࠷ޙʹҰகͨ͠ͷ͕ j จࣈલ Ͱ͋ΔΑ͏ͳ ঢ়ଶͷ૯਺ ͱ͢Δ ࣍ͷϖʔδͰৄ͘͠ݟ͍ͯ͜͏ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 26 / 36
40. Genetic engineering ېࢭจࣈྻͷͱ͖ͱಉ༷ʹɺύλʔϯจࣈྻ͔Β Trie ໦Λ࡞Δ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 27 / 36
41. Genetic engineering DP ͕ҎԼͷঢ়ଶͰ͋ͬͨͱ͢Δ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 28 / 36
42. Genetic engineering ࣍ͷจࣈͱͯ͠ `T' Λબ୒͢ΔͱɺҎԼͷঢ়ଶʹͳΔ ࠷ޙʹύλʔϯͱҰகͨ͠ͷ͸ 4 จࣈલ͕ͩɺ3 จࣈͷύλʔϯจࣈྻͰ ͸͜ͷߔΛຒΊΒΕͳ͍ͷͰɺ͜ͷঢ়ଶ͸ࣺͯΒΕΔ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 29 / 36
43. Genetic engineering ࠷ޙʹύλʔϯͱҰகͨ͠ͷ͕ɺ΋͏গ͔ۙͬͨ͠ΒͲ͏ͳΔ͔ʁ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 30 / 36
44. Genetic engineering ͜ͷ৔߹͸ɺύλʔϯจࣈྻ AGT ʹΑͬͯߔΛຒΊΒΕΔʂ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 31 / 36
45. Genetic engineering ࠓͷભҠʹΑͬͯύλʔϯͱҰகͨͨ͠Ίɺ࠷ޙʹύλʔϯͱҰகͨ͠ͷ ͸ 0 จࣈલʹߋ৽͞ΕΔ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 32 / 36
46. Genetic engineering Trie ໦಺ͷঢ়ଶ਺࠷େ͸ɺ͍͍ͩͨύλʔϯจࣈྻ௕ͷ૯࿨ L = ∑ i |pi | (ߴʑ 100) ࠷ޙʹύλʔϯͱҰக͢ΔΠϯσοΫε͸ɺߴʑʮ࠷΋௕͍ύλʔϯ จࣈྻ௕ʯલ·Ͱߟྀ͢Ε͹ྑ͍ ͦΕҎ্ԕ͘·Ͱ૎Βͳ͚Ε͹͍͚ͳ͍৔߹ɺߔΛຒΊΔͷ͸ෆՄೳ X = maxi |pi | (ߴʑ 10) DP ͷঢ়ଶ਺͸ O(NLX) ͰɺભҠ O(1) ͳͷͰɺDP ͷܭࢉྔ͸ O(NLX) ˠ ؒʹ߹͏ʂ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 33 / 36
47. Genetic engineering ࣮૷ (௕͍ͷͰ DP ෦෼ͷΈ঺հ) tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 34 / 36
48. උߟ Trie ໦ʹ͓͍ͯʮ࣍ʹͲͷϊʔυʹҠಈ͢Δ͔ʯͷલॲཧ͸ɺ࣮͸ઢ ܗ࣌ؒͰߏஙՄೳ (Aho-Corasick ๏) ը૾ग़య: Aho Corasick ๏ - naoya ͷ͸ͯͳμΠΞϦʔ Link tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 35 / 36
49. ࿅श໰୊ OnlySanta (TopCoder SRM 727 Div1 Easy) Link ManageSubsequences ͱಉ͡ճͷ Div1 Easy ղ๏΋ඇৗʹࣅ͍ͯ·͢ ༗޲άϥϑ (AtCoder Regular Contest 030 C) Link యܕΑΓͷจࣈྻ DP લճ monkukui ܅͕঺հͯ͘͠Εͨάϥϑ෼໺ͷ෮शʹ΋ͳΓ·͢ ͨΜͨ͘͝͞Μ (ఱԼҰϓϩάϥϚʔίϯςετ 2016 ຊઓ C) Link Trie ໦ʹ׳ΕΔͷʹ࠷దͳ໰୊ͩͱࢥ͍·͢ ๅ͘͡ (౦ژେֶϓϩάϥϛϯάίϯςετ 2014 E) Link ͜Ε΋ Trie ໦ จࣈྻ (Typical DP Contest O) Link ·ͩղ͍ͯͳ͍ɾɾɾ tsutaj (Hokkaido Univ.) จࣈྻ DP (Ԡ༻ฤ) July 27, 2018 36 / 36