—2025/04/09
Javaばばは家事以外に時間たっぷりを持っている、今日Atcoderの９１回目を挑戦した。
結果は
C問題には、一回目の提出はバッグを出だ、なぜNGになったのを調べた。
問題自体はそれほど難しくなかった、仲良し数字ペアの最大個数を求めること。
具体的に、N個の(X,Y)座標AとN個の(X’,Y’)のB座標がある、そのうちX<X’又Y<Y’という仲良し数字ペアが最大何組を求める問題。
そのため、最初思案したのは以下の例を対応できる方法、
3 2 0 3 1 1 3 4 2 0 4 5 5
３組のA座標(2,0),(3,1),(1,3) と３組のB座標(4,2),(0,4),(5,5)の内、仲良しペアの個数は何個？
まず、A、B座標をそれぞれをソーティング昇順して、B座標の内にA座標（1,3）のX（1）より大きいの最初の座標(4,2)を対象にして、Y座標を比較、3は2より大きいなので、該当ペアではない、次へ探し、（5,5）を対象にして、条件を満たす、ペアとしてカウントする。
このようにロジックを組みました。
以下のようの構図になっている、
その答えは２組で、正解だ。
実際ソースを上がって見ると、バグだ。
以下の例を通らない、
今までのロジックで実行した結果は以下のように、
その結果は４個
正解はこうだ、
５個は正解だ。
間違った考え方は、(0,0)の仲良しペアは(3,7)ではない、(9,1)です。つまり、Y座標０より一番大きいの最小値１を絞ること、それを気づいて、ロジックを再度考案し、うまく通った。
解説のように、これは有名な二部最大マッチングという算法だね。ばばにも勉強になった。
crossorigin="anonymous">