どうもこんにちは！
今週のコンテストはCまで完答。
問題
問題は以下のリンクから。完答できたCまでを振り返ります。
A - Approximation -
与えられた正の整数Aと正の奇数BからA÷Bの差が最小となる整数を出力するという問題です。計算結果を四捨五入した値を出せばよいです。
ちょうど丸めに関連してまとめたところでした。正の整数とわかっているので、計算式で処理しました。
a,b = map(int,input().split())
print(int(a/b*2+1)//2)
B - P(X or Y) -
6面体のサイコロを2つ振ったときに、次の2つの条件の少なくとも一方を満たす確率を求めるという問題です。なお、計算結果は小数となり絶対誤差が$10^{-9}$以下であれば正答と判断されます。
- 2つの出目の合計がX以上
- 2つの出目の差の絶対値がY以上
組み合わせは36通りで2重ループでも十分計算できるとして、全ての組み合わせでどちらかを満たす組み合わせの数をカウントして、36で割った値を出力しました。Pythonは計算結果をそのまま出力してもテストケースの範囲ではACとなりました。
x,y = map(int,input().split())
c = 0
for i in range(1,7):
for j in range(1,7):
if i+j >= x or abs(i-j) >= y:
c +=1
print(c / 36)
C - Security 2 -
前提として、はじめは空の文字列tに対して、以下の加工ができるとします。
- tの末尾に0を追加する。例えば012を0120にする。
- tに含まれるすべての数字がそれぞれ次の数字に置き換える。ただし、9の次は0とする。例えば0129を1230にする。
このどちらかの加工をしたときを1回として、与えられた文字列Sを生成するには最小で何回加工する必要があるかという問題です。Sは0から9の数字からなり、文字数は最大$5×10^5$文字です。2重ループはTLEになりそうですね。
解き方のポイントは以下と考えました。
- 1の桁の加工の回数はその数字の数。例えば3なら0から3への3回。13回加工しても3になるが最小回数ではない。
- 末尾に0をつけるときの1の桁の数字は、追加する桁の加工回数を引いた数。例えば、53を作りたいとき、1の桁を追加する前の数字は5-3で2のとき。(2→20→31→42→53という順で加工)
以上から、与えられた文字列Sを逆順に並び替えて、桁の追加回数と1桁ずつ数字を加算した回数を数えればfor文1回で算出できます。このとき、末尾の加算回数を引いたときに負の数になることもありますが、10で割ったあまりに置き換えることで9から0のループも踏まえた処理ができます。(例えば、2から3回分戻すと-1になるが、-1を10で割ったあまりは9になる)
s = input()
r = s[::-1] # 与えられた文字列を逆順に並び替え
a = b = 0
for i in r:
i = int(i)
i -= b # 桁を追加する前の数字に戻す作業
if i < 0:
i %= 10
b += i # 0から数字を増やす回数のカウント
a += 1 # 桁の追加回数のカウント
print(a + b)
--- 2025/5/28 追記 ---
D問題の公式解説を見て、Pythonに変換したので追記します。
D -Domino Covering XOR -
H行W列のマス目に非負整数がマスごとに1つ配置されていて、このマス目に0個以上のドミノを置けるとします。1個のドミノは2マス分の大きさで、重ならないように縦か横に配置できるものです。
この条件下で、ドミノが置かれていないマスの非負整数をビットごとに排他的論理和した値の最大値を求める問題。
計算量的に全探索ができるということで、すべてのケースで求める値を計算して最大値を出力すればよかったようです。
def score(ans,i,j):
if j == w: # i行の最終列のマスを確認後のとき、i+1行の最初に移動する
j = 0
i += 1
if i == h: # すべてのマスを確認後のとき、置かれたドミノをもとに計算する
point = 0
for ni in range(h):
for nj in range(w):
if domino[ni][nj] == False:
point ^= s[ni][nj]
ans = max(ans,point)
return ans
if domino[i][j] == True: # ドミノが配置済みのマスなら次のマスを確認
ans = max(ans,score(ans,i,j+1))
else:
ans = max(ans,score(ans,i,j+1)) # ドミノを配置しないとして次のマスを確認
if j+1 < w and domino[i][j+1] == False: # ドミノを横に配置する場合
domino[i][j] = domino[i][j+1] = True
ans = max(ans,score(ans,i,j+1))
domino[i][j] = domino[i][j+1] = False
if i+1 < h and domino[i+1][j] == False: # ドミノを縦に配置する場合
domino[i][j] = domino[i+1][j] = True
ans = max(ans,score(ans,i,j+1))
domino[i][j] = domino[i+1][j] = False
return ans
h,w = map(int,input().split())
s = []
for _ in range(h):
s.append( [int(x) for x in input().split()] )
domino = [[False]*w for _ in range(h)]
ans = score(0,0,0)
print(ans)
--- 追記ここまで ---
ではでは。