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