little star's memory

競プロの参加記など

HHKB プログラミングコンテスト 2020

あたたまり~。

コンテストページ

以下は参加した感想。

A - Keyboard

大文字にするときに26を足したり引いたりしたら全然違う文字が出てきた。32が正しい数値だったらしい。本番ではtoUpperCase関数を使った。

B - Futon

全探索

C - Neq Min

ちょっと悩んだ。最初に考えたのはsetに0から200005までを入れて、p[i]を削除しながら最小値を求めていく方法。ただKotlinはsetの最小値をO(1)で求められないのでこれは却下。その次にbool配列を使う方法を考えた。愚直に0から試すとTLEするけど、答えは減少しないので、前回の値から探索していくと大丈夫。

D - Squares

とても難しい。すべての置き方は(N-A+1)2(N-B+1)2通りで、ここから重なるような置き方を引いていく。重なってできる図形は、角の部分を埋めて長方形とみなしてもよい。この長方形の辺の長さをx,yとする。長方形の置き方は(N-x+1)(N-y+1)通りある。あとは長方形の大きさがx,yになるような置き方の数を求めればよい。A<Bとしておく。x,y>Bのときは4通りある。x=y=Bのときは一辺Bの正方形の内側に一辺Aの正方形を置くので(B-A+1)2通り。x=B,y>Bのときは2(B-A+1)通りで、x>B,y=Bのときも同じ。

足し合わせるときはN-x+1をx'に置き換えると楽かも。

1WAして絶望していたけど、n<a+bのときに0を出力するようにしたら通った。

E - Lamps

Dが解けないのでEを見たら一瞬で解法が浮かんで笑顔になった。

この問題はABC129D - Lampを解いたことがあるかどうかで難易度が大きく変わりそう。タイトルもそっくりだけど中身もそっくり。

照明の置き方についての和を求める問題だけど、これをマス目についての和に言い換える。数え上げでは定番のテクニック。あるマスについて、そのマスから上下左右に連続する空マスの個数がnで、空マスの総数がkのとき、答えに$(2 ^ n-1)2 ^ {k-n}$を加算する。nの計算に、上であげたLampのコードを流用した。

1TLEした。2べきの計算が重いので前計算したら通った。logは定数ではない…。

F - Random Max

積分をつかうらしい。確率も積分もよくわからない。数学ができません。