Home / Python /

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

投稿日：　 更新日：2022/09/02

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を使用します.

# 入力
s = input()
t = input()
# 大文字にするには.upperを使用
if s == "Y":
print(t.upper())
else:
print(t)
view raw atcoder-abc-HHKB2020-a.py hosted with ❤ by GitHub

B - Futon

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

# 入力
h, w = [int(i) for i in input().split()]
s = [input() for _ in range(h)]
# 答えを格納
ans = 0
# 今いるマスとその右マスがともに空いているなら+1
# 今いるマスとその下マスがともに空いているなら+1
for i in range(h):
for j in range(w):
if j != w-1 :
if s[i][j] == "." and s[i][j+1] == "." :
ans += 1
if i != h-1 :
if s[i][j] == "." and s[i+1][j] == "." :
ans += 1
# 答えを出力
print(ans)
view raw atcoder-abc-HHKB2020-b.py hosted with ❤ by GitHub

C - Neq Min

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

# 入力
n = int(input())
p = [int(i) for i in input().split()]
# 各iに関して
for i in range(n) :
# 出力値の初期値
output = 0
# 配列を切り出す
p2 = set(p[:i+1])
# 0から調査
while output in p2 :
output += 1
# 出力
print(output)
view raw atcoder-abc-HHKB2020-c-tle.py hosted with ❤ by GitHub

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

# pmax
pmax = 200001
# 入力
n = int(input())
p = [int(i) for i in input().split()]
# 整数が登場したかのフラグを格納する配列
a = [False for _ in range(pmax)]
# 出力値の初期値
ans = 0
# 各iに関して
for i in range(n) :
# 整数p[i]が登場したフラグを立てる
a[p[i]] = True
# 前回の出力値以上の値に関して調査
for j in range(ans, pmax):
# 整数ansが登場していないなら、それが出力すべき値
if a[ans] == False:
break
# ansに+1して再調査
ans += 1
# 出力
print(ans)
view raw atcoder-abc-HHKB2020-c.py hosted with ❤ by GitHub

D - Squares

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

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

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

# mod
mod = 1000000007
# 入力：int型N,A,B
# 出力：赤い正方形の内部と青い正方形の内部が重ならない置き方の総数
def ans(Nin, Ain, Bin):
return (((Nin - Ain + 1)**2)*((Nin - Bin + 1)**2) - x1(Nin, Ain, Bin)) % mod
# 入力：int型N,A,B
# 出力：赤い正方形の内部と青い正方形の内部が重なる置き方の総数
def x1(Nin, Ain, Bin):
return x2(Nin, Ain, Bin)**2
# 入力：int型N,A,B
# 出力：長さAの区間と長さBの区間を長さNの区間に詰めたとき、区間が重なる置き方の総数
def x2(Nin, Ain, Bin):
return (Nin - Ain + 1)*(Nin - Bin + 1) - x3(Nin, Ain, Bin)
# 入力：int型N,A,B
# 出力：長さAの区間と長さBの区間を長さNの区間に詰めたとき、区間が重ならない置き方の総数
def x3(Nin, Ain, Bin):
# 空白マスが作れなければ0であることに注意
if Nin - Ain - Bin < 0:
return 0
else:
return (Nin - Ain - Bin + 2)*(Nin - Ain - Bin + 1)
# T入力
T = int(input())
# T回ループ
for _ in range(T):
# NAB入力
N, A, B = [int(x) for x in input().split()]
# 答えを出力
print(ans(N, A, B))
view raw atcoder-abc-HHKB2020-d.py hosted with ❤ by GitHub

E以降

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

参考にしたサイト等

Search

search

About Me

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

Labels

Blog Archives