なかけんの競プロノート
🕒 2020/10/10 🔄 2024/10/20

HHKB2020感想戦

😜

HHKB プログラミングコンテスト 2020　参加しました。3完で死にました。

以下は、コンテスト中に考えたことなどです。間違ったことも考えてます。

Aは、大文字小文字の変換を知ってますか？という問題。Bは、可能性のあるものを全部調べる。

Cは、少し難しくて、もちろんそのままやると間に合わない。けど、i番目まで見て答えがXだとすると、i+1番目に答えるものはX以上のはずなので、Xから進めてみていけばいい。pの値をテーブルに入れておいて、すでにあるかどうかを見ていけばOK。

この時点で、今回は難しそうな予感がして、Dを見る。Eも見てFも見て、まぁ一応Dを頑張るかと思う。

Dは、意味は分かるけど、各テストケースで答える時間が短い。なので、なんとか早く答えないといけない。以下は、コンテスト中に考えてた落書き。

感覚的に言って、ダメなケースを全体から引けばよさそう。で、ダメなケースをいくつか書き出してみた。そうすると、縦と横が max(A,B) 以上で A+B 未満のエリアを選べば、そのエリアと辺を共有するように正方形をおけばダメなケースが数えられそう。

とりあえず、 $A\\leqq B$ と仮定する。 $B$ 以上 $A+B$ 未満の整数 $H,W$ を固定して、ダメなケースを数えてみる。

  1. $B\\lt H, W$ のとき。このときは、ダメエリアの縦の選び方が $N-H+1$ 通り。横の選び方が $N-W+1$ 通り。その中で正方形の配置方法が $4$ 通り。図では2通りと書いてるけど、これはミスってる。
  2. $B=H$, $B\\lt W$ のとき。ダメエリアの縦の選び方が $N-H+1$ 通り、横の選び方が $N-W+1$ 通り。その中で、一辺 $A$ の正方形の縦の配置が $B-A+1$ 通りある。さらに、どちらが右にあるか、2通りある。
  3. $B=W$, $B\\lt H$ のとき。2と同じ。
  4. $B=H=W$ のとき。ダメエリアの縦と横の選び方が $N-H+1$, $N-W-1$ 通り。その中で、一辺 $A$ の正方形の縦と横の配置が、それぞれ、 $B-A+1$ 通りある。

これらをそれぞれ数え上げればよさそう。

とりあえず、1を計算。 $H,W$ それぞれ独立に計算すればOK。同じ式が出てくる。結局、 $N-A-B+2$ から $N-B$ までの和を求めて2乗すればOK。これは自然数の和の公式を求めればいい。あと、 $A,B\\geqq 2$ のときじゃないとこの式は意味がないし、 $N-A-B+2$ が負なら $0$ に置き換えて足さないといけない。

2も、定数部分を前に出して、シグマの計算をする。シグマの部分は1と同じ内容。3は2と同じ。4はそのまま掛けるだけ。

これらを実装したんだけど、ダメエリア内での配置方法の数え方がミスっていた。正方形の大きさが同じ場合は、「場所が2通り、色が2通りだから4通りだな」と思っていたが、異なる場合は「場所が2通りだな」と思ってしまっていた。本当は、大きい正方形が、右上、右下、左上、左下のケースがあってこの場合も4通りで、実は正方形の大きさが同じか違うかで場合分けはしなくてもよかった。場合分けをして、サンプルが通らず。結局時間切れ。

途中で、Eも見たけれど、Dを通したい欲望が大きくて時間を費やし、Eは見た瞬間に方針がたつわけではなかったので、結局Dに全コミット。途中の順位表を見ながら、失敗したなぁと思ってた。

落ち方が半端ない。もうちょっと頑張らないと。。。