CS Academyは動的配点（解いた人数によって配点が変化）など、コンテストの仕組みは面白いのですが、問題の不備などは結構多い印象です。
ただ、この一年の間にいつの間にかPyPyが使えるようになっていたのは嬉しかった。
このコンテストはCまでの三完。Dは実質的にはできていたのですが……。
コンテストへのリンク
As easy as ABC
配列Aが与えられ、そのうちのK個を+1したとき、中央値は最大いくつになるか、という問題。
元々の中央値をMとすると、答えは高々M+1（全部に+1したとしても中央値は1しか増えないので）。
結論としては、MがA中に何個含まれるかを調べれば良い。
K個以上あればそのK個に+1することで、中央値も+1される。
Boring Operation
$10^9/2$以上なら$10^9$から引く。
Cosmological Nightmare
連鎖的に点が現れたり消えたりする場合に注意。
逆に言えば、mod (x,y)$\in$ Vで一致している点の個数の偶奇を数えさえすればOK。
コンテスト中は、一回移動したらどうなるか……みたいなことを考え、それで上手くいかなかったために解法に気付いた。そのせいで、コンテスト中のコードは無駄が多いものになってしまっている。
Driveaway
コンテスト中、PyPyで提出してTLEでしたが、Python3で出せばACできました。PyPyだとheapq+tupleが遅いようです。注意。
また、JOI春合宿2018 J - 飴 (Candies)とほとんど同じ内容だったようです。
この問題のコードをそちらに合わせて修正すれば通りました。
ただ、この問題の方が若干解法に辿り着きやすいかな、と思います。
で、解法。
おおまかに言えば、隣り合った二要素の和が最大になるものに貪欲にvoucher（商品券？）を使っていくのがベスト。ただし、voucherでの減額は最高Kなので、min(二要素の和, K)の最大値をheapqに入れて管理する。
そして、単純に最大値を考えるのではなく、差分計算を考えなくてはダメ。
たとえば、サンプル2。
・1 3 7 7 3 1
なら、「3 7」「7 7」「7 3」のいずれかでK減額できる。たとえば、「7 7」にvoucherを使うと、残ったものは、
・1 3 3 1
次にvoucherを使うのは「3 3」なのだけど、これにvoucherを使ったとき減額できるのは3+3=6ではない。実際は「3 7 7 3」に二回voucherを使っていることに注意。
このとき、本当は「3 3」にvoucherを使っているのではない。でも、「7 3」「3 7」とvoucherを使えば「3 7 7 3」にvoucherを使うことは実現できる。
そして、減額される額は、3+7+7+3から、前回までで減額されていた額10を引いた10となる。
残りは、
・1 1
で、最後にこの二つに使う。
という感じでやればOK。
あとは、実装だけれど、その際、ある数の左右に何があるか、を管理できれば良い。
それを実現できるのが「隣接リスト」。それとも、「左右隣接リスト」と書いた方が良いのかな。（「隣接リスト」という名前は、以前Codeforcesでこういうデータ構造が必要な問題が出たときに、誰かがTwitterで使っていたのだけど、グラフ理論での隣接リストと意味的に対応しているのですね。なるほど。）
つまり、その点から一つ左にある要素、右にある要素を持っておき、要素が取り除かれるごとにそれを更新していく。
時々出てくるデータ構造なので、自分はしていないけど、ライブラリ化している人もいると思う。
0 件のコメント:
コメントを投稿