はじめに
2完だった。ARCは考察が大事だと思うので、その整理と解説を兼ねて書く。
A - Three Cards
問題
当時の考察
「数字を連結する」という操作が発生することを考えると、無理にintにするより、
文字列のままのほうが扱いやすそうだな、と思って文字列のまま考え始めた。
「出来上がった数字が一番大きくなる」を文字列として考えると、
まず、文字数が最も多くて、次に辞書順で最も遅いものである。
※なお、辞書順で遅い≠文字列が長いではないので注意が必要である。
>>> "2" < "12"
False
これは材料となる数字も同じなので、文字長順→辞書降順でソートする。
これの上位3つを上位順にくっつければ答え、と思ったらWAした。
このままだと、上位３つで桁が異なるケースで、桁数が大きいが先頭行の数字が小さい場合に問題になる。
具体的には、入力が下記のケースにおいて、
3
9 111 21
911121が最も大きくなるが、桁順が優先でソートされると111219になってしまう。
よって上位3個抽出した後に、さらに辞書降順にソートした上で結合するようにした。
2022/8/21 8:40 追記
再度提出したらafter_contestでWAがでた。
3個の候補を全探索してベストを探す実装に変更。
AC提出
B - Plus and AND
問題
当時の考察
まず、M回の操作の使いどころについて考える。
ANDの最大値ということを考えると、上位bitを立てずに操作を温存して下位bit全てを立てたとしても、出来上がる値は改善することはない。
例:1000 > 111
従って、上位桁から順に操作を行えばよい。
また、操作はKより多い要素に対しても行うことができるが、要素選択に選ばない要素に操作をすることは無駄である。よって、一度操作および最後の選択対象の要素を決めた後は、それ以外の要素は忘れて、決定した要素のみに操作を行うようにすればよい。
さて、これらを踏まえてとりあえず実装を始めた。
上位bitから見ていくが、場合分けとして、
- 元からK個以上着目するbitが立っている時
- 立っていない時
A. K個以上bitが立つように要素に加算できる時
B. 操作回数が足りず加算できない時
が考えられる。
1.の時、そもそも操作が必要ないので、回答のbitに含めることができる。また、該当bitが立っている要素は、選択対象の候補になる。逆に該当bitが立っていない要素に関しては、選択対象にはなりえないので、処理対象から外してよい。
2.の時、補充するために必要な操作数を数えよう。この操作対象の要素は元の値が大きければ操作回数を削減できるので、現在の着目bitより下のbitを見たときに、数字が大きい値ものから上位K個だけを見てあげればいい。（実装上は、全体のbit走査毎にに上位bitは都度消して降順ソートしているので、上位K個を見ている）
2-Aの時、累積の操作回数を合算し、後続の2-A,Bの判定に利用する。
なお、操作後の要素は、着目bitより下は0埋めされたものになる。（実装上は0、すなわち上位も含めて0にしている）
AC提出
309msでコンテスト時pythonだと最速だった。
たぶん計算量は、各bit走査O(log(A)× 要素のソートO(NlogN) = O(N logN logA)で公式解説より速そう。
Aのbit数に依存したbitマスクをしてるので、結局 O(N logA (logA+logN))っぽい。（やりたいことは単一bitを0にしたいだけだけど）
更にK個より多いのは対象から外すとかしているので、枝切りされて定数倍にも効いているっぽい。
違ってたら教えてください。