HHKB2020

一見簡単そうに見えるDで計算間違いをしてハマって時間が解けて3問でした。飛ばしてEをやればよかった。

https://gyazo.com/96fdb60be9b5c7f4c36b92c975424089

https://gyazo.com/9d6d93ac3d485534cc5a6bed6d31b23f

https://gyazo.com/d25766b2c359add23bb67af11630b668

数えます

番兵付きの一次元でマップを読むコードは、作ってスニペットに登録してました

code:python

def solve(data):

ret = 0

for i in allPosition():

ret += 1

ret += 1

return ret

https://gyazo.com/3bd559ee36a1dd8e504a027b0b98bb28

code:python

def solve(N, XS):

cur = 0

for i in range(N):

cur += 1

print(cur)

二重ループだけども内側も高々20万回しか呼ばれないので大丈夫

usedのサイズをNやN+1にしててRE。Nより大きな値がくる可能性がある。

https://gyazo.com/4e292857475488888efb440a7ce310a6

一見簡単なように見せかけて「あっ、はみ出す時があるのか」「あ、はみ出す幅によって減らす数が違うのか」とズブズブと泥沼にハマっていく問題

落ち着いて整理したら解けたのかもしれないが時間を溶かしすぎて、焦りから頭が働かなくなった

なお素朴解法はこんな感じ

code:python

def blute(N, A, B):

ret = 0

for ax in range(0, N - A + 1):

for ay in range(0, N - A + 1):

for bx in range(0, N - B + 1):

for by in range(0, N - B + 1):

if ax <= bx < ax + A or ax < bx + B <= ax + A:

if ay <= by < ay + A or ay < by + B <= ay + A:

continue

ret += 1

return ret

(1-x)^5で割れば4次式になることは確認した

code:python

array([ 36300, -151980, 238728, -166632, 43560, 0, 0,

0, 0, 0])

デカい係数を見てから「あ、これ3変数だった、どうするんだっけな」みたいな気持ちになった

計算は苦手なのでコンピュータわ

公式解説

https://gyazo.com/28c8b91789fd402d10da52759be21205

Dで時間がなくなった。後で読んでみたらこっちの方が僕には解きやすそう。先に問題を全部読んだり、泥沼にはまらないようにポモドーロタイマー掛ければよかったかも。

考えたこと

例えば2つの照明が置けるマスで照らされるマスがあった場合、そのマスは4通りの照明の置き方の組み合わせのうち3通りで照らされる

すべてのマスについてKを求める

例えば上方向に何マス続いてるかは、自分の上のマスを見て1を足せばいい

これを四方向についてやる

点灯パターンごとの照らされたタイルの枚数の和は、タイルごとの照らされる点灯パターンの和

https://gyazo.com/4ece1b83003aa351486285e44b87a67c

max(a,b,c) <= x ⇔ a<=x and b<=x and c <= x

みたいな感じになって、不等号の方が扱いが簡単。