C
配列aを配列bにまとめられるか考える。
しゃくとり法みたいに、sumがb以下になるまで
足していき、sumじゃなかったらNO。
sumだったら、それをLinkedListに突っ込んで、
一番大きい値から隣を食べていく。
このとき、ListIteratorを使えば削除と挿入がスムーズ
(のはずなのだけれど実装が大変で1時間かかった)。
コンテスト時にはSystem Testで落ちる。
原因が分からなかったが、同じ実装をしているっぽい
とーらすさんに聞いたらお返事をいただけた。
@arukuka 色々あるらしいですが,わたしのは少なくともこれ https://t.co/lHSBeM4dOP で落ちます
— とーらす (@torus711) 2016年10月31日
配列aを使いきれているかチェックしたらAC。
D
コンテスト中には実装しきれなかったが、
方針は合ってそうで、実際ACした。
a, b, cの中で一番小さい値が
出来上がる球体の半径となる。
まとめられるかどうかを判定するときに、
いちいち全部見ていたらO(N^2)になってしまう。
ここは二分探索を用いる。
とは言えど、2つの長さが同じで、かつ残り1つが
最大の要素を取り出してくるにはどうするか。
これは、Comparatorを定義して、優先順位を変えてあげるものを
用意しておけばいい。
ここで、(2, 3, 4)に合わせるものを探索するときは、
- (inf, 3, 4)
- (3, inf, 4)
- (3, 4, inf)
をそれぞれキーにして、優先順位の異なる3つのComparatorで
binarySeachを呼ぶ(infになっているところが一番優先度が低い)。
自分自身を選んでいないことに注意すれば、
これがその直方体にとって最良の選択になる。
max を更新するときは、着目している配列の中で
2番目に小さい長さと、1番目に小さい要素に結合した長さ
の小さい方を選んでくる必要がある。
これは、新しい配列の中で一番小さい値を探す操作と一緒。
これで全体でO(N long N)になった。
実装がかなり大変で、何度もバグらせてWAしたが、
無事ACできた。
Submission #21948334 - Codeforces
それにしても汚い。エレガントな解答はあるのだろうか。
順位は1111位で、レーティングが30増え1494(シアン在留)となった。
落ちなかった分よかったけど、青色は遠い。