AtCoder ARC031 感想

本日午後21時から22時半にて開かれたARC031に先ほど参加していましたが4問中1問しか解けませんでした()

 

解説見た後にB問題実装したらすぐに通ったので割りと悲しみを背負っています。。。

 

問題はこちら

Welcome to AtCoder Regular Contest 031 - AtCoder Regular Contest 031 | AtCoder

 

A問題 名前

文字列を受け取って後ろからと前から進むもので比較。

  1.  
  2. using namespace std;
  3.  
  4. int main(){
  5.  
  6.     string str;
  7.  
  8.     cin>>str;
  9.  
  10.     for(int i=0;i<str.size()/2;i++){
  11.         if(str.at(i)==str.at(str.size()-i-1)){
  12.             continue;
  13.         }
  14.         cout<<"NO"<<endl;
  15.         return 0;
  16.     }
  17.     cout<<"YES"<<endl;
  18.     return 0;
  19.  
  20. }

A問題はすぐに出来ました。

 

B問題 埋め立て

これで詰まってしまいました()

すべての島から1マスずつ領域を伸ばしてあげて、全ての島の領域が重なった部分があれば答えみたいな感じで実装しようとしたのですが色々見落としなどがあり時間切れ・・・

解説を見た後に全探索で実装したのが以下のコードです。

  1. int main(){
  2.  
  3.     //a:盤面;
  4.     //state:島の番号を表す。;
  5.     //flag:盤面の領域探索済かどうか;
  6.     int a[12][12]; 
  7.     int state[12][12];
  8.     int flag[12][12];
  9.  
  10.     //stateCnt:島の数;
  11.     int stateCnt=0;
  12.  
  13.     //データ入力時受け取り文字列;
  14.     string str;
  15.  
  16.     //幅優先探索用キュー;
  17.     queue<int> x;
  18.     queue<int> y;
  19.  
  20.     //初期化;
  21.     for(int i=0;i<12;i++){
  22.         for(int j=0;j<12;j++){
  23.             a[i][j]=0;
  24.             flag[i][j]=0;
  25.             state[i][j]=0;
  26.         }
  27.     }
  28.  
  29.     //データ入力;
  30.     //x:a[i][j]=0
  31.     //o:a[i][j]=1
  32.     for(int i=0;i<10;i++){
  33.         cin>>str;
  34.         for(int j=0;j<10;j++){
  35.             if(str.at(j)=='x'){
  36.                 a[i1][j1]=0;
  37.             }
  38.             else{
  39.                 a[i1][j1]=1;
  40.             }
  41.         }
  42.     }
  43.  
  44.     //u,v:埋立地座標;
  45.     //i,j:全探索座標;
  46.     for(int u=1;u<=10;u++){
  47.         for(int v=1;v<=10;v++){
  48.  
  49.         stateCnt=1;
  50.         int breakFlag=0;
  51.         if(a[u][v]==1)continue;
  52.  
  53.         a[u][v]=1;
  54.  
  55.         for(int i=0;i<12;i++){
  56.             for(int j=0;j<12;j++){
  57.                 flag[i][j]=0;
  58.                 state[i][j]=0;
  59.             }      
  60.         }
  61.  
  62.         for(int i=1;i<=10;i++){
  63.             for(int j=1;j<=10;j++){
  64.                 breakFlag=0;
  65.                
  66.                 //探索開始;
  67.                 if(a[i][j]==1 && flag[i][j]==0){
  68.                     x.push(i);
  69.                     y.push(j);
  70.                     flag[i][j]=1;
  71.                     state[i][j]=stateCnt;      
  72.                     while(x.size()!=0){
  73.                         breakFlag=1;
  74.                         int topX=x.front();
  75.                         int topY=y.front();
  76.                         x.pop();
  77.                         y.pop();
  78.                         if(a[topX-1][topY]==1&&flag[topX-1][topY]==0){
  79.                             x.push(topX-1);
  80.                             y.push(topY);
  81.                             state[topX-1][topY]=stateCnt;
  82.                             flag[topX-1][topY]++;
  83.                         }
  84.                         if(a[topX1][topY]==1&&flag[topX1][topY]==0){
  85.                             x.push(topX1);
  86.                             y.push(topY);
  87.                             state[topX1][topY]=stateCnt;
  88.                             flag[topX1][topY]++;
  89.                         }
  90.                         if(a[topX][topY1]==1&&flag[topX][topY1]==0){
  91.                             x.push(topX);
  92.                             y.push(topY1);
  93.                             state[topX][topY1]=stateCnt;
  94.                             flag[topX][topY1]++;
  95.                         }
  96.                         if(a[topX][topY-1]==1&&flag[topX][topY-1]==0){
  97.                             x.push(topX);
  98.                             y.push(topY-1);
  99.                             state[topX][topY-1]=stateCnt;
  100.                             flag[topX][topY-1]++;
  101.                         }
  102.                     }
  103.                     if(breakFlag==1){
  104.                         stateCnt++;
  105.                     }
  106.                 }
  107.             }
  108.         }
  109.         //島の数が1個のみカウントされた場合はYESし終了;
  110.         if(stateCnt==2){
  111.             cout<<"YES"<<endl;
  112.             return 0;
  113.         }
  114.         //埋め立てた場所を元に戻す。;
  115.         a[u][v]=0;
  116.         }
  117.     }
  118.     cout<<"NO"<<endl;
  119.  
  120.  
  121.     return 0;
  122.  
  123. }

C問題、D問題は後で見てみます(白目)