Toy と帽子と ADP BE

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

AtCoder Beginner Contest 221

4完。落ち着いてやる、という当初の目標は達成できたかなー。

各問題

A - Seismic magnitude scales

32 ^ (A - B)ですね。

B <= A っていう制約、プチフリーズしてしまうのでやめてほしい・・・。

B - typo

まず、SとTが同じかどうかチェックします。(重要)

その後、Sのスワップを端から順に試します。

C - Select Mul

まずNは文字列で受け取っておきます。

ビット全探索で、Nをビットが立っている桁と立っていない桁に分けます。分けた後、それぞれを降順にソートして数値に変換するとお互いの最大の数が得られます。あとはそれらを掛けます。

掛けて得られた数のうちで最大のものが答えです。

D - Online games

座標圧縮してからimos法でもよいですし、mapで管理してimos法と同様に和を管理させるようループ処理を書くでもよいです。

自分は後者でやりました。

E - LEQ

小さい数から見ていくとかやってみましたが、そんなことをしても愚直に計算した場合は結局最悪ケースの計算量は変わらないのでだめ。

fenwicktreeとかで使用済みの位置を管理するとかも考えたのですが、欲しいのは数じゃなくて場所だしなぁ、とか。

わからんわからんとなっているうちにコンテストが終わってしまいました。

F - Diameter set

数分考えたのですがなにもわからず、順位表を見ておとなしくEに戻りました。

まとめ

9月はなんと一度も水パフォを取れていなかったので、一月ぶりに水パフォ取れてほっと一安心です。AGCまでにはレートも水色に戻したい。

f:id:mdstoy:20211002231712p:plain