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

ABCEの4完。今回は何か最初から心拍数が高く、最初のほうの問題を解くのに時間がかかった。調子は悪くなかった。Dが解けそうだったのでFをやらなかったが、どうだったか(微妙なところ)。

今回は録画した。
HHKBプログラミングコンテスト2020の録画(658位)

A - Keyboard

両方文字なの気づいてなくて(片方は文字列だと思ってた)入力をstringにしてしまい後で直した。Yだったら(小文字を)大文字に変換。'a'を引いて'A'を足せばいい。

B - Futon

Bにしては考察が要求される。縦に敷くか横に敷くかでN*(N-1)通りずつあるのでそれを全探索。

C - Neq Min

最近のCにしては難しいけど、C問題らしくて面白かった。現在の最小値と、各数が現れたかどうかのフラグを持つ。最小値の更新が全体でO(N)でできればよく、フラグを更新したら未出現の数になるまでインクリメントすればいい。

D - Squares

しばらく考えて、解ける問題ではありそうだけど果てしなく面倒くさそうなのでEへ。

基本的な方針としては、青の正方形を置くのが何通りかはすぐわかって、B=1ならA*Aを除いたマスの数を掛けるだけで簡単なのでAをB-1だけ太らせて(はみ出すこともある)、青の正方形が動き回ったときに太らせたほうの正方形が白い正方形をどれだけ覆うかを足し上げる、というもの。1次元ならまだしも2次元は相当面倒。正方形のサイズにより場合分けが生じるのでやりたくない。ただ、計算を楽にする方法だけを考えていたので、最後のほうになってE問題と同様に各マスの立場で何回覆われるかを考えることに気づいた。で、九九の表の和を求めるみたいな処理が必要になるが、これはよく考えるといつものやつだ(面積で考えるとわかりやすく、積の和は和の積で求まる)。正方形なので片方の和だけわかればいい。あとは、山の頂上に行けるかとNが偶数かで場合分けすれば計算はそれほど難しくない。しかし、自分が何をやっているか把握できないややこしさで、ギリギリ時間内に書き上げたもののサンプルが通らなかった。

E - Lamps

「美術館」というパズルみたいな設定。区間をまとめてとか色々考えても、上下が絡み合って不可能に見える。少しして、逆にあるマスが2^K回中何回照らされるかを数えればいいと気づいた(典型)。上下左右合計で何マス照らせるかを各マスについて知る必要がある。上下と左右に分けて、左右に(散らかっていないマスが)何マス連続しているかを数えて、例えば6マス連続していたら戻って直前の6マスに6と書き込む。上下も同様にして足して1(交点のぶん)を引けばいい(上下と左右で別々に変数を持ってしまったが一つだけ用意して足していけばよかった)。その中に一つでも照明があればいいので、一つも照明がない1通りを除く。そして2の「それ以外のマスの数」乗を掛ける。これを各空きマスについて足し上げれば答え。Dと比べて簡単すぎておっかなびっくりだった。