AtCoder ABC121のただの感想

どうもーーーーー

懲りずにまたABCに参加。

結果は初の全完。

今回は全完がいつもより多いみたい！
ラッキー

それでは適当に感想

A:
B,Cよりも悩みました笑
(Aなのに5:27もかかった。)

H, W = LI()
h, w = LI()
 
print((H-h)*(W-w))

もともとの幅-黒い部分の行数
と
もともとの高さ-黒い部分の列数
を
かけあわせると白い部分の四角の面積が求まる！

■■■□□
■■■□□
■■■□□
■■■■■
■■■■■

これなら5-3と5-2をかけると、白い部分が出ます。

もっとはやく解けるべきである。

B:
素直に問題文の条件をコードに落とすだけ。
気をつけることはない。

N, M, C = LI()
B = LI()
A = []
for i in range(N):
    A.append(LI())

res = 0  
for i in range(N):
    x = sum([A[i][j] * B[j] for j in range(M)]) + C
    if x > 0: res += 1
print(res)

普通に格納されたAの各行に対して、BをかけたものとCを足して、0より大きいかを比べて大きければresultに1を足していくだけ。

C:
貪欲。数少ない私の知るアルゴリズム。
pythonだと普通にソートするだけでいいから楽。

N, M = LI()
 
AB = []
for i in range(N):
    a,b = LI()
    AB.append([a, b])
 
# ただ安い店から買い叩いていくだけの話
AB = sorted(AB, key=lambda x:x[0])
 
count = 0
idx = 0
cost = 0
while count < M:
    if AB[idx][1] > M - count:
        # この店で終わりの場合
        cost += (M-count)*AB[idx][0]
        count = M
        break
    else:
        # 全部買う
        cost += AB[idx][0] * AB[idx][1]
        count += AB[idx][1]
    idx += 1
 
print(cost)

sortのところでkeyを指定してるけど、いらなかったな。
てかこれ、せめて価格と本数の入力を逆順にするべきだったのでは？？

最後のループは変数が多くて気持ち悪い感じになってしまいましたが、今まで買った本数をcount, それまでにかかったコストをcost,訪れる店の番号をidxで管理しました。

訪れた店のレッドブルを全部買うべきなら、その店の値段と本数をかけたものをプラス。
訪れた店の在庫のほうが、足りない本数より多い場合は、その店で買って買い物終了なので、足りない本数×その店の値段を足して終了。

初Dをリアルタイムで通せた。
しかし、正直理解してません。
気合で通しました。
競プロは気合が命。
気合があればDも通る。

A, B = LI()
if B % 4 == 0:
    # 0になるのが1つ前
    pass
elif B % 4 == 1:
    # 0 になるのが2つ前
    B = B^(B-1)
elif B % 4 == 2:
    # 0になるのが３つ前
    B = B^(B-1)^(B-2)
elif B%4 == 3:
    B = 0
    
A = A - 1
if A % 4 == 0:
    pass
elif A % 4 == 1:
    A = A ^ (A-1)
elif A % 4 == 2:
    A = A ^ (A - 1) ^ (A - 2)
else:
    A = 0
 
print(A^B)

この解答を見ると気合のほどが伝わってくるのではないでしょうか。。

まあ思考の過程をたどると、まず値がかなりでかい。10**12て。
これは計算させる気はないなと思いました。
DPなどもさすがにこの桁数になると関係ないだろうーと思って。

ということであんまりXX法的な話では無いかなーと思い。とりあえず0~8までを紙に２進数で書き出して、
いろいろxorを取ってみました。

f:id:mktrdbg:20190309235456p:plain

そうすると、このように0-3-7-11といったように、４個ごとにxorが0になるという規則性を見出しました。
これが気合の力。
（ちなみに２個毎に１になるという規則性もあるらしい）
つまり、20は０から数えたときに21番目なので、20の2進数が0-20のxorになります。
21の場合は0から22番目なので、20と21のxorになります。

しかしそれだけでは解けず。
さらなる気合を注入し、
0-5のxorを取った後、0-3のxorを取って、その2つのxorを取ったりいろいろしてたら、たまたまそれが正解だった。

こうして一切のかっこよさのない解答ができましたとさ。めでたし。

つまりこのD正答は、偽。
他のD問題等にあまり汎用性のない解き方をしてしまった感。
小手先のテクニック。

まあしかし今は良しとしよう。少しずつ伸ばしていく。

f:id:mktrdbg:20190310000222p:plain

なんとかあともう少しで緑というところまできた。
まあ右肩上がりだしよしとしよう。

AGCで１完だったらレーティング下がるかな？？

参加するか悩む。
早く解けたら提出しようかな。

ま、今回はこんなところで。

Terada's Blog

フリーランスでソフトウェア開発してます。プログラミング、競プロ、スタートアップなどについて

AtCoder ABC121のただの感想