geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

ABC230 参加記録

ABC 貪欲法 床関数

コンテスト中AC:A〜D
Eを解説ありで解きました。

 

 

A - AtCoder Quiz 3

公式解説より、setfillとsetwでleading zerosを実現できるらしいです。

 

B - Triple Metre

簡潔の判定方法が思いつきませんでしたが、公式解説のように、modの値で判定できるのですね。

 

C - X drawing

a=max(1-A,1-B),b=min(N-A,N-B)

c=max(1-A,B-N),b=min(N-A,B-1)

とします。

 

マスの座標からkを逆算してkが条件を満たすか考えます。マス(i,j)が黒となる条件は

1つ目が、

i-Aとj-Bが等しく、かつ、k=i-Aとした時にa\leq k\leq bを満たす

と言い換えられます。

同様に2つ目は、

i-AとB-jが等しく、かつ、k=i-Aとした時にc\leq k\leq dを満たす

と言い換えられます。

 

各マスについていずれか一方を満たせば黒となるので、これを各マスについて判定していけば良いです。

提出コード

 

D - Destroyer Takahashi

類題を見たことがあるので、典型かと思います。

・今壊れていない壁の中で最もRが小さい壁について、Rでパンチする。

が最適な貪欲法です。

これが最適な理由は、

・これより後ろでパンチすると、この壁を壊せない。

・この壁を壊したい時、これより前でパンチするよりもRでパンチした方がより後ろの壁まで破壊できる。

ためです。

 

実装としては、

まず、壁を、Rをキーとして昇順にソートしておきます。

最後にしたパンチが届く範囲の最も右の列をxとし(便宜上初期値は0)、i番目の各壁について、

・L_i\leq xならその壁は既に破壊されているので何もしない。そうでなければ、R_iでパンチし、x\leftarrow R_i-D+1と更新する。

としていけば良いです。

提出コード

 

E - Fraction Floor Sum

Web公式解説を見ました。

説明のため、iに対応する\lfloor \frac{N}{i}\rfloorをiのスコアと呼びます。

例えば、N = 16として、i=1〜Nと対応するスコアを並べてみます。

 

\mathtt{\ 1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 8,\ 9,10,11,12,13,14,15,16}
\mathtt{16,\ 8,\ 5,\ 4,\ 3,\ 2,\ 2,\ 2,\ 1,\ 1,\ 1,\ 1,\ 1,\ 1,\ 1,\ 1}

 

これを見るとi=\sqrt{N}で、スコアは \sqrt{N}となっています。

このように、\sqrt{N}より大きいスコアは、対応するiが(おおよそ)\sqrt{N}くらいまでです。したがって、この時のスコアの合計はiを1から順に問題の通りスコアを計算していくことで、O(\sqrt{N})で求められます。

 

次に、\sqrt{N}以下のスコアは、スコアから対応するiの範囲を逆算することで、その合計をO(\sqrt{N})で求められます。

 

スコアkからiの範囲を逆算するときの計算は公式解説にもありますが、

\frac{N}{k+1}\lt i \leq \frac{N}{i}
となります。

 

まとめると、

スコアがi=\sqrt{N}より大きい部分はiから、

スコアがi=\sqrt{N}以下の部分はスコアから、

その合計を求められます。

提出コード