概要
- N(=3000)枚の寿司ネタ(a-zの26種類)を連続して流す(文字列Sとする)。
- その中からM(=7)枚の部分列がQ(=30000)個問い合わせられる。ただし場合により部分列は連続していないことがある。
- そのそれぞれに対し、S上でのインデックスを答える。
決定的アルゴリズム
この問題、D=1とすれば、部分列は連続であることが保証されます。つまり、決定的アルゴリズムを使うことができます。
発展
- この状態であれば、0..Nのそれぞれ(j)に対し、qがS[j,M*3]中にこの順番で入っている数(ただしSの先頭に入っているほど重みを大きくする)が最大となるjをインデックスとして答える実装にすることで、D=2.5程度までは安定してインデックスを求めることができます。
- 「*3」は、元となる部分文字列の長さはM*3以下であることを期待しています。
この「重み」が評価関数の肝になると思うのですが、調整の余地が残っている気がします。
C++の(コンテスト後)最終版(381792点) https://rco-contest-2018-final-open.contest.atcoder.jp/submissions/2179945
なお、コンテスト中は元となる部分文字列の長さがMであり、qの長さがM未満になりうると誤読していました、D=1.5にしかできなかったので324730点どまりでした。無念。
記事としての結論
- 順位表で、ある点数を取っている人が沢山いる場合は決定的アルゴリズムを疑うのは有用ではないかと思います。
補足
1
| kzsbqmuxtqwazgonugucjaouqsihsmgjpvdiwscfaewltvsyolgoenjcmlylyzhqlhgaypshugqlrqfxjigsliujfconzsyrnctoeztichmtznzxfhfkcpytpenkyqxmwxeaihahytbkbqkzxplhdtnzbsnpwhdpzjykrgwoxihvkiqrgmruztplaiuqecvbrvlbkwsbylxgxytyhsyiedtfvkjiylnjmcmhvtlkrmqbafrhngsqrvfbkadbkjshyhbagjoyhqmwipzegzqjkpxoquezkdplxombjqkdtbgnghkdaregkmrxelhpfbfoewbnfewmqvyivwkhfahoryxqvqnoguwpcldzcqlbpfruijrenfofeajcnrtcnqlzhbwdxwglmbkhdfhdyhfinxkwksypafghuoilqofnmbiavcqtjszdtowlqsdienoymvlrhczlysmlokhbvluaelotziotdtcwnvsigjnfjfywkeyalcmxgwyojkjrigvlnoqehmgopgvhntqxvnmxobebiwbzomjracdoerdndvbdygoyeayujwhtoiouxhmdbqusqbmqwnucgbzligimgnaswqbcdjchomvihdwmksltueulypyjsrnjeyoipdfxtveurkuwxatwmawmvrahsgexunjrdzemesmkfxmdzjvqxijdqoabvahbzeklborztczqlicyzbpemqinofcfuvaznakgxaevhcmqgmnescpxghixypxsxcxcqsqpkldvycwkxhkqcwqlqxnpoazsohnoucsztqdizbntfdeteiximtuymuzodlquigwhzoqjezyqahpkifvbyhkibmhslzdwybpojuegpyopwcdigpepmgpgdgdlumhrnfscleimrhriyjxfypdawcybayotfguipljmjvzxixpxugnlzvqemwluzwskegvpmpvrftyrfegxwetstcouotmofsakluqdmliroqiaodhrbvxnqgwrqntenstlhykhjalzlwuqvcmwawfyqojhpymlgycsxyhgqxjvesdbifgxitdikicrtnuzywysuvxrsidvtwisowtvltfyvmeqdpnzhklcvxmygjzmtpfqzezwkgiwfdctpchqfljqenqbxhxuivldilsldfesvtebuxcpqsharzikqnvxudumxqlknkpblcicqjimafnaqbocjmguzcliduealstwhnyqcbypexcnyjndbwgvefjwlbzilcqejkylrwqmbzsxolbvuihmkvyjlwkitvthxsmozyektmnhxifxziytweudfnhipwstdzwqcekmuswolxrvwagpfhlgwqhqsgocwioykxpnlkpcjtzdfwfxnfrdjnpkmfkninbsmpdblqveasiejnqxthdioxfpruxabcjftnkgdphravwvzlcgtonqcftlckmvmxvhojwuzpetwyhzvcrgclxembtiksgkxrnwhpamnrcztbftknzijgsrxwnfxrzhacvfakjapavrbrmdacqhurnqozroebwnqjgmcnpdwkrhzwbrusawknwyglczmewansanujgkljlntcbxeqtuczwnsvawpgkzkzqnruqbnuoepfxylqmqfodorsrlyuhoxtgxqizpzokjqskcapuoctghnhsprjgyayidqelwfaufxvpcqgtbvgltgbrbmtawovsdvsnmjymqdtkjeptmhmcjenmwktbnvmqnjyuceclnpeqktpdhclyvwbszlqlvzbahuktlwyzphaoaftshmvelbhvbqyfatbjmknybdnpjpxtovwodvxzdapgwbekptxputuqwsfrcqyauvegdfcjsjudqnqiqsfzeoevlkdczpkwejcfekodqdcpzqsjfhgkovcjzhtnyosceiknalxljzpcsnqnpvigrmblkflihbrireolvlpmyunynuemvfkmyhryqvwcqrbnryjydnsusbesncslszxjpirhqxbfnsxlwsrbxurvjystorpmeiyxcmgynknfdlzqgatiyhmyfksjbcokchpbgxgjkiafsmzepbfmjzyntzcalnfufqlgqkwynmizavocyqijpuevsjdlvbwmycvepjzvhxznxlyhaeypicgiyfnxwasyukgmiwikmgtkvgwevafmkpnphuvczrjcgqewivjugpikduiofvaeshowxzcuxecemurqieiflobzxbxswciepxwfmhkevjxtngfxgckfvtztjyznqkyiymeauyvkdgspmzgxmxuoztrkpudrdowrysdcozcpbydsygxroclwhldqrzswnldbgjybwhrseljwmclgzabgpmthltqocahrzrnowgpcrzkazcyhxqdknlapzhjyhjsnejbnoeabjvdcxjkgcniokyxyjujkfmtgrxdvwpnbxficmzrbspvozlsmdoxdefbhgmfumuakdxdivrvzjfdngjqxutjeibzahvmktqjvryplivblnetnvukxjmvtgzidxhokfhicoaqvhpmwpoefwgqsznyczfetgnfqtwornmnslycqodunanvrzvtufmxdqubnqfbyzrwcmyteukdskmjhsijkhzqopckiobdabsyzujbxjnymiaroiwafpwbpihqnhlmxsopoxbqrfxhavgqurfpkgskntoavqdbfhqkfyspwmihrtesoemfnbwswyqutsaujcdkepdukawaigywzveizimplsnvalkgrgeuznvbxgeruhwoijvmcazucrvofdmvuqcsyejrmeyclsgafckhcdtpvlvymcvswgfzkphxbmgcdxzlxzqmdwocowclvwrspkurzjsbnxfxiatubjfriasfyxwdejpmsfvmfptijwykizxoubgetmbsogpwqwkqlsfxklopxpwjwrpizgqonplrpfpmqagnmcgcoqgemovxtxrkdnwqugvmyqetbiqchfcmpsunwjnuplmzwjplfj
|