Codeforces Round #378 (Div. 2) A B C D

codeforces.com

A

母音間の距離の最大値を求める。
初期indexを-1にして、末尾に番兵の'A'を置くと楽

Submission #21920570 - Codeforces

B

全体のsumを取っておいて、列iを右左入れ替えたときに
最大値を更新できるか舐めていく。

Submission #21924549 - Codeforces

C

配列aを配列bにまとめられるか考える。

しゃくとり法みたいに、sumがb以下になるまで
足していき、sumじゃなかったらNO。
sumだったら、それをLinkedListに突っ込んで、
一番大きい値から隣を食べていく。
このとき、ListIteratorを使えば削除と挿入がスムーズ
(のはずなのだけれど実装が大変で1時間かかった)。

コンテスト時にはSystem Testで落ちる。
原因が分からなかったが、同じ実装をしているっぽい
とーらすさんに聞いたらお返事をいただけた。

配列aを使いきれているかチェックしたらAC。

Submission #21948689 - Codeforces

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(シアン在留)となった。
落ちなかった分よかったけど、青色は遠い。