🗂

【ABC261】「A - Intersection」のメモ

2022/07/24に公開

AtCoder

競プロ

tech

概要

AtCoder Beginner Contest 261のA問題で異様に苦労したので、もうちょっとわかりやすいやり方でやり直してまとめてみます。

コンテスト中に書いたコード

数字をこねくり回しながらひねり出したコードですが、説明しろと言われてもよくわからないです…

#include <bits/stdc++.h>
using namespace std;

int main() {
    int L1, R1, L2, R2;
    cin >> L1 >> R1 >> L2 >> R2;

    if(R1 > L2 && L1 < R2) {
        if(R1 < R2) {
            if(L1 > L2) {
                cout << R1 - L1 << endl;
            } else {
                cout << R1 - L2 << endl;
            }
        } else if(L1 <= L2) {
            cout << R2 - L2 << endl;
        } else {
            cout << R2 - L1 << endl;
        }
    } else {
        cout << 0 << endl;
    }
}

考察のやり直し

そもそも変数が4つもあって、それらの組み合わせを考えるのはかなりしんどいです。
しかし、点ではなく「線」で考えれば、変数は2つしかないかのように考えることができます。
実際に線を描けばさらにわかりやすくなります。
あまり綺麗じゃないですが描いてみたのが以下です。

1～5は青い線は止まっていて、赤い線が左から右に向かって移動していく過程を描いたというイメージです。（絵が下手なのでそう見えないかもしれませんが、そうなのです）
そのように考えると、赤い線と青い線の位置関係は5パターンになります。
実際には逆パターンもあるため、赤と青の位置を反転させたのが6～10になります。
先端同士が被るパターンは実装時に吸収すると考えると、位置関係は全10パターンということになります。

1、5、6、10は全く被らないパターンで0を出力すればいいので、真っ先に除外して考えるとよさそうです。
なのでそれらを除外した残り6パターンを愚直に実装すれば解けそうです。

書き直したコード

図を眺めながら書いたのが以下です。
よく見たら2と9、また4と7は同じなので0パターンを除外した残りは4パターンまで減りました。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int L1, R1, L2, R2;
    cin >> L1 >> R1 >> L2 >> R2;

    if(R1 < L2 || R2 < L1) {
        cout << 0 << endl;
    } else {
        if(L1 < L2 && L2 <= R1 && R1 <= R2) {
            cout << R1 - L2 << endl;
        } else if(L2 <= L1 && R1 <= R2) {
            cout << R1 - L1 << endl;
        } else if(L2 < L1 && L1 <= R2) {
            cout << R2 - L1 << endl;
        } else if(L1 <= L2 && R2 <= R1) {
            cout << R2 - L2 << endl;
        }
    }
}

スマートではないですが、スマートに書こうとしてバグらせるくらいならこのほうがマシです。

ここまでで20分くらいでした。Aにしては時間かかりすぎですが本番はもっとヤバかったので、このやり方を本番でやりたかったですね…

教訓

できるだけ変数は減らして考えるようにする
頭で考えてわからなければ図を描く

追記

配列を2つ作って共通部分を数えればいいのではとTwitterで教えてもらいました。
たしかにそのほうがずっと楽ですね！そうすればよかったです！！！

サクッとPythonで書いてみたのがこちら。

L1, R1, L2, R2 = [int(i) for i in input().rstrip().split()]
red = {i for i in range(L1, R1 + 1)}
blue = {i for i in range(L2, R2 + 1)}

print(max(0, len(red & blue) - 1))

C++だとこんな感じ。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int L1, R1, L2, R2;
    cin >> L1 >> R1 >> L2 >> R2;

    set<int> red;
    for(int i = L1; i <= R1; i++) {
        red.insert(i);
    }
    set<int> blue;
    for(int i = L2; i <= R2; i++) {
        blue.insert(i);
    }
    vector<int> v;
    set_intersection(red.begin(), red.end(), blue.begin(), blue.end(), back_inserter(v));

    cout << max(0, ((int)v.size()) - 1) << endl;
}

概要

コンテスト中に書いたコード

考察のやり直し

書き直したコード

教訓

追記

Discussion