AtCorder Regular Contest 082 を受けた感想 - プログラミング上達したい人が書くブログ

筆者の結果

E問題無理。

C問題解法について

　ソースコードは以下のようになります。

　考えた解き方としては、ある数字の個数と前後数字の個数を足した数の最大値が答えとなると考えました。例えば、入力が1 3 5 8 2 7 7 6としたとき、1-3の個数が3、2-4の個数が2、...、6-8の個数が4となり、最大値が4となり最終的な答えが4となります。

　ソースコードの内容として、配列nは、それぞれの数字の個数を入れる役割を果たしています。例えば、5の個数であればa[5]の値で表します。

　最初のfor文は入力部分です。vector配列aに入力値を入れている。

　次のfor文では、値を調べてその値の個数に1足している。＊よく考えたら、この部分入力部分でもできるから実質無駄なことしてます。

　それ以降のソースコードでは、毎回連なっている3つのnの足した数をもとめて、それの最大値を出しています。

#include<iostream>
#include<vector>

using namespace std;

int main(){

  vector <int> a;
  int N,b;
  int num[100000] = {0};
  cin >> N;
  for(int i = 0;i < N;i++){
    cin >> b;
    a.push_back(b);
  }
  for(int i = 0;i < N;i++){
    num[a[i]]++;
  }

  int max = num[0]+num[1]+num[2];
  for(int i = 1;i < 99998;i++){
    int m;
    m = num[i]+num[i+1]+num[i+2];
    if(max < m){
      max = m;
    }
  }

  cout << max << endl;
  
}

D問題解法について

　ソースコードは以下に張り付けておきます。はい、長いです。申し訳ありません。

　考え方としては、「pi = i」となるものが1つ続いているか、2つ続いているか、3つ続いているかに分けているものです。

　例えば、入力が1 3 2であった場合続いているものは1つなので、次のやつと入れ替えればいいのです。また、入力が1 2 4 3のときは、2つ続いていますが、これも1と2を入れ替えればいいのです。では、入力が1 2 3のときはどうするかというと、２回適当に入れ替えれば大丈夫です。

　このように、各部分をパターン認識のような考え方をして回数を求めました。

　ソースコードを解説すると、ごり押ししてます。if文1個続いたら、2個続いたら、3個続いたら、ほかには見たいな感じに場合分けしています。注意すべきは、問題が1から始まるのに対して、配列が0から始まることです。

#include<;iostream>
#include<algorithm>
#include<vector>

using namespace std;

int main(){
  vector <int> a;

  int N;
  cin >> N;
  for(int i = 0;i < N;i++){
    int b;
    cin >> b;
    a.push_back(b);
  }
  int sum = 0;
  for(int i = 0;i < N;i++){
    if(a[i] == i+1){
      if(a[i+1] == i+2){
	if((a[i+2] == i+3) && (a[i+3] != i+4)){
	  sum = sum+2;
	  int swap;
	  swap = a[i];
	  a[i] = a[i+1];
	  a[i+1] = swap;
	  swap = a[i+1];
	  a[i+1] = a[i+2];
	  a[i+2] = swap;
	  i = i + 2;
	  
	}
	
	else{
	  int swap;
	  swap = a[i];
	  a[i] = a[i+1];
	  a[i+1] = swap;
	  sum++;
	  i++;

	}
      }
      else{
	int swap;
	swap = a[i];
	a[i] = a[i+1];
	a[i+1] = swap;
	sum++;
	i++;

      }
    }
  }
  
  cout << sum << endl;

}

今回の感想

　とにかくE問題レベルになると全く解けなくなります。550点くらいの問題を出してほしい...