C++ の動作確認をしてみた（６０９）

C++の練習を兼ねて, 第九回アルゴリズム実技検定の問題H (最長非共通部分列) を解いてみた.

■感想.
1. 問題Hは, 方針が見えなかったので, 解説を参考にしたところ, AC版に到達できた.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 最長非共通部分列(Longest Non-Common Subsequence)に関して, その概念を, 学習できたと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト第九回アルゴリズム実技検定の各リンクをご覧下さい.

■C++版プログラム(問題H／AC版).

// 解き直し.
// https://atcoder.jp/contests/past202112-open/editorial/3129
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vs = vector<set<int>>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
int dp[5050][5050];

int main(){
    
    // 1. 入力情報.
    char s[5050], t[5050];
    scanf("%s %s", s, t);
    
    // 2. dp更新.
    int N = strlen(s);
    int M = strlen(t);
    rep(a, N){
        rep(b, M){
            // S[a] と T[b] を 両方使う.
            if(s[a] != t[b]) dp[a + 1][b + 1] = max(dp[a + 1][b + 1], dp[a][b] + 1);
            
            // S[a] と T[b] の 少なくとも一方を使わない場合.
            dp[a + 1][b + 0] = max(dp[a + 1][b + 0], dp[a][b]);
            dp[a + 0][b + 1] = max(dp[a + 0][b + 1], dp[a][b]);
            dp[a + 1][b + 1] = max({dp[a + 1][b + 1], dp[a + 1][b + 0], dp[a + 0][b + 1]});
        }
    }
    
    // 3. 出力.
    printf("%d\n", dp[N][M]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/past202112-open/editorial/3129

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vs = vector<set<int>>;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

int dp[5050][5050];

int main(){

// 1. 入力情報.

char s[5050], t[5050];

scanf("%s %s", s, t);

// 2. dp更新.

int N = strlen(s);

int M = strlen(t);

rep(a, N){

rep(b, M){

// S[a] と T[b] を両方使う.

if(s[a] != t[b]) dp[a + 1][b + 1] = max(dp[a + 1][b + 1], dp[a][b] + 1);

// S[a] と T[b] の少なくとも一方を使わない場合.

dp[a + 1][b + 0] = max(dp[a + 1][b + 0], dp[a][b]);

dp[a + 0][b + 1] = max(dp[a + 0][b + 1], dp[a][b]);

dp[a + 1][b + 1] = max({dp[a + 1][b + 1], dp[a + 1][b + 0], dp[a + 0][b + 1]});

}

// 3. 出力.

printf("%d\n", dp[N][M]);

return 0;

}

[入力例]
abc
aba

[出力例]
2
※AtCoderテストケースより

[入力例]
aaaaaa
a

[出力例]
0
※AtCoderテストケースより

[入力例]
abra
cadabra

[出力例]
4
※AtCoderテストケースより

[入力例]
oooopppqqrrrsss
oooppqrrssstttt

[出力例]
12

[入力例]
yfbtiphgpoierzzkhrnyawhgjqbnsciaiditqouwhtfxhamwryqtzguzrafvgifexvvmiktzepdwnvesuvmsgigxizbxrynyskypjrthvvicmifkyffqxkiouieoidjtsxwwjqaflytcmzvmpacmalcuucqtujpagpmtnpdtadlvosihreliuhfwssakqknyiqowqlww
zfdxmlcbgrubvnalctxasvihvjweishewyhvvziaoyyybklzhcomsgjncqcscfzdyknlbmdrxligotjlshferdfwqkoastrqcqfepovdxmpjobgujagplfbnrnbvdntpnkrvbkdjznjybqpcnbrxpkeolbrmyjvscroszlravwxsribentjjwcisvujyjlpvnwvtkrca

[出力例]
197

[入力例]
cuwllsesaoaanxfghjytmttwsmdrmgfisujygpusbxgwdsikzuyixsbtpnwuwuawarsesfmnhuijjhfetoovqwuezcxqhneuyjnfibobwgyjpgamvdpresibyqrpcyusskijajdalxyvqgldyqcukldztmuaxnfqmocvxjrlziivycyrgdfbqvbysdtydffvwnsivkicgdmtmcugfkhscbuuvbsqfaykqiiseztmebmzdksulvxsyqqyekwfgntubqqggtlegcophdaedonulmnvqyunwukrclpsezrwoplyxxqsmbvlykctngbcyhgfaydfbtdetknxibyessslaghwrqizaafjlxgrokbdexyyxelmgesdlegamceyobadkylenxntzogqmgohmwgzsilajuxohgxjxaloryjsbjsrutzcilgwrmfwlbtfptwkxyfjywihisvpaozszcpmwhjtpwelkmfjfjnfstyaukhscantysqiljidoikimpmngpsmijhklknshqhcubhfgdcfgkifayxdlvaakunebttqhhchkoyknrlwwpyqucipsvxntlkqrwrgflupqdetxinhzhaesriqtdngrxuxccoedyhoesdydenrutgfqkrvuecajgkdxfdufptcrxmsbgllzhniarmnivvdkadflexzfpooomhcydasfrcshfbyetninsxnutpiyqrbtzqcdsujcznnptplcrjiddnnurlervukhhqeweyiypqrznznfxwggrfqloloehthkrthnxqqceqdteyinpcvuwzrximynobuglgwvsczkvebtngsgvyocvnqjnaanelwaamkhwlmrwihlgfplojnvywwjcizwycnbyvgpulydcfyukfucdvlxxgzcvwlqchommydyrfukhqzlweqvcrpqawuabfclpjohsiidfrtbsdfzohkkjsvlvkwujbfrlorlqakoiwonpjmwgrkegiacbco
fwmskagltnakcfqnfwsqtelzinginpilrbjchyfbjkgqjhnrrzcmqbqvcompavodojucybjlkfhqsvvibqcrjtmsbzcmuzmzrpnngaouepcscmmohyojyhrdyijesqfocykarhfmxozhqeaawogsbethpydovwnipohocnratyaagqjgmudgwxigxyyvzaigkinpuabgzsrcqbcxmdcugpovtnlaiyxreifjjiifpwtvnlwemocuijllpxhdmvvliioqvqrfoaqebopripetkludfcucjbhqlrtipoxyrfwfclmhvbbrebwcezjzydrwnudfzaykbvieabjezocryfrbitlyapjcffbaqmgutydvoyzzallhnuqnflqyjlfdajgwajkdjawjxfixuycyhffsayfjjrwyvnawqdnpbionwgktolanaxzuclwltsngdqfcjdvwvuaelupmoxalmsgjfrrafmvoeiqbtdrpfowapyiwfegvsdvytijbzglpzxcvnddqiijthfngxwtcnqosoodogpbnvbzovdsbniyokqiqhkmhofzhgarxetezzchmhrkuwliwwrlcetgxhwddxrdunwjaqrpfyfoniuopcxhxwzkzvypkvykslkchudkxgrrjhqmfkclslsccedueymrsdiaejfjngvyvarongoewfmnfxkqtxcvnhujprdskjgmcqmezwmrtauhnenfojpwofvpvrqzoiuecnndpnnauzvpomtcdimjbgcpewpkcyyimzqunxthtzhcxuazuuhynzdtrvxevitgfmgpcjlhqetmkonmzairztyhghtqakkfcqbrpxzvgasrsunnlrhyomxnoihilfnkckaqvstlwuahbupufwzleplwjvyllhgndzcptjheuekrnimvaykhinxivupxpxuzbnggjubvaeemencunpzcosjvndsmfvyvfsstenakcdsgxwnmegaykmmdcsnzxblvt

[出力例]
985

[入力例]
tjgqvvdipknzaeedgpuwbtowamjeeszoeptnnwkjvetrkcrpbnykpvxvxkmafjmojswxvxzlulxlzkdcdgwprvulgdxjwadenwyagqhnyamttckhrugrybquhnddojizvotaowmoczmwvzmojasuyqvsiymzmirsoxqqzixlkfdrdanjzsnhhjksiszhejyjxjujhwaqaalbmjqwssiqcchsylvezfeviijzzobiyeyestlajsnlbwodlgwsufoqtupwnppcbwiryhwyhhkyciscfmmkqaubysmmrqwxgqprtutnbwyrzinpmkmtdtfchqpvqankqdlpehzrsbytdflyerlrbkwjwkrshbjijqvqfbgvmoocpuqephppczawzcfuiolvsdpcwidoewthgkwnsutdaazpnwygfkoxatecipqoaoglgrckdufenwhjuycxmybfdpjtoilmjxzjcdwvvqkynfevakjyasmqnbbwfybfcejhseuodowvlnznewqunixjktsqbuwkwsjupxszbjxogxgmxdwgmdzrbogvmsfyklxctnxopcviuoxjlrepdgydgxkjjxoqxxzqlhmaxdwayafcphklrupuuitvapphmkgwgxrquggkhnftqvgdwpibmlepvglfftsuczcqsbbwhkybefdjzdbpyxnlajpqrjtqdsdsrbvejlsfenpjogmspqmpbxnhcxxgsyafxjyulkcbauxzegzvndqwdfxtuuoxqbingaasqukhzhympmirgnhczytrfpdtezrstxtgssrolkgxixntfkfcysknbvtwjqxffljieuxahyylbcuhpywxjfvaiowjuuxwghfyvvrujctjqaynhlovucvdthektngptqcjbzwcidogjncihfnfpmosfkbmgoakyrxhqcwukdlrsqcsybhchmtbqkynswxqcaesnkgoaacddybwmxkhuxqqditkdrzneneeccllxuhzcsxfrnmffojtopguoxlvsiyzomfpoyoduiuhhxsiixpqbhsivyxkefaujmfevuhxbwynwqfjfhfobolnumvvoyydzoezldblgnnnwcscajuwicymyjdjdpyduycinojkmvamfxjdfiknuptpdkmwvhelssvsdjojtvrgocrwmftacorkqtsqyhjnpxnhbfjspingmjiaycqfmicfehtsutsfgvhkohqvwiebohencjgnwnnpwzvkumwwankrzhvfmfopqfddwvckhtgjcvjqvztvhzryprmocrsyvjrhghqekimygtaciqzcbvzujjptsvrouoqhveecbccssdzzxaxwfboyxaozplhdryqudahniwmgmxfapgsmwxnximgbucxbpcclyrexiqufafvjvphbbeziqryihbxrlllfltnwytmoarlxbwihiaosmbiqlwgeynfukwalhorqfpahlyzkeehfauulbekusyxdftdbqudczkdqtuujcjlfikjzxgobwzwakmueykehpovfhuhiiasbhucpotjddrwtnbfgijnfwylozwnclimdwnivhulmrprqbtesdkjiuqlchzagdaxxoiojfhewwwguwnndqnrjciouakgklgtaittvjibzvovtehyhtqrubhgcdftflyscstlmkqeuvsuxfzslprioqymdvgcstbxqvdzpnwtudndnsjmhdrgzuafrllgbkrfmenarowdjwebyqravatgiqbuympdyqfunspxoklbyasrtibikwbvnnrsxzxewkejfbydiliyktdfzhszkofdvnqvkqezaucqjobvrcuwwhnqypnwmmtqzjxuggfhtjijcifbakepkvxxlzwkmyrtqhywslvwwpeoyxsrktkjoouvukqjizkcyoihmwwmyafomuuxysgvgypnwkjnjdzojxlwxzkmnecwjwljoadctwwfjxircxlvooxyvehqoywoefvdsiipocwjpzurzbwdsbnhjongsrkddksxqfoyjeybjhdfijvbcvzxoahduambjlgiryvjhgtzahssjeuvpghzrvxwiqkkmnrhrszlgfaykjdgocmdzmbtrfgoyekmlozxeopirxmluoxqjrixxgnlvyymuynmrxlimllfbsngvfklgwgotkykrlsrgiztauhuaejodhenbcejtfofktsmtsmbycgdbuaozghxopehhpuuqkqidngibqrbocrifqczzczmrdtzfutmvaotosymlnszyfkmgpkrfwldehjfblyxpbamnskkkehriazbedwdjmfzpjhhkpqwbjgocxireiujvyoxctrbdqgbyiyavulokjdbldaauraqdzswyskbqmtazvmjmzlnsuccdlhckfvgzrvlpicwhgmbbqpvkzholayimpvdewtjvqblurucqokcpzvinqjwmsfhuslvwogfmgsuirttcsgusegvbyullwwvgbaawmdkdtypxuftw
zmusswrdosvdpdmjmnxixmrdafjwzicvgouewzoxawirtfjybalmgepmuyshctdeynkjxuqrbzrsmtfklbwabjqxhtefyeujhbeucruirfikyfbbefpjvrnkegwowgqdocycgfaqawvyeowoxqxfdrhkbimkaycysijshsfxwybtnyyrrvbjwvwrlykuixvminybjiekdfugcoiutqzmbuvedfburfqwodxrqdecvnmsuenxnxzazpctqitltbsifspekzbjephsnhzgyqqsnzlamfjzdzyporzsrpbnvuqviilqvlfrrjtpweyelndzibejgekummgkdsrrdwgkfbngyajdtafaebjdinjsvhhxgrsyntoycubblukgejkctshjclxotgnctmbkpqpwsdfsknnxjrnpuexqgfpefwdzciinieempavtyobezwktzrmmwwaxrqemektgjcsqieyxveasqfkmeznlribgvauretvdmswuqwxulmealcozeltmhjwgjipgowgddlpvplxopwafdepuekmgjlxjwafkzlddbepjbuwrsrxwlppegpfzganrdbkhmldnzluabikaafdrwdvjinkwltjoebjrvajduwdismobyqskodndnecrjdczdeudjnajpxevctyjnsfszlsduydwquwqkwchkpcdbdnyajrwajdtzkzqjxirspgjnzdfuilvhnujnrpvhzvctlebfrvfqgjapcmsjquxjnypzhofiidseigebuevdutnjrrcfonhemocuohtohodvelhcslaudwqlolpeiibnrbxfxfxtannbrazeasofuiusnwtevfcqsuggewepdvtwrozjcgcbuvhssykugxbjmgryyhnnwdvtueejjwnpgxwbldzmyytirbyuzrnmxpqyhlbprrzftczghhivqvjovgaryigqllalrqycjmcaehgxskljgzzqlhdtgnziyxribyyhcgvbqslhtcflbmraohrmpkycxrrdnndeorxkmzgmykysughcjzkxzzbkndseerorasojbcypcknsksimpibchhrtnsdtmkrranfurkqjwyzqzifgypqalncntrghrqvnwsvspkytrmqzrmqhqozntqkybetbdotoupgdejrishmfvgdwryclkeibgjfygliqqptcxmpoumlbraztaiqmtlzumfntkmfvdtpnldfcuoyehbflwofjautatkfljzpomqfzbhdgkdlkcprajcofapdafsyqfnpkggacijxndfwwjzziwtduxosqknmglqeuqpyxcxmopvnmtijituzptnajvkqwrilidlnxmmajipjhwivbwdnhoizmxdxpmsafliprgedieifljibtmuydkhwljuqufagudeukmnhldemzhjwudptxvuxnhkiocqusdpgmgnrdyxsqftakvredpzqaryskufmtcthydhmihaxjhnszgpikhkrynfgzzjglvzubonxbwqkbvfbefajddnunpjdsfonxpevkrwltagvtvjjotqnegawfnjjduomtgfsydpoctkvtfbsuxamulkwooluhgsxqhckfpobjshspkdpyucddqerkxvzzvltbtvprmrwpbtltkiwbfnotdedsqmgotanfzdopthflaiflysyiwgulhxxfgxwhuohjauovyhwkxuxxkibspugiaaqdztutmurcmnltjivbwsnmfhjzqhlbhaxdbnthkhkkahjtanblvuqidylxelgzhqncsqawjndxpifvqxetaimerwyktohnsuqzfftlkkczimzubnsfvllibqsvihhpkhvdhbdpyuidwapmdtlkrfpuvevbepgrgnklryvscoagzsgxkvnleekcpbhewvvhludjujkjozvulsczmrejdufnhizcahcmffofawlnwtqqygeprypdhrhxgwjfzjpuufqpzwncoltuhwoooktquyzlhmlbgwagmnbjybagjsopidpnmciotrepzdgloqvcebmjbsmpgsbjbkmzojjhjhirzawunifuualostpobqikadddrmiaogyigkjpmtwbjrlvdhwinmdfbikqgmtacbpqnxijiuegdroqutwrjyyscodibseiiaegloepyfssdblyqhxeosbmjpcmtsykdaplplmhdzefbkwbqlujvwlhsjrdkfkuagvifddvhaylvtjccpzhpolyquzcdlrirvsxbdrecrqnqhanigehjsrglfbnoroqowtmfeepfwvuiyhhgrcqewozmpeztltqbzdulygczgwyfrdqeznngwcqtflhhxnxeohurgyknlofsrcogerhszfisxtjpmxzshlizpufnbrojmebnbbpulvuzizjnyvltqkhafglyrtscgndgouhrzjpmvebznuepmwnlyviobosfflknhfizjstjbydphjhxngvuzejhchhkklpkvlabcogaml

[出力例]
2472

[入力例]

abc

aba

[出力例]

※AtCoderテストケースより

[入力例]

aaaaaa

[出力例]

※AtCoderテストケースより

[入力例]

abra

cadabra

[出力例]

※AtCoderテストケースより

[入力例]

oooopppqqrrrsss

oooppqrrssstttt

[出力例]

[入力例]

yfbtiphgpoierzzkhrnyawhgjqbnsciaiditqouwhtfxhamwryqtzguzrafvgifexvvmiktzepdwnvesuvmsgigxizbxrynyskypjrthvvicmifkyffqxkiouieoidjtsxwwjqaflytcmzvmpacmalcuucqtujpagpmtnpdtadlvosihreliuhfwssakqknyiqowqlww

zfdxmlcbgrubvnalctxasvihvjweishewyhvvziaoyyybklzhcomsgjncqcscfzdyknlbmdrxligotjlshferdfwqkoastrqcqfepovdxmpjobgujagplfbnrnbvdntpnkrvbkdjznjybqpcnbrxpkeolbrmyjvscroszlravwxsribentjjwcisvujyjlpvnwvtkrca

[出力例]

197

[入力例]

cuwllsesaoaanxfghjytmttwsmdrmgfisujygpusbxgwdsikzuyixsbtpnwuwuawarsesfmnhuijjhfetoovqwuezcxqhneuyjnfibobwgyjpgamvdpresibyqrpcyusskijajdalxyvqgldyqcukldztmuaxnfqmocvxjrlziivycyrgdfbqvbysdtydffvwnsivkicgdmtmcugfkhscbuuvbsqfaykqiiseztmebmzdksulvxsyqqyekwfgntubqqggtlegcophdaedonulmnvqyunwukrclpsezrwoplyxxqsmbvlykctngbcyhgfaydfbtdetknxibyessslaghwrqizaafjlxgrokbdexyyxelmgesdlegamceyobadkylenxntzogqmgohmwgzsilajuxohgxjxaloryjsbjsrutzcilgwrmfwlbtfptwkxyfjywihisvpaozszcpmwhjtpwelkmfjfjnfstyaukhscantysqiljidoikimpmngpsmijhklknshqhcubhfgdcfgkifayxdlvaakunebttqhhchkoyknrlwwpyqucipsvxntlkqrwrgflupqdetxinhzhaesriqtdngrxuxccoedyhoesdydenrutgfqkrvuecajgkdxfdufptcrxmsbgllzhniarmnivvdkadflexzfpooomhcydasfrcshfbyetninsxnutpiyqrbtzqcdsujcznnptplcrjiddnnurlervukhhqeweyiypqrznznfxwggrfqloloehthkrthnxqqceqdteyinpcvuwzrximynobuglgwvsczkvebtngsgvyocvnqjnaanelwaamkhwlmrwihlgfplojnvywwjcizwycnbyvgpulydcfyukfucdvlxxgzcvwlqchommydyrfukhqzlweqvcrpqawuabfclpjohsiidfrtbsdfzohkkjsvlvkwujbfrlorlqakoiwonpjmwgrkegiacbco

fwmskagltnakcfqnfwsqtelzinginpilrbjchyfbjkgqjhnrrzcmqbqvcompavodojucybjlkfhqsvvibqcrjtmsbzcmuzmzrpnngaouepcscmmohyojyhrdyijesqfocykarhfmxozhqeaawogsbethpydovwnipohocnratyaagqjgmudgwxigxyyvzaigkinpuabgzsrcqbcxmdcugpovtnlaiyxreifjjiifpwtvnlwemocuijllpxhdmvvliioqvqrfoaqebopripetkludfcucjbhqlrtipoxyrfwfclmhvbbrebwcezjzydrwnudfzaykbvieabjezocryfrbitlyapjcffbaqmgutydvoyzzallhnuqnflqyjlfdajgwajkdjawjxfixuycyhffsayfjjrwyvnawqdnpbionwgktolanaxzuclwltsngdqfcjdvwvuaelupmoxalmsgjfrrafmvoeiqbtdrpfowapyiwfegvsdvytijbzglpzxcvnddqiijthfngxwtcnqosoodogpbnvbzovdsbniyokqiqhkmhofzhgarxetezzchmhrkuwliwwrlcetgxhwddxrdunwjaqrpfyfoniuopcxhxwzkzvypkvykslkchudkxgrrjhqmfkclslsccedueymrsdiaejfjngvyvarongoewfmnfxkqtxcvnhujprdskjgmcqmezwmrtauhnenfojpwofvpvrqzoiuecnndpnnauzvpomtcdimjbgcpewpkcyyimzqunxthtzhcxuazuuhynzdtrvxevitgfmgpcjlhqetmkonmzairztyhghtqakkfcqbrpxzvgasrsunnlrhyomxnoihilfnkckaqvstlwuahbupufwzleplwjvyllhgndzcptjheuekrnimvaykhinxivupxpxuzbnggjubvaeemencunpzcosjvndsmfvyvfsstenakcdsgxwnmegaykmmdcsnzxblvt

[出力例]

985

[入力例]

tjgqvvdipknzaeedgpuwbtowamjeeszoeptnnwkjvetrkcrpbnykpvxvxkmafjmojswxvxzlulxlzkdcdgwprvulgdxjwadenwyagqhnyamttckhrugrybquhnddojizvotaowmoczmwvzmojasuyqvsiymzmirsoxqqzixlkfdrdanjzsnhhjksiszhejyjxjujhwaqaalbmjqwssiqcchsylvezfeviijzzobiyeyestlajsnlbwodlgwsufoqtupwnppcbwiryhwyhhkyciscfmmkqaubysmmrqwxgqprtutnbwyrzinpmkmtdtfchqpvqankqdlpehzrsbytdflyerlrbkwjwkrshbjijqvqfbgvmoocpuqephppczawzcfuiolvsdpcwidoewthgkwnsutdaazpnwygfkoxatecipqoaoglgrckdufenwhjuycxmybfdpjtoilmjxzjcdwvvqkynfevakjyasmqnbbwfybfcejhseuodowvlnznewqunixjktsqbuwkwsjupxszbjxogxgmxdwgmdzrbogvmsfyklxctnxopcviuoxjlrepdgydgxkjjxoqxxzqlhmaxdwayafcphklrupuuitvapphmkgwgxrquggkhnftqvgdwpibmlepvglfftsuczcqsbbwhkybefdjzdbpyxnlajpqrjtqdsdsrbvejlsfenpjogmspqmpbxnhcxxgsyafxjyulkcbauxzegzvndqwdfxtuuoxqbingaasqukhzhympmirgnhczytrfpdtezrstxtgssrolkgxixntfkfcysknbvtwjqxffljieuxahyylbcuhpywxjfvaiowjuuxwghfyvvrujctjqaynhlovucvdthektngptqcjbzwcidogjncihfnfpmosfkbmgoakyrxhqcwukdlrsqcsybhchmtbqkynswxqcaesnkgoaacddybwmxkhuxqqditkdrzneneeccllxuhzcsxfrnmffojtopguoxlvsiyzomfpoyoduiuhhxsiixpqbhsivyxkefaujmfevuhxbwynwqfjfhfobolnumvvoyydzoezldblgnnnwcscajuwicymyjdjdpyduycinojkmvamfxjdfiknuptpdkmwvhelssvsdjojtvrgocrwmftacorkqtsqyhjnpxnhbfjspingmjiaycqfmicfehtsutsfgvhkohqvwiebohencjgnwnnpwzvkumwwankrzhvfmfopqfddwvckhtgjcvjqvztvhzryprmocrsyvjrhghqekimygtaciqzcbvzujjptsvrouoqhveecbccssdzzxaxwfboyxaozplhdryqudahniwmgmxfapgsmwxnximgbucxbpcclyrexiqufafvjvphbbeziqryihbxrlllfltnwytmoarlxbwihiaosmbiqlwgeynfukwalhorqfpahlyzkeehfauulbekusyxdftdbqudczkdqtuujcjlfikjzxgobwzwakmueykehpovfhuhiiasbhucpotjddrwtnbfgijnfwylozwnclimdwnivhulmrprqbtesdkjiuqlchzagdaxxoiojfhewwwguwnndqnrjciouakgklgtaittvjibzvovtehyhtqrubhgcdftflyscstlmkqeuvsuxfzslprioqymdvgcstbxqvdzpnwtudndnsjmhdrgzuafrllgbkrfmenarowdjwebyqravatgiqbuympdyqfunspxoklbyasrtibikwbvnnrsxzxewkejfbydiliyktdfzhszkofdvnqvkqezaucqjobvrcuwwhnqypnwmmtqzjxuggfhtjijcifbakepkvxxlzwkmyrtqhywslvwwpeoyxsrktkjoouvukqjizkcyoihmwwmyafomuuxysgvgypnwkjnjdzojxlwxzkmnecwjwljoadctwwfjxircxlvooxyvehqoywoefvdsiipocwjpzurzbwdsbnhjongsrkddksxqfoyjeybjhdfijvbcvzxoahduambjlgiryvjhgtzahssjeuvpghzrvxwiqkkmnrhrszlgfaykjdgocmdzmbtrfgoyekmlozxeopirxmluoxqjrixxgnlvyymuynmrxlimllfbsngvfklgwgotkykrlsrgiztauhuaejodhenbcejtfofktsmtsmbycgdbuaozghxopehhpuuqkqidngibqrbocrifqczzczmrdtzfutmvaotosymlnszyfkmgpkrfwldehjfblyxpbamnskkkehriazbedwdjmfzpjhhkpqwbjgocxireiujvyoxctrbdqgbyiyavulokjdbldaauraqdzswyskbqmtazvmjmzlnsuccdlhckfvgzrvlpicwhgmbbqpvkzholayimpvdewtjvqblurucqokcpzvinqjwmsfhuslvwogfmgsuirttcsgusegvbyullwwvgbaawmdkdtypxuftw

zmusswrdosvdpdmjmnxixmrdafjwzicvgouewzoxawirtfjybalmgepmuyshctdeynkjxuqrbzrsmtfklbwabjqxhtefyeujhbeucruirfikyfbbefpjvrnkegwowgqdocycgfaqawvyeowoxqxfdrhkbimkaycysijshsfxwybtnyyrrvbjwvwrlykuixvminybjiekdfugcoiutqzmbuvedfburfqwodxrqdecvnmsuenxnxzazpctqitltbsifspekzbjephsnhzgyqqsnzlamfjzdzyporzsrpbnvuqviilqvlfrrjtpweyelndzibejgekummgkdsrrdwgkfbngyajdtafaebjdinjsvhhxgrsyntoycubblukgejkctshjclxotgnctmbkpqpwsdfsknnxjrnpuexqgfpefwdzciinieempavtyobezwktzrmmwwaxrqemektgjcsqieyxveasqfkmeznlribgvauretvdmswuqwxulmealcozeltmhjwgjipgowgddlpvplxopwafdepuekmgjlxjwafkzlddbepjbuwrsrxwlppegpfzganrdbkhmldnzluabikaafdrwdvjinkwltjoebjrvajduwdismobyqskodndnecrjdczdeudjnajpxevctyjnsfszlsduydwquwqkwchkpcdbdnyajrwajdtzkzqjxirspgjnzdfuilvhnujnrpvhzvctlebfrvfqgjapcmsjquxjnypzhofiidseigebuevdutnjrrcfonhemocuohtohodvelhcslaudwqlolpeiibnrbxfxfxtannbrazeasofuiusnwtevfcqsuggewepdvtwrozjcgcbuvhssykugxbjmgryyhnnwdvtueejjwnpgxwbldzmyytirbyuzrnmxpqyhlbprrzftczghhivqvjovgaryigqllalrqycjmcaehgxskljgzzqlhdtgnziyxribyyhcgvbqslhtcflbmraohrmpkycxrrdnndeorxkmzgmykysughcjzkxzzbkndseerorasojbcypcknsksimpibchhrtnsdtmkrranfurkqjwyzqzifgypqalncntrghrqvnwsvspkytrmqzrmqhqozntqkybetbdotoupgdejrishmfvgdwryclkeibgjfygliqqptcxmpoumlbraztaiqmtlzumfntkmfvdtpnldfcuoyehbflwofjautatkfljzpomqfzbhdgkdlkcprajcofapdafsyqfnpkggacijxndfwwjzziwtduxosqknmglqeuqpyxcxmopvnmtijituzptnajvkqwrilidlnxmmajipjhwivbwdnhoizmxdxpmsafliprgedieifljibtmuydkhwljuqufagudeukmnhldemzhjwudptxvuxnhkiocqusdpgmgnrdyxsqftakvredpzqaryskufmtcthydhmihaxjhnszgpikhkrynfgzzjglvzubonxbwqkbvfbefajddnunpjdsfonxpevkrwltagvtvjjotqnegawfnjjduomtgfsydpoctkvtfbsuxamulkwooluhgsxqhckfpobjshspkdpyucddqerkxvzzvltbtvprmrwpbtltkiwbfnotdedsqmgotanfzdopthflaiflysyiwgulhxxfgxwhuohjauovyhwkxuxxkibspugiaaqdztutmurcmnltjivbwsnmfhjzqhlbhaxdbnthkhkkahjtanblvuqidylxelgzhqncsqawjndxpifvqxetaimerwyktohnsuqzfftlkkczimzubnsfvllibqsvihhpkhvdhbdpyuidwapmdtlkrfpuvevbepgrgnklryvscoagzsgxkvnleekcpbhewvvhludjujkjozvulsczmrejdufnhizcahcmffofawlnwtqqygeprypdhrhxgwjfzjpuufqpzwncoltuhwoooktquyzlhmlbgwagmnbjybagjsopidpnmciotrepzdgloqvcebmjbsmpgsbjbkmzojjhjhirzawunifuualostpobqikadddrmiaogyigkjpmtwbjrlvdhwinmdfbikqgmtacbpqnxijiuegdroqutwrjyyscodibseiiaegloepyfssdblyqhxeosbmjpcmtsykdaplplmhdzefbkwbqlujvwlhsjrdkfkuagvifddvhaylvtjccpzhpolyquzcdlrirvsxbdrecrqnqhanigehjsrglfbnoroqowtmfeepfwvuiyhhgrcqewozmpeztltqbzdulygczgwyfrdqeznngwcqtflhhxnxeohurgyknlofsrcogerhszfisxtjpmxzshlizpufnbrojmebnbbpulvuzizjnyvltqkhafglyrtscgndgouhrzjpmvebznuepmwnlyviobosfflknhfizjstjbydphjhxngvuzejhchhkklpkvlabcogaml

[出力例]

2472

■参照サイト
第九回アルゴリズム実技検定

C++の練習を兼ねて, 第九回 アルゴリズム実技検定 の 問題H (最長非共通部分列) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, 第九回アルゴリズム実技検定の問題H (最長非共通部分列) を解いてみた.

コメントを残すコメントをキャンセル