Home / Python /

HHKB プログラミングコンテスト 2020をPythonで解く

投稿日：　

Atcoder Python

B!
Daniel AgreloによるPixabay(https://pixabay.com/)からの画像

こんにちは, Shinoryoです.

今回はHHKB プログラミングコンテスト 2020を, Pythonで解いてみた結果を書き連ねていこうと思います.

HHKB Programming Contest 2020 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A - Keyboard

大文字にするには.upperを使用します.

B - Futon

「今いるマスとその右マスがともに空いているなら$+1$」「今いるマスとその下マスがともに空いているなら$+1$」という計算を利用します. indexのout of rangeエラーには注意が必要です.

C - Neq Min

問題文にあることをそのまま律儀に実行することもできますが, 時間計算量が膨大になってしまい, TLE.

そこで, $i$が大きくなるにつれ答えも増加すること(正確には, 減少しないこと)を利用します. ある$i$に対する答えを求めたいときは, $i-1$について求めた答え以上の値で, 今まで追加した整数の中に登場しない最小の値を求めればよいことになります. 今までに登場したかどうかを, $200001$個の変数を格納する配列で管理すると楽です.

D - Squares

以下のようにして求めるようです.

  • 求める答えを$\mathrm{ans}$とします. 赤い正方形と青い正方形を敷き詰める場合の総数は$(N-A+1)^2 (N-B+1)^2$なので, 赤い正方形の内部と青い正方形の内部が重なるように置く場合の数を$X_1$とすれば, \begin{align} \mathrm{ans} = (N-A+1)^2 (N-B+1)^2 - X_1 \end{align} となります.
  • 「赤い正方形の内部と青い正方形の内部が重なる」は「赤い正方形の$x$座標と青い正方形の$x$座標が重なる」かつ「赤い正方形の$y$座標と青い正方形の$y$座標が重なる」となります. したがって, 1次元的に長さ$A$の区間と長さ$B$の区間を長さ$N$の区間に詰めたとき, 区間が重なる置き方の総数を$X_2$とすれば, \begin{align} X_1 = X_2^2 \end{align} となります.
  • 長さ$A$の区間と長さ$B$の区間を長さ$N$の区間に詰める場合の総数は$(N - A + 1) (N - B + 1)$なので, 長さ$A$の区間と長さ$B$の区間を長さ$N$の区間に詰めたとき, 区間が重ならない置き方の総数を$X_3$とすると, \begin{align} X_2 = (N - A + 1) (N - B + 1) - X_3 \end{align} となります.
  • 長さ$A$の区間と長さ$B$の区間を長さ$N$の区間に詰めたとき, 区間が重ならない置き方の総数というのは,
    • 空白部分$N - A - B$個
    • 赤い部分$1$個(つながっているものはまとめて$1$個と見なす)
    • 青い部分$1$個(つながっているものはまとめて$1$個と見なす)
    の並び替えなので, 同じものを並べ替える場合の数で \begin{align} X_3 = \frac{(N - A - B + 2)!}{(N - A - B)!} = (N - A - B + 1) (N - A - B + 2) \end{align} となります.

以上を利用すれば, 各テストケースに対して定数時間($O(1)$)で計算することができます. 下の例では関数を用いて記述しています.

E以降

E以降は私の能力不足故に省略いたします.

参考にしたサイト等

Search

About Me

自分の写真
理系大学生でした. Bloggerを利用して発信を行っています.

Labels

Blog Archives