AtCoder Beginner Contest 163 - いろいろな記録

ABC163お疲れ様でした。コンテスト中にTwitterを見ないので、unratedに気づかずに100分やってました。

入水がかかっていたので焦っていたのもあるかもしれませんが、個人的にかなり反省の多いセットでした。パフォーマンスは1173で、ratedであればレートは若干下がっていました。いずれにせよ入水はお預けといったところでしょうか。

atcoder.jp

A - Circle Pond

実数に気をつけながら、 $2 \times r \times \pi$ を出力します。

テンプレートに long double PI = acos(-1) を入れていなかったので、今後は入れておこうと思います。

B - Homework

宿題はバラバラに与えられますが、合計値( $a$ とする)しか気になりません。

$a \geq n + 1$ なら $-1$ で、それ以外なら $n - a$ です。

宿題は計画的にやりましょう。

C - management

一つ目のやらかし。

問題を誤読して、その人以下の部下の数を全て出力する問題だと勘違いしていました。グラフとして考えれば良いからdfsだ、的なことを考えながら実装していたのですが、見るべきは「直属の部下」だけなので、各数字の出現回数を追うだけで問題ありません。

これで15分も溶かしてしまったのでガチで反省したほうが良いです。

D - Sum of Large Numbers

二つ目のやらかし。

「和としてあり得るものの個数のmod」を「和のmodとしてあり得るものの個数」と誤読して、10分ほど時間を無駄にしました。以下、ちゃんと題意を把握してから考えた考察です。

和として取りうる値を考えます。適当にサンプルを見ると、それぞれの和については「（ $10^{100}\times i$ ）+ （ $0$ から $n$ までの中の $i$ 個の整数の和）」となっていることがわかります。ここで、（ $0$ から $n$ までの中の $i$ 個の整数の和）が $10^{100}$ を超えることは到底ないので、この二つの項をそれぞれ一意に定めれば、和が一意に決まるということになります。

となると、（ $0$ から $n$ までの中の $i$ 個の整数の和）の取りうるパターン数を求めれば良いということになります。このうち最小のものは、 $0$ から $i-1$ までの和で、最大のものは $n-i+1$ から $n$ までの和です。そして、このあいだの値は全て、 $0$ から $n$ までの整数から $i$ 個ピックアップしてきたものの和として表すことができます。（例えば、最小値より $1$ 大きいものを作る場合は、 $k-1$ を $k$ にswapすれば良いです）

したがって、 $i$ 個選んだ時の和のパターンは、 $\sum_{l = n - i + 1}^{n} l + \sum_{l = 0}^{i - 1} l + 1$ となります。これを計算していては間に合わないので、数列の和の公式で計算すれば $O(1)$ で求まります。

最後に、 $k \leqq i \leqq n + 1$ なので、for文を回して合計を取れば答えが出ます。ちなみにこれも数列の公式で頑張ったら $O(1)$ でいけそうですが、「計算量は贅沢に使え」という教訓のもと、PCに計算させました。

誤読に気づいてからは10分ほどで捌けました。たらればは断じて良くないですが、CDの誤読で合計15分溶かさなかったとしたら、パフォーマンスは推定1500ほどでした。

僕は早解きが得意ではないのですが、その原因はこういった誤読やペナが多いです。それによりかなりのパフォーマンスを捨てているので、落ち着いて的確に問題を捌けるように注意したいです。

E - Active Infants

優先度を決めてはめていくという発想自体は合っていたのですが、dp使うとシンプルに捌けることがわかって感動しました。計算上黄diffとなっていますが、unratedで撤退した人が多かった結果diffが少し上がったのではないかと思っています。

dpかなり苦手（というか典型からあまり理解していない）なのですが、「1. その問題に対してdpが適用できることがわかる」「2. dpテーブルを的確に置く」「3. 漸化式を正確に立てる」「4. 適切な順でdpテーブルを埋める」という感じで、ハードルが数ステップある気がしています。僕の場合は1, 2の時点であまりできていないので、とりあえず色々問題を漁ってみようと思います。

次回も頑張りましょう。