見出し画像

627(Div.3)【B問題の反省とD問題の復習】いい加減、二分探索の問題はできないといけないよなぁ

3月12日に、海外の競技プログラミング「Codeforces」で開催された「Codeforces Round#627(Div.3)」に参加した。

【今回の結果】
     順位:5464 位(参加者:約 7578 名 上位 72 %くらい)
    レート:1155(前回:1175 前回比:-20)

全6問出題され、A,B,C問題の3問をpretestでACになったが、D問題を考えている途中で終わってしまった。最終的には、B問題でHackされ、2AC。B問題は少し考察が足らなかったな。D問題もなんとなくできそうだなと思っていたのだが、できなかったなぁ。ということで、今回は以下の2つを行う。

1.B問題でHackされたことの反省
2.D問題の復習

【B問題】全部同じ数値の場合を想定していないからHackだった

問題文は以下のリンクをご確認ください。

【概要】
数列が与えられる。
この数列から並び順を変えずに3つの数値を抜き出す。
抜き出した3つの数値が回文になっているものを作ることができる場合はYesを、できない場合はNoを出力せよ。

このような感じの問題。
Hackされたコードは以下の通り。

#include <bits/stdc++.h>
using namespace std;
int main() {

 int t;
 cin >> t;

 while (0 < t) {

   int n;
   cin >> n;

   vector<int> a(n);
   for (int i = 0; i < n; i++) {
     cin >> a[i];
   }

   string answer = "NO";

   vector<int> count(5010, -1);

   for (int i = 0; i < n; i++) {
     int a_ = a[i];
     if (count[a_] < 0) {
       count[a_] = i;
     } else {
       if (1 < i - count[a_]) {
         answer = "YES";
         break;
       } else {
         count[a_] = i;
       }
     }
   }

   cout << answer << endl;

   t--;
 }

 return 0;
}

ざっくりといえば、「ある数値が2回目に現れたら、1回目に現れた場所から2以上離れていれば回文は作れると判断する」という方針で実装したものです。しかし、この方針だと例えば、1,1,1の数列を考えると、そのまま、1 1 1 を抜き出して、回文を作ることができるが、上記のコードではNOとなる。う〜ん。見逃していたな。

ということで方針を、「ある数値が数列で何番目で現れたのかを配列で持ち、配列の長さが3以上なら回文は作れる。配列の長さが2の場合は、それらの場所が2以上離れていれば回文は作れる。それ以外はダメ」という感じに変更した。

変更してACしたコードは以下の通りです。

#include <bits/stdc++.h>
using namespace std;
int main() {

 int t;
 cin >> t;

 while (0 < t) {

   int n;
   cin >> n;

   // 例えば、2は数列の[1,4,7]にあったという感じで管理する
   map<int, vector<int>> count;
   for (int i = 0; i < n; i++) {
     int a;
     cin >> a;
     count[a].push_back(i);
   }

   string answer = "NO";

   for (auto item:count) {
     // 配列の要素が3以上だと回文は作れる
     // 配列の要素が2だと間に1つ以上の他の数値が必要
     if (3 <= item.second.size()) {
       answer = "YES";
       break;
     } else if (2 == item.second.size()) {
       if(1 < (item.second[1] - item.second[0])) {
         answer = "YES";
         break;
       }
     }
   }

   cout << answer << endl;

   t--;
 }
 return 0;
}

【D問題】二分探索の復習

問題文は以下のリンクをご確認ください。

【概要】
あるトピックについて学校で話し合う。
n個のトピックがあって、i番目のトピックはa_iの先生たちが興味を持っていて、b_iの生徒たちも興味を持っている。
n個のうち2つトピック(iとj)を選び、良い組み合わせを作りたい。
ここでの良い組み合わせとは、先生の興味(a_i + a_j)> これらの生徒の興味(b_i + b_j)になる2つのトピックの組み合わせである。
作ることができる良い組み合わせの個数を出力せよ。

このような感じの問題。

各トピックは以下の2つに分類できる。

1.先生の興味と生徒の興味の差が0を超える
2.先生の興味と生徒の興味の差が0以下

1.のトピックが2個の場合は必ず良いトピックになる。
2.のトピックが2個の場合は必ず良いトピックにならない。
1.と2.が1個ずつの場合は、1.の差が大きい場合は良いトピックになる。

したがって、各トピックの差を昇順に並び替えて、差が小さい順から順番に、1.のトピックだったら、0 - 「1.のトピックの差」+ 1 のトピックが何個あるかを数える。昇順に並んでいるので、二分探索を使うといい。

以上の考え方をもとに実装し、ACしたコードは以下の通りです。

#include <bits/stdc++.h>
using namespace std;
int main() {

 int n;
 cin >> n;

 vector<int> a(n);
 for (int i = 0; i < n; i++) {
   cin >> a[i];
 }

 vector<int> b(n);
 for (int i = 0; i < n; i++) {
   cin >> b[i];
 }

 // 差の配列を作る
 vector<int> d;
 for (int i = 0; i < n; i++) {
   int c = a[i] - b[i];
   d.push_back(c);
 }

 sort(d.begin(), d.end());

 long long answer = 0;
 
 for (int i = 0; i < n; i++) {
   
   // 0以下は無視
   if (d[i] <= 0) {
     continue;
   }
   // 差がd[i]の場合、-d[i]+1以上の数が何個あるかを数える 
   int position = lower_bound(d.begin(), d.end(), 0 - d[i] + 1) - d.begin();

   answer += i - position;

 }

 cout << answer << endl;

 return 0;
}

二分探索は他の問題でも何度も出題されていて、できていなくて反省ばかりしているので、いい加減もうできないといけないよなぁ、と反省している。

この記事が気に入ったら、サポートをしてみませんか?気軽にクリエイターを支援できます。

ありがとうございます!
三重県伊勢市でiOS・AndroidアプリのUX設計・UIデザイン・実装、Webサイト、Webアプリの情報設計、UIデザイン、実装を行なっています。また、競技プログラミングに参加したり、読書をしたり、2羽の文鳥と遊んだり、写真を撮ったり、洋菓子を作ったりしています。