愚直に有り得る組み合わせを試していったらMLE（メモリ制限超過）した。愚直過ぎた。悔しい。
解説
制約と問題の性質上、有り得るパターンを分けていけば探索の必要なくACできる。
2つより多く分かれることを考えなくてよく、分かれなかったものが存在する場合はAの中で最も大きい要素がLとなるはず。となれば昇順に並び替えても問題がない。
考慮すべきは「全て分かれた場合」と「分かれなかったものが存在する場合」の2通りのみ。
全て分かれた場合であれば偶数本になり、A1+An, A2+An-1… と足していってそれがLになる。
分かれなかったものが存在する場合であればL=Anとなるのでそれを省き、残ったもので「全て分かれた場合」と同様の手順を適用できる。
答えは昇順で出力しなければならないが、同じAを使って場合分けをする都合上、Lとなり得る2通りであるAnとA1+Anでは「An＜A1+An」以外の状況は考えられないので「分かれなかったものが存在する場合」→「全て分かれた場合」と出力するだけでよい。
そして、制約上どちらかが必ず答えとなるのでこの2通り以外を考慮する必要がないこともわかる。
感想
コンテスト終了後にだいぶ時間を掛けて解説を頭にぶち込んだ。
公式解説や解説放送のコードだと「全て分かれた場合」と「分かれなかったものが存在する場合」の2通りのみを考えて合致しないパターンをはじくように実装していたが、あり得るパターンをこれでちゃんと網羅出来ているのかを理解するのに苦戦した。実力が足りていない。
「全て分かれた」「分かれなかったものが存在する」の場合、これを順にX,Yとして同じAの配列を用いて考えると答えとなるLは必ずY<Xの関係になり、その上でどちらかが存在するか、両方が存在する場合のみ。どちらも存在しない場合は制約上考えなくてよい。
制約を踏まえると賢いコードだけど、特に入力例2みたいな「全て分かれなかった場合」はかなりグレーな通り方をしているように思える。公式解説のコード見て「それで通るの……？」ってなった。
で、公式解説の入力例2は実は「分かれなかったものが存在する」パターンに含まれる。
こちらでは全て割れた結果偶数になる必要があるが、手順通り分かれなかったものを省くと残りは0、つまり偶数になる。要素数が0になると残りの分かれた分を考慮する必要が無いので、初めに置いたL=Anがそのまま答えとして出力できる。
要約すると、とにかく制約に気を付けること。あと求める答えであるLが実質2通りだけになることが肝。答えが3通りかと思ったら、2通りでした～。チクショ～！！！！
コメント