SRM 486 :: DIV2
参加できなかったのでPractice
250
Strange abbreviations are often used to write text messages on uncomfortable mobile devices. One particular strategy for encoding texts composed of alphabetic characters and spaces is the following:
* Spaces are maintained, and each word is encoded individually. A word is a consecutive string of alphabetic characters.
* If the word is composed only of vowels, it is written exactly as in the original message.
* If the word has at least one consonant, write only the consonants that do not have another consonant immediately before them. Do not write any vowels.
* The letters considered vowels in these rules are 'a', 'e', 'i', 'o' and 'u'. All other letters are considered consonants.
For instance, "ps i love u" would be abbreviated as "p i lv u" while "please please me" would be abbreviated as "ps ps m".
You will be given the original message in the String original. Return a String with the message abbreviated using the described strategy.
easyにしては実装がやや面倒な問題だった。やるだけ
struct TxMsg{ bool boin(string t){ int i; for(i=0; i<t.size(); i++){ if( !(t[i]=='a' || t[i]=='i' || t[i]=='u' || t[i]=='e' || t[i]=='o') )break; } return i==t.size(); } string getMessage(string original){ vector<string> vs; stringstream ss(original); string t; while(ss>>t){ if( boin(t) ){ vs.pb(t); } else{ int f=0; int ch[64]; memset(ch,0,sizeof(ch)); rep(i,t.size()){ if( t[i]=='a' || t[i]=='i' || t[i]=='u' || t[i]=='e' || t[i]=='o' ) { ch[i]=1; f=0; }else if( f==1 ){ ch[i]=1; }else{ f=1; } } string a=""; rep(i,t.size())if( !ch[i] ){ a += (char)t[i]; } //t = a; vs.pb(a); } //cout << t << endl; } string ret; rep(i,vs.size()){ if( i>0 )ret += " "; ret += vs[i]; } return ret; } };
500
You've designed a computer and implemented all the common arithmetic operators: addition, subtraction, multiplication and integer division. However, your budget was very limited, so you could only afford to place a single register in the computer. The register can store any non-negative integer value. Since there is only one register, there is no need to identify the store location or the operands of each operation or its result. The programming language has four instructions: '+', '-', '*' and '/'. Each instruction performs the corresponding operation using the value in the register as both its parameters. It then stores the result in the same register, overwriting the previous content.
A program for your computer is a sequential list of zero or more instructions. You want to show that, even with its limitations, your newly constructed computer is powerful. You will be given two ints s and t. Return the shortest program that finishes with a value of t in the register if it contained s before executing. If there is more than one possible answer, return the one that comes earliest lexicographically. If there is no program that can do the job, return ":-(" (quotes for clarity) instead.
オーバーフロー処理してないけど、システムテスト通る…。
てきとーにBFS
struct OneRegister{ string getProgram(int s, int t){ set<ll> st; queue<pair<string,ll> > q; st.insert((ll)s); q.push( mp(string(""),s) ); if( s==t ) return ""; if( t==0 ) return "-"; if( t==1 ) return "/"; while( !q.empty() ){ queue<pair<string,ll> > tmp; while( !q.empty() ){ pair<string,ll> a = q.front(); q.pop(); if( st.find( a.second*a.second ) == st.end() ){ if( a.second*a.second == t )return a.first + "*"; st.insert( a.second*a.second ); tmp.push( mp(a.first + "*", a.second*a.second) ); } if( st.find( a.second+a.second ) == st.end() ){ if( a.second+a.second == t )return a.first + "+"; st.insert( a.second+a.second ); tmp.push( mp(a.first + "+", 2*a.second) ); } if( st.find( 1 ) == st.end() ){ if( 1 == t )return a.first + "/"; st.insert( 1 ); tmp.push( mp(a.first + "/", 1) ); } } q = tmp; } return ":-("; } };
1000
A rigorous teacher makes all his students stand in a line before entering the classroom. Being a rigorous teacher, he makes the students line up in non-descending order by height. One time, while the students were lining up, the teacher had to go to the bathroom. The students took the opportunity to play with the teacher's head and make a crazy line. They defined the craziness of a line as the sum of the absolute difference in height between each pair of consecutive students. Since a line ordered by height has minimum craziness, they of course decided to arrange themselves in a line with maximum craziness.
You are given a int[] heights, where each element is the height of a single student. Return the maximum possible craziness of a line made by those students.
struct CrazyLine{ int maxCrazyness(vector <int> heights){ vector<int> left,right; left = right = heights; sort(right.rbegin(), right.rend()); sort(left.begin(), left.end()); int ans = 0; if( heights.size()>1 )for(int k=0; k<2; k++){ vector<int> v; if( k==0 )v.pb(right[0]); else v.pb(left[0]); int cnt = 1; int ret = 0; int r,l; int end = 0; if( k==0 ){ r=1; l=0; } else { l=1; r=0; } for(int i=0;!end;i++){ if( i%2==k ){ if( cnt<heights.size()-1 ){ if( abs(v[0]-left[l])+abs(v.back()-left[l+1]) > abs(v.back()-left[l])+abs(v[0]-left[l]) ) { v.insert( v.begin(), left[l] ); v.pb( left[l+1] ); }else{ v.insert( v.begin(), left[l+1]); v.pb(left[l]); } l += 2; cnt += 2; }else{ if( abs(v[0]-left[l]) > abs(v.back()-left[l]) ){ v.insert(v.begin(),left[l]); }else{ v.pb(left[l]); } l++; cnt++; } if( cnt==heights.size() )break; }else{ if( cnt<heights.size()-1 ){ if( abs(v[0]-right[r])+abs(v.back()-right[r+1]) > abs(v.back()-right[r])+abs(v[0]-right[r]) ) { v.insert( v.begin(), right[r] ); v.pb( right[r+1] ); }else{ v.insert( v.begin(), right[r+1]); v.pb(right[r]); } r += 2; cnt += 2; }else{ if( abs(v[0]-right[r]) > abs(v.back()-right[r]) ){ v.insert(v.begin(),right[r]); }else{ v.pb(right[r]); } r++; cnt++; } if( cnt==heights.size() )break; } } rep(i,v.size()-1)ret += abs(v[i]-v[i+1]); ans = max(ans,ret); } return ans; } };
上記のコードになった経緯↓
えーっと、最初に基準を決めて、差の絶対値が大きい順に前か後ろに追加していく単純な貪欲法では？
てきとーに書く。サンプル通る、よし。
提出→Failed
なんでー、あ、最初の基準を最大しか試してなかった。最小も入れる。
サンプル通る、よし。
提出→Failed
orz
貪欲法が正しい解法か疑いつつも、おかしな処理を追加しつつテストしたら通った。おいおい
一発で通らなかったけど、1000pt問題の割にはすごく簡単なほう。
絶対に最初に考えた解法で正しいはず、と、書き直したら通った。まぁ不思議（よくあること
書き直したコード
struct CrazyLine{ int maxCrazyness(vector <int> heights){ int ret = 0; int n = heights.size(); sort(all(heights)); rep(k,2){ vector<int> tmp; int r,l; r = k ? n-2 : n-1; l = k ? 0 : 1; tmp.pb( k ? heights[n-1] : heights[0] ); for(;;){ if( tmp.size() == n )break; int t = -1; int num; if( abs(tmp[0]-heights[l]) > t ){ num=0; t=abs(tmp[0]-heights[l]); } if( abs(tmp[0]-heights[r]) > t ){ num=1; t=abs(tmp[0]-heights[r]); } if( abs(tmp.back()-heights[l]) > t ){ num=2; t=abs(tmp.back()-heights[l]); } if( abs(tmp.back()-heights[r]) > t ){ num=3; t=abs(tmp.back()-heights[r]); } if( num==0 || num==1 ){ tmp.insert(tmp.begin(),heights[num==0?l:r]); num==0 ? l++ : r--; }else{ tmp.pb(heights[num==2?l:r]); num==2 ? l++ : r--; } } int sum = 0; rep(i,tmp.size()-1)sum+=abs(tmp[i]-tmp[i+1]); ret = max(ret,sum); } return ret; } };
250のコードを逆アセンブリ
環境：g++ (Ubuntu 4.4.1-4ubuntu9) 4.4.1
何を思ったのか、逆アセンブリしたくなったのでやってみた。
感想：C++のアセンブリコードきたねえええええええええええええ、よめねえええええええええええ
if( t[i]=='a' || t[i]=='i' || t[i]=='u' || t[i]=='e' || t[i]=='o' )
.text:0804918A loc_804918A: ; CODE XREF: _ZN5TxMsg10getMessageESs+1C8j .text:0804918A mov eax, [ebp+var_2C] .text:0804918D mov [esp+218h+var_214], eax .text:08049191 lea eax, [ebp+var_20] .text:08049194 mov [esp+218h+var_218], eax .text:08049197 call __ZNSsixEj .text:0804919C movzx eax, byte ptr [eax] .text:0804919F cmp al, 61h .text:080491A1 jz short loc_8049207 .text:080491A3 mov eax, [ebp+var_2C] .text:080491A6 mov [esp+218h+var_214], eax .text:080491AA lea eax, [ebp+var_20] .text:080491AD mov [esp+218h+var_218], eax .text:080491B0 call __ZNSsixEj .text:080491B5 movzx eax, byte ptr [eax] .text:080491B8 cmp al, 69h .text:080491BA jz short loc_8049207 .text:080491BC mov eax, [ebp+var_2C] .text:080491BF mov [esp+218h+var_214], eax .text:080491C3 lea eax, [ebp+var_20] .text:080491C6 mov [esp+218h+var_218], eax .text:080491C9 call __ZNSsixEj .text:080491CE movzx eax, byte ptr [eax] .text:080491D1 cmp al, 75h .text:080491D3 jz short loc_8049207 .text:080491D5 mov eax, [ebp+var_2C] .text:080491D8 mov [esp+218h+var_214], eax .text:080491DC lea eax, [ebp+var_20] .text:080491DF mov [esp+218h+var_218], eax .text:080491E2 call __ZNSsixEj .text:080491E7 movzx eax, byte ptr [eax] .text:080491EA cmp al, 65h .text:080491EC jz short loc_8049207 .text:080491EE mov eax, [ebp+var_2C] .text:080491F1 mov [esp+218h+var_214], eax .text:080491F5 lea eax, [ebp+var_20] .text:080491F8 mov [esp+218h+var_218], eax .text:080491FB call __ZNSsixEj .text:08049200 movzx eax, byte ptr [eax] .text:08049203 cmp al, 6Fh .text:08049205 jnz short loc_804920E .text:08049207 .text:08049207 loc_8049207: ; CODE XREF: _ZN5TxMsg10getMessageESs+107j .text:08049207 ; _ZN5TxMsg10getMessageESs+120j ... .text:08049207 mov eax, 1 .text:0804920C jmp short loc_8049213 .text:0804920E ; ﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄ .text:0804920E .text:0804920E loc_804920E: ; CODE XREF: _ZN5TxMsg10getMessageESs+16Bj .text:0804920E mov eax, 0 .text:08049213 .text:08049213 loc_8049213: ; CODE XREF: _ZN5TxMsg10getMessageESs+172j .text:08049213 test al, al .text:08049215 jz short loc_804922E .text:08049217 mov eax, [ebp+var_2C] .text:0804921A mov [ebp+eax*4+var_204], 1 .text:08049225 mov [ebp+var_28], 0 .text:0804922C jmp short loc_804924B .text:0804922E ; ﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄﾄ .text:0804922E .text:0804922E loc_804922E: ; CODE XREF: _ZN5TxMsg10getMessageESs+17Bj .text:0804922E cmp [ebp+var_28], 1 .text:08049232 jnz short loc_8049244 .text:08049234 mov eax, [ebp+var_2C] .text:08049237 mov [ebp+eax*4+var_204], 1 .text:08049242 jmp short loc_804924B
__ZNSsixEjってなんだよorz
いや、それ以前に、さすがにこれはないんじゃないのｗｗｗ
無駄な処理多くなイカ？
最適化オプションでO2を設定してコード吐かせてみると、
.text:08049B97 loc_8049B97: ; CODE XREF: _ZN5TxMsg10getMessageESs+4D7j .text:08049B97 movzx ecx, byte ptr [eax+ebx] .text:08049B9B lea edx, [eax-0Ch] .text:08049B9E cmp cl, 61h .text:08049BA1 jz short loc_8049B60 .text:08049BA3 cmp dword ptr [edx+8], 0 .text:08049BA7 mov edi, edx .text:08049BA9 js short loc_8049BC2 .text:08049BAB lea edx, [ebp+var_28] .text:08049BAE mov [esp+228h+var_228], edx .text:08049BB1 call __ZNSs12_M_leak_hardEv .text:08049BB6 mov eax, [ebp+var_28] .text:08049BB9 movzx ecx, byte ptr [eax+ebx] .text:08049BBD lea edx, [eax-0Ch] .text:08049BC0 mov edi, edx .text:08049BC2 .text:08049BC2 loc_8049BC2: ; CODE XREF: _ZN5TxMsg10getMessageESs+4F9j .text:08049BC2 cmp cl, 69h .text:08049BC5 jz short loc_8049B60 .text:08049BC7 cmp dword ptr [edx+8], 0 .text:08049BCB js short loc_8049BE4 .text:08049BCD lea ecx, [ebp+var_28] .text:08049BD0 mov [esp+228h+var_228], ecx .text:08049BD3 call __ZNSs12_M_leak_hardEv .text:08049BD8 mov eax, [ebp+var_28] .text:08049BDB movzx ecx, byte ptr [eax+ebx] .text:08049BDF lea edx, [eax-0Ch] .text:08049BE2 mov edi, edx .text:08049BE4 .text:08049BE4 loc_8049BE4: ; CODE XREF: _ZN5TxMsg10getMessageESs+51Bj .text:08049BE4 cmp cl, 75h .text:08049BE7 jz loc_8049B60 .text:08049BED cmp dword ptr [edx+8], 0 .text:08049BF1 js short loc_8049C0A .text:08049BF3 lea eax, [ebp+var_28] .text:08049BF6 mov [esp+228h+var_228], eax .text:08049BF9 call __ZNSs12_M_leak_hardEv .text:08049BFE mov eax, [ebp+var_28] .text:08049C01 movzx ecx, byte ptr [eax+ebx] .text:08049C05 lea edx, [eax-0Ch] .text:08049C08 mov edi, edx .text:08049C0A .text:08049C0A loc_8049C0A: ; CODE XREF: _ZN5TxMsg10getMessageESs+541j .text:08049C0A cmp cl, 65h .text:08049C0D jz loc_8049B60 .text:08049C13 cmp dword ptr [edx+8], 0 .text:08049C17 js short loc_8049C30 .text:08049C19 lea edx, [ebp+var_28] .text:08049C1C mov [esp+228h+var_228], edx .text:08049C1F call __ZNSs12_M_leak_hardEv .text:08049C24 mov eax, [ebp+var_28] .text:08049C27 movzx ecx, byte ptr [eax+ebx] .text:08049C2B lea edx, [eax-0Ch] .text:08049C2E mov edi, edx .text:08049C30 .text:08049C30 loc_8049C30: ; CODE XREF: _ZN5TxMsg10getMessageESs+567j .text:08049C30 cmp cl, 6Fh .text:08049C33 jz loc_8049B60 .text:08049C39 cmp [ebp+var_1FC], 1 .text:08049C40 jz loc_8049DF8 .text:08049C46 add ebx, 1 .text:08049C49 cmp [edx], ebx .text:08049C4B mov [ebp+var_1FC], 1 .text:08049C55 jg loc_8049B82 .text:08049C5B nop
__ZNSs12_M_leak_hardEvってなんｄ（ｒｙ
連続cmpっぽい処理の流れになってるので、ちゃんと最適化されてる。
