Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

AtCoder Beginner Contest 134

AtCoder c++ competitive programming ABC

ABCEの4完。Dはバグが取り切れずー。

各問題

A - Dodecagon

問題文に沿って、3 * r * r を計算するだけです。

こんなシンプルな問題が出たの、久しぶりでは？

B - Golden Apple

一人の監視員が監視できる本数は2 * D + 1です。そこからN本の木に対して何人監視員が必要になるかを割り算で求めるだけです。答えを切り上げることに注意。（つまり、intでの/除算が切り捨ての言語はちょうど割り切れる時に気をつけないといけないことに注意。）

え、これA問題でもおかしくないのでは？今回簡単セットなのかな？

C - Exception Handling

数列の中の最大値を、複数の項が持っている場合、いずれかの最大値を抜いても他の最大値が残ります。なので、どの項を除こうが最大値は常に同じ（数列中の最大値）です。 最大値が単独の場合、その項を抜いた場合だけは二番目に大きい数が最大値になります。

最大値とその項番は、入力を取得する時に容易に保存しておけますし、二番目に大きい数は数列をソートすれば容易にとれます。（editorialの方針1もその方法ですね）

D - Preparing Boxes

iが大きい方から見ていけば、すべての箱に対してボールを入れるか入れないかを決定することが可能です。 D問題なのに計算量についてはそれで問題ありません。i == 1のときはN個見ないといけませんが、上半分については自分自身しか見る必要がありませんからね。

とか言いつつ、私は実装をバグらせてしまい、コンテスト中にデバッグしきれませんでした。on_

（追記）

デバッグした結果はこれでした。

そんなミスするか常識的に考えて！？on_

E - Sequence Decomposing

editorialにはLISってありましたが、私はそれ系の知識を持ち合わせていないので、ごりごり実装しました。（勉強しないと）

説明はしにくいんですけど、実装は単純なのでとりあえず見てください。（えー）

https://atcoder.jp/contests/abc134/submissions/6467438

要するに、待ち受けしている数字に繋げられるなら繋げる（その際できるだけ大きい方に繋ぐ）、そうでなければ自身を新しい待ち受けにする、を繰り返して、最終的に待ち受けしている数字の個数が答え、としました。

（追記：YouTube解説と全く同じ考え方でした！　なんか嬉しい）

ところで自分はvectorで実装したんですけど、こういうこときにmultisetを使うんですね。

あと、ソート済みのvectorに対しては、push_backして改めてsortするより、挿入位置を探してinsertするほうが速いということを身をもって知りました。

ダメな実装

            if (x == q.begin()) {
                q.push_back(a);
                sort(ALL(q));
            } else {
                q.erase(x - 1);
                q.push_back(a);
                sort(ALL(q));
            }

ましな実装

            if (x == q.begin()) {
                auto x = upper_bound(ALL(q), a);
                q.insert(x, a);
            } else {
                q.erase(x - 1);
                auto x = upper_bound(ALL(q), a);
                q.insert(x, a);
            }

F - Permutation Oddness

まったく考察できず。

まとめ

  • コンテナに関する知識をアップデートした
  • LISとかそういう系統の知識が全く無いので勉強しないといけない
  • 最後慌てすぎた・・・

まあ一月ぶりにHighestを（2点だけですが）更新できたので、とりあえずよし。

f:id:mdstoy:20190721010501p:plain