hhkb2020

NISHIO Hirokazu [Translate]
HHKB2020
HHKB プログラミングコンテスト 2020 - AtCoder
一見簡単そうに見えるDで計算間違いをしてハマって時間が解けて3問でした。飛ばしてEをやればよかった。


B - Futon
数えます
番兵付きの一次元でマップを読むコードは、作ってスニペットに登録してました
地図読み込み時に番兵をつける
pythondef solve(data):
    ret = 0
    for i in allPosition():
        if data[i] and data[i + 1]:
            ret += 1
        if data[i] and data[i + WIDTH]:
            ret += 1
    return ret


C - Neq Min
pythondef solve(N, XS):
    used = [0] * (200_000 + 1)
    cur = 0
    for i in range(N):
        used[XS[i]] = 1
        while used[cur]:
            cur += 1
        print(cur)
二重ループだけども内側も高々20万回しか呼ばれないので大丈夫
usedのサイズをNやN+1にしててRE。Nより大きな値がくる可能性がある。

D - Squares
一見簡単なように見せかけて「あっ、はみ出す時があるのか」「あ、はみ出す幅によって減らす数が違うのか」とズブズブと泥沼にハマっていく問題
落ち着いて整理したら解けたのかもしれないが時間を溶かしすぎて、焦りから頭が働かなくなった
なお素朴解法はこんな感じ
pythondef 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次式になることは確認した
python>>> xs = np.array([blute(20, 10, i) for i in range(1, 11)])
>>> reduce(np.convolve, [[1, -1]] * 5, xs)[:10]
array([  36300, -151980,  238728, -166632,   43560,       0,       0,
             0,       0,       0])
関連 数列を有理式にする
デカい係数を見てから「あ、これ3変数だった、どうするんだっけな」みたいな気持ちになった
計算は苦手なのでコンピュータわ
ラグランジュ補間を勉強しておくべきだったか？
公式解説
一番なるほどだったのは「対称性からXとYを個別に考えないで良い」ってところ 対称性で次元削減
「重ならないケースを数えたいが難しいので全体から重なるケースを引く」は余事象を引くだな

未AC

E - Lamps
Dで時間がなくなった。後で読んでみたらこっちの方が僕には解きやすそう。先に問題を全部読んだり、泥沼にはまらないようにポモドーロタイマー掛ければよかったかも。
考えたこと
例えば2つの照明が置けるマスで照らされるマスがあった場合、そのマスは4通りの照明の置き方の組み合わせのうち3通りで照らされる
全部でNマスあってK個で照らされるなら2^{N-K} (2^K -1)通りで照らされる
すべてのマスについてKを求める
例えば上方向に何マス続いてるかは、自分の上のマスを見て1を足せばいい
これを四方向についてやる
無意識にやったけどこれは足し算の順序を変えるだな
点灯パターンごとの照らされたタイルの枚数の和は、タイルごとの照らされる点灯パターンの和
xごとのf(x,y)の和はyごとのf(x,y)の和
未AC

F - Random Max
確率変数の最大値の期待値
> max やそれを含む順位統計量の確率密度関数は、累積分布関数を求めてから微分します。
> max(a,b,c) <= x ⇔ a<=x and b<=x and c <= x
> みたいな感じになって、不等号の方が扱いが簡単。
https://twitter.com/maspy_stars/status/1314927370105581569?s=21
maxの不等号は不等号のand
>0,1 の一様乱数 K 個の最小値の期待値は 1/(K+1) 
https://twitter.com/noimi_kyopro/status/1314924799303458819?s=21
未AC