読者です 読者をやめる 読者になる 読者になる

ichirin2501's diary

いっちりーん。

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' )

上記のC++コードのアセンブリコードが、

.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
いや、それ以前に、さすがにこれはないんじゃないのwww
無駄な処理多くなイカ?
最適化オプションで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ってなんd(ry
連続cmpっぽい処理の流れになってるので、ちゃんと最適化されてる。