2023年10月21日（土）に行われた、企業・学校対抗のプログラミングバトル PG BATTLE 2023 に参戦しました。
この記事では、Python 3によるましゅまろ問題の解説や大会の結果を共有します。
同じチームのかつおぶし担当の方も参戦記を執筆しているので、こちらの記事も是非読んでください！
PG BATTLE とは
PG BATTLEとは「企業・学校対抗プログラミングコンテスト」です。
3人1チームで参加し、3人それぞれに異なる4問の問題を制限時間内に解きプログラムを提出します。
コンテスト終了後にプログラムが採点され、チームの合計点数と解答時間で順位が決まります。
ましゅまろ担当 問題と解答例
下記ページに問題一覧とAtCoder社による解答例が公開されています。
ましゅまろ 難易度1 : コイントス
考察
各コイン投げの結果は独立しているため、単一のコイン投げにおける裏が出る確率 $\frac{1}{2}$ を $N$ 回掛け合わせたものを出力します。
コード
N = int(input())
print(pow(0.5, N))
ましゅまろ 難易度2 : 微分
考察
微分の知識がなくても、問題文の通りに実装すれば正解できます。
コード
A, B = map(int, input().split("x^"))
print(f"{A * B}x^{B - 1}")
ましゅまろ 難易度3 : 2 進数と 10 進数
考察
Pythonの特定のバージョン以降において桁数が4300を超える数を入力で受け取りstrからintへ変換する場合、工夫をしないでint(input())とするとエラーになります。
sys.set_int_max_str_digits(n)を追加することで、整数の文字列変換の長さの制限を設定することができます。
コード
import sys
sys.set_int_max_str_digits(5000)
A = int(input())
B = int(input(), 2)
if A > B:
print(">")
elif A < B:
print("<")
else:
print("=")
補足
解答例は、decimalモジュールを使用して大きな桁数の数の変換で起きるエラーを回避しています。
ただし、decimal.Decimalクラスでは、int(x, base)のように基数を指定して数値を変換するメソッドは提供されていません。
そのため、2進数と10進数の変換を自力で実装する必要があります。
ましゅまろ 難易度5 : ダンス
自力では解けず、解答例を見ました。
解答例
解答例のコード説明
解答例では、前半で二項係数を事前に計算し、後半で区間DPを使用して問題を解いています。
前半：二項係数の計算
後半の処理で多数の二項係数の計算が必要であるため、事前に計算します。
必要な二項係数はパスカルの三角形を使用して$O(N^2)$で計算できます。
計算速度に影響が出ないように値はmod = 998244353で割った余りを格納します。
(合同式の性質により最終的な結果は正しく計算することが保証されます)
binominal = [[0] * (N + 1) for _ in range(N + 1)]
binominal[0][0] = 1
for i in range(1, N + 1):
binominal[i][0] = 1
for j in range(1, i + 1):
binominal[i][j] = (binominal[i - 1][j - 1] + binominal[i - 1][j]) % mod
後半：区間DP
区間DPを使用して最終的な結果を求めることができます。
DPテーブルを以下のように定義します。
-
dp[l][r]:= 位置lから位置r-1までの範囲にいる人々を列から取り除くための方法の総数をmodで割った余り
初期条件として、l = rのときdp[l][r] = 1とします。
lとrの差が小さいほうから順にDPを計算していき、dp[0][N]を出力することで正解できます。
dp = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(N + 1):
dp[i][i] = 1
for w in range(2, N + 1, 2):
for r in range(w, N + 1):
l = r - w
for m in range(l + 1, r, 2):
if S[l] != S[m]:
dp[l][r] = (dp[l][r] + dp[l + 1][m] * dp[m + 1][r] * binominal[(r - l) // 2][(r - (m + 1)) // 2]) % mod
print(dp[0][N])
結果・感想
企業の部 23位/187チーム中 でした！
個人としては、全問正解を目指していたのですが、2問しか正解することができませんでした。。。
次回は、全問正解できるよう精進します！
We Are Hiring!
参考