どうもこんにちは！
今週のコンテストはCまで完答。
振り返りもCまでやります。
問題
問題は以下のリンクから。
A - What month is it? -
与えられる整数をx,yとし、現在をx月としたときにyか月後が何月かを出力する問題。与えられる整数は1~12です。
シンプルに計算すればよいですね。
n,m = map(int,input().split())
if n+m <= 12:
print(n+m)
else:
print(n+m-12)
B - Most Minority -
N人が0か1の投票をM回おこなったとして、0と1で構成されるM文字の文字列がN個与えられます。
1回の投票ごとに、全員が同じ値に投票した場合は全員に1点、そうでない場合は0と1のうち、少数派に投票した人にのみ1点が与えられるという条件のとき、合計得点が高い人の番号を出力するという問題。人数は最大99人で必ず奇数、投票回数は最大100回です。
すんなり解く方法がありそうな気がしますが思いいたらず、以下のようにしました。
- 入力を受け取る際に、投票ごとに0と1の投票人数をカウントする
- 人ごとに投票を見て、投票数が少ない方に投票している回数と全員が一致した投票の回数の和をスコアとする
- 最大の得点だった人をピックして出力
自分だけかもわかりませんが、整理にすごい時間がかかりました・・・後述するC問題の方が解きやすかった気がします。
n,m = map(int,input().split())
s = []
count_0 = [0] * m # i回目の投票で0に投票された数
count_1 = [0] * m # i回目の投票で1に投票された数
for _ in range(n):
vote = list(input())
s.append(vote)
for i in range(m):
if vote[i] == '0':
count_0[i] += 1
else:
count_1[i] += 1
score = [0] * n
for i in range(n):
for j in range(m):
a = '0' if count_0[j] < count_1[j] else '1'
if count_0[j] == 0 or count_1[j] == 0 or s[i][j] == a:
score[i] += 1
ans = []
for i in range(n):
if score[i] == max(score):
ans.append(i+1)
print(*ans)
C - Sum of Min Query -
2つの長さNの整数列A,BとQ個のクエリが与えられ、1つのクエリを処理するごとに$\sum^n_{k=1}min(A_k,B_k)$を出力するという問題。クエリは指定された整数列の指定要素の値を変更するというものです。例えばA 2 10というクエリなら、整数列Aの2番目の値を10に変更します。
整数列の要素の最大は$2 × 10^5$、整数列の要素の値の最大は$10^9$です。
以下のような手順として実装しました。
- 入力を受け取る際に、最小の値を保持するリストとその合計値を作る
- クエリごとに指定された整数列の値を変更する
- クエリの処理により以下の条件のいずれかを満たす場合、最小値を保持するリストと合計値を更新する
- 現在の最小値を更新する → 更新後の値ともう一方の整数列の要素の値の小さい方を最小値として更新
- 更新により現在の最小値より小さい値が追加される → リストの値を追加された値に更新
n,m = map(int,input().split())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
q = [input().split() for _ in range(m)]
m = []
ans = 0
# 最小値のリストとその合計を作成
for i in range(n):
m.append(min(a[i],b[i]))
ans += min(a[i],b[i])
# クエリの処理
for i in q:
idx = int(i[1])-1
v = int(i[2])
if i[0] == 'A':
if a[idx] == m[idx]: # 現在の最小値を更新する場合
ans += (min(v,b[idx]) - m[idx])
m[idx] = min(v,b[idx])
elif v < m[idx]: # 現在の最小値より小さい値が追加される場合
ans += (v - m[idx])
m[idx] = v
a[idx] = v
else:
if b[idx] == m[idx] or v < m[idx]: # 現在の最小値を更新する場合
ans += (min(v,a[idx]) - m[idx])
m[idx] = min(v,a[idx])
elif v < m[idx]: # 現在の最小値より小さい値が追加される場合
ans += (v - m[idx])
m[idx] = v
b[idx] = v
print(ans)
ではでは。