はじめに
コンテスト中に解けなかった AtCoder ABC386 "D - Diagonal Separation" の復習をしていて、最終的にバカな Runtime Error に悩まされたので、二度と繰り返さないようにするための備忘録です。
アホすぎるので自分以外には、おそらく学びはありません。ご了承ください。
書きたいコードの方針
この記事の主旨とは異なりますが、自分がどういうコードを書きたかったかという内容が伝わらないと意味不明なので、念のためどういう解法をコード化したかったかを記述しておきます
ぶっちゃけ公式解説を言い換えているだけで恥ずかしいので、折りたたんでおきます
問題文がグリッド表記なのでY軸を下に伸ばす形で図示します。入力で与えられるマスの座標の指定をX軸の昇順でソートして、X=0から順に評価していきます。
白マスの指定を「黒マスの指定に対する高さの制限」ととらえます。横スクロールのゲームでいうと、白マスの指定を下からせりあがってくる床みたいにイメージして、それ以降の黒マス指定が一つでも白マスにめり込んでいるとNG("No")、そうでなければOK("Yes")、というコードをC++で書こうとしました。（使用する言語が異なる以外、本当に公式の解説と同じです）
言われてみればめちゃくちゃシンプルなのに、コンテスト中の私は、これを黒と白の座標に分けてそれぞれソートして、二分探索をうまいこと組み合わせて座標の矛盾を判定しようと四苦八苦してましたねぇ。頭固い
前置き：最初に書いたコードで WA が出た話
方針が決まれば特に難しいことはないので、ざっくり書いたコードでサンプルACを確認後提出してみたところ、WA が 4件でました。
これは、入力をソートするときにXの値しか見ていなかったのが原因ですね。同じ列に対する黒マスと白マスの指定がある場合、白マスのほうを先に評価しないと、黒の矛盾が判定をすり抜けてしまうので、ソート時にそこを考慮する必要がありました。
struct Cell{
ll x;
ll y;
char color;
};
sort( vecCell.begin(), vecCell.end(),
[](const Cell & a, const Cell & b ){return a.x < b.x;});
WA x 4 のコード全体
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
struct Cell{
ll x;
ll y;
char color;
};
int main( void )
{
// 入力
ll N, M;
cin >> N >> M;
vector<Cell> vecCell;
for( int i = 0; i < M; ++i)
{
ll X, Y; char C;
cin >> X >> Y >> C;
Cell tmp = { X, Y, C};
vecCell.push_back(tmp);
}
// X の比較だけでソートしているのでNG
sort( vecCell.begin(), vecCell.end(),
[](const Cell & a, const Cell & b ){return a.x < b.x;});
ll minY_W = LLONG_MAX;
for( int i = 0; i < M; ++i)
{
if( vecCell[i].color == 'W')
{
minY_W = min( minY_W, vecCell[i].y);
}
else
{ // B
if( vecCell[i].y >= minY_W)
{
cout << "No" << endl;
return 0;
}
}
}
cout << "Yes" << endl;
return 0;
}
本題：WAをなおしたら別のケースがREになった話
ソート時に X の値が等しい場合は、'W' の要素が 'B'の要素より前にくるように比較してやればいいだけだな。
と判定部分を書き直して再提出してみたところ、前回WAだったケースが無事 AC になってめでたしめでたし、‥と思ったら、これまで通っていたケースがいくつか RE になりました。
自分の中で、『RE(Runtime Error) ≒ メモリの Out of bounds』という認識だったので、「そんな修正はしてないがっ！？」と半ギレになりながら、ループの回数やら確保しているメモリのサイズやらをチェックしましたが、問題らしきものはなし。
15分ほど浪費して、最終的に原因にいきついた時には、自分のアホさ加減に泣きそうになりました。
ようは 'W' が前にくれば他の要素はなんでもいいから、これでいいじゃん、と考えて書いたコードがこちらです。
sort( vecCell.begin(), vecCell.end(), [](const Cell & a, const Cell & b ){
if( a.x != b.x ) {
return a.x < b.x;
} else {
if(a.color == 'W') {
return true;
} else {
return false;
}
}
});
入力ミスとかではなく、本当にこれで動くと思ってたのがアホすぎですね。ちゃんと 'W' と 'B' を比較するコードに書き変えたら、普通に動きました。（わざわざ引き算になっているのは、不等式で書いたら、上のXを比較している式と干渉して気持ち悪かったので、一目で別の評価をしていると思えるようにするためです）
sort( vecCell.begin(), vecCell.end(), [](const Cell & a, const Cell & b ){
if( a.x != b.x ) {
return a.x < b.x;
} else {
return (a.color - b.color) > 0;
}
});
Compare 用の関数の要件
とはいえ、WA になるならわかるけど、なぜ RE？ というのがピンとこなかったので調べてみたところ、c++ の stl に対する compare 用のオブジェクトに対してはちゃんと厳密な要件があり、それに沿っていないと環境により例外を吐いたり、未定義動作になったりする、ということを学びました。
ちゃんと勉強せずに、動けばよかろうというコードを書き飛ばしているとこうなるという見本でした。以後気を付けます