脳log[20221002]

2022年10月02日 (日) [AtCoder] 今日は ARC149。B 問題「Two LIS Sum」(緑 diff) のみの１完だったのでそれについて書く。並び順が連動する A、B ２つの順列を好きに並べ替えて A の LIS と B の LIS の長さの和を最大化する問題。最初はソートの問題かなと思った。左下から右上に向かって点(A,B)を並べて、双方にとっていい感じに点を選んでいくのかなと。サンプルが合わせられないので次は DP かなと思った。ある点を選んだとして、次に選んで LIS を増加させられる点は第Ⅰ象限にあたる位置にしかないので。これも実は最初の解法と違いがなくサンプルが合わせられなかったので、次は先に A の LIS を最大化(N に等しい)したあとで B を最大化する方法を考えた。どうやって双方のバランスを取るかを考えているうちに、常にあちらを立てればこちらが立たずが成り立つことに気がついた。つまり、A のソート列を壊して(LIS(A)を１減らして)増やせる B の LIS もまた１が上限なのだから、手を入れる意味がない。A または B をソートした後で他方の LIS をすれば答えが出る。■提出 #35352966 (AC / 180 Byte / 501 ms)。今日はこれで終わり。解説を見たらすること自体は簡単なので、ネタバレ前に通せて良かった。■時間内には解けなかった A 問題についてはね……。XXXXXXX が M の倍数であるとはどういうことか、X、XX、XXX……と累積的に求めていった余りが０になることだ、ということがそもそもわからなかった。余りが０なら倍数だということがわからなかった。わからないはずがないと思うんだけど、M が素数か合成数かでなんか違いがあるのかなーとかぼんやりしたことを考えていた。そういう日もある(そういう日そうでない日の割合、つきつめて、そうでない日の存在については何も述べていない)。