AtCoderのABC121に出たときの記録です。
開催日時は、2019年3月9日土曜日21:00〜22:40です。
使用言語はpython3です。
A、B、C、Dの順番で解きました。
A – White Cells
問題はこちら。
やることは全部のマス目の数H*Wから指定された行数と列数の塗られたマス目の数h*W+H*w-h*wを引くだけでした。
行、列のマス目の重複h*wを忘れないようにするだけでした。
特に詰まるところはなく、3分で提出。
↓提出したプログラム
H, W = list(map(int, input().split()))
h, w = list(map(int, input().split()))
print(H*W - h*W - H*w + h*w)B – Can you solve this?
問題はこちら。
行列計算するだけの問題でした。リスト内包表記で各要素の足し算を行って、それの合計を求めました。
リスト内包表記の書き方が少し曖昧でしたが、 問題なく解き終わりました。ここまでで12分。
↓提出したプログラム
N, M, C = list(map(int, input().split()))
B = [int(i) for i in input().split()]
A = [list(map(int, input().split())) for _ in range(N)]
count = 0
for a in A:
c = sum([a[i]*B[i] for i in range(M)])
if c+C > 0:
count += 1
print(count)C – Energy Drink CollectorA – White Cells
問題はこちら。
値段の安いものから貪欲に買えるだけ栄養ドリンクを買っていきました。
特に詰まることなく提出できました。ここまでで20分でした。
↓提出したプログラム
N, M = list(map(int, input().split()))
data = [list(map(int, input().split())) for _ in range(N)]
data.sort()
price = 0
for d in data:
price += d[0] * min(M, d[1])
M -= d[1]
if M <= 0:
break
print(price)D – XOR World
問題はこちら。
XORを使う問題で、少し戸惑いました。普段XORなどのビッド演算をしていないので、悩みました。
結果的には時間内では解くことができず、コンテスト終了後20分で提出。ACでしたが、時間内に解くことができず悔しいです。
解答を見てみると、隣接する数に注目するという方法でした。
nが偶数の時、n xor (n+1) = 1
確かに、これが分かればすぐにできますね。悔しい。
AからBまでというのを、0からBまでと0からA-1までに分けるということには気付いていましたが、これには気付けませんでした。
自分のプログラムでは、2進数で表すと11…111と表せる数までのXORの結果は0になることを利用して、100…000となる数からMまでのXORを求めました。2^0の桁は4で割ったあまりで場合分けして、それ以外の2^kの桁はMの2^kの桁の数が1の時に100…000からMまでの数の個数の偶奇でXORした結果が2^kの桁で0か1かを求めました。
↓提出したプログラム（コンテスト時間内には解けず）
A, B = list(map(int, input().split()))
def f(M):
digit = len(bin(M)) - 2
num = M - 2**(digit-1) + 1
x = 0
for i in range(digit):
if i == 0:
if M % 4 == 1 or M % 4 == 2:
x += 1
else:
if bin(M)[-(i+1)] == '1':
x += (num % 2) * (2**i)
return x
if A == 0:
print(f(B))
else:
print(f(B)^f(A-1))まとめ
A、B、Cはほとんど詰まらずにできましたが、Dで悩みすぎてしまって時間内に全完できませんでした。
rated対象者でも500人以上がDを解くことができていたため悔しいです。
レートも998から992に少し下がってしまいました。
そろそろ本格的に過去問解いたり勉強してレートを上げていきたいと思っています。
