AtCoderのABC124に出たときの記録です。
開催日時は、2019年4月13日土曜日21:00〜22:40です。
使用言語はpython3です。
A、B、C、Dの順番で解きました。
最近過去問を解き始めたおかげか、初めて全完することができました。
A – Buttons
問題はこちら。
AとBのボタンを押しますが、同じボタンを押すと取れる枚数が1枚減ります。
AとBの獲得枚数が同じ場合はAとBのボタンを1回ずつ押し、違う場合は獲得枚数が多い方を2回押すという風に実装しました。
しかし、素早く提出するためにパッと書いて提出したところ、2回押すという操作の部分の実装の”2*”の部分を書き忘れるケアレスミスで1ペナを取ってしまいました。直して提出して、ここまで3分。
こういうケアレスミスは注意しないとだめですね。結局ちゃんと試してから提出した方がいいのかな？でも、早く提出したい欲もあったり。
↓提出したプログラム
A, B = map(int, input().split())
if A == B:
print(A+B)
else:
print(2 * max(A, B) - 1)B – Great Ocean View
問題はこちら。
海に近い順にホテルの高さを確認していき、今までの見てきたホテル以上の高さがあれば海を見ることができます。
ここまでで6分です。
↓提出したプログラム
N = int(input())
H = [int(i) for i in input().split()]
count = 1
before = H[0]
for i in range(1, N):
if before <= H[i]:
count += 1
before = max(before, H[i])
print(count)C – Coloring Colorfully
問題はこちら。
‘0101…10’にする場合の塗り替えるタイルの枚数を調べて、’1010…01’にする場合と比較します。
‘0101…10’から’1010…01’に塗り替える場合は、N枚のタイルを塗り替える必要があります。つまり、’0101…10’の場合の塗り替える枚数をx枚とすると、’1010…01’の場合の塗り替える枚数はN-x枚となります。
‘0101…10’にする場合の塗り替えるタイルの枚数は一枚ずつ0か1かを調べていく方法で実装しました。
実装も難しくなく、すぐに提出できました。ここまでで9分でした。
↓提出したプログラム
S = input()
a = ['0', '1']
count = 0
n = len(S)
for i in range(n):
if S[i] == a[i%2]:
count += 1
print(min(n-count, count))D – Handstand
問題はこちら。
0と1をある範囲で入れ替える操作をK回まで行うことができて、1の連続する数の最大を求めます。
10…01の場合は1回の操作で11…11になります。ここまでは簡単です。
2回操作を行う場合は、その操作の範囲が被る可能性があります。つまり、1回目の操作でl1からr1まで0と1を入れ替えた後に、2回目の操作でl2からr2までの0と1を入れ替える場合で、l2 < r1か、l1 < r2となる場合です。
10…01…10…01を0…01…10…0の部分の0と1の入れ替えを行うと、11…10…01…11になり、その後0…0の部分の0と1の入れ替えを行うことで1…1になります。
1の連続する数を増やす場合には、10…01…10…01は0…0を1…1に2回する操作でも1…1になるので、考えるべき操作は、それぞれの範囲が重複しないような0と1の入れ替えとして考えることができます。
つまり、0と1の与えられた列のうち、0と1のそれぞれで0または1が連続する数を求めていき、K個までの連続する0が1である場合に、1が連続でいくつあるのかの最大値を求めていきます。
注意するべき点としては、連続する0の部分列がK個未満の場合や、与えられた列の先端や末端が0の場合の扱いです。
その部分の実装をするのでいくつかのミスをしてしまったため、2ペナついてしまいましたが、解くことができました。
全部解き終えて57分でした。
↓提出したプログラム（実装は結構汚いです）
N, K = map(int, input().split())
S = input()
c_1 = [0]
c_0 = [0]
count = 0
before = '1'
answer = 0
for i in S:
if i == before:
count += 1
else:
if before == '1':
c_1.append(c_1[-1] + count)
else:
c_0.append(c_0[-1] + count)
if i == '0':
if K+1 < len(c_1):
answer = max(answer, c_1[-1] - c_1[-(K+2)] + c_0[-1] - c_0[-(K+1)])
else:
answer = max(answer, c_1[-1] + c_0[-1])
count = 1
before = i
if i == '1':
c_1.append(c_1[-1] + count)
if K + 1 < len(c_1):
answer = max(answer, c_1[-1] - c_1[-(K + 2)] + c_0[-1] - c_0[-(K + 1)])
else:
answer = max(answer, c_1[-1] + c_0[-1])
else:
c_0.append(c_0[-1] + count)
if K + 1 < len(c_1):
answer = max(answer, c_1[-1] - c_1[-(K + 1)] + c_0[-1] - c_0[-(K + 1)])
else:
answer = max(answer, c_1[-1] + c_0[-1])
print(answer)まとめ
A、B、Cはほとんど詰まらずにできましたが、Dは実装のミスを直すのに時間がかかりました。扱いが難しい部分もちゃんと考慮に入れて、素早く実装できるようになりたいです。あと、ケアレスミスによるペナルティは避けたいですね。
初の全完は嬉しかったです。最近過去問を解くようになったおかげだと思います。
rated対象者でも700人以上がDを解けていたので、比較的簡単めなD問題なのでしょうか？
最近のAtCoderは参加者が増えていてすごいですね。A問題の提出者の人数も4000人を超えていました。
これからもどんどん参加者が増えていきそうですね。
