🗂

ABC351結果

2024/04/28に公開

AtCoder

tech

AB2完で冷えてしまいました・・・
敗因：
①大きい数を指数に使ってはいけない。時間かかるしメモリもオーバーフローする。
②アルゴリズムにとらわれすぎない。手段と目的をはき違えない。

以下記録。

A - The bottom of the ninth

チームAのsumからチームBのsum引いたものに1足してAC。

'''
1行目にチームAのスコア
2行目にチームBのスコアが与えられる。
0 1 0 1 2 2 0 0 1
1 1 0 0 0 0 1 0
チームBが何点取ればチームAを逆転できるかを求める。
'''

A = list(map(int, input().split()))
B = list(map(int, input().split())) 

A_score = sum(A)
B_score = sum(B)
print(A_score - B_score + 1)

B - Spot the Difference

制約がたかだかN<100、計算量O(N^2)でもたかだか一万。全探索でGO！

'''
縦Nマス横Nマスのグリッドが2個
グリッドを比較すると1マスだけ違う
このマスの位置を答える。

入力例
3
abc
def
ghi
abc
bef
ghi

出力例
2 1

'''

N = int(input())
A = [input() for _ in range(N)]
B = [input() for _ in range(N)]

for i in range(N):
    for j in range(N):
        if A[i][j] == B[i][j]:
            continue
        else:
            print(i+1, j+1)

C - Merge the balls

問題はこいつ。
敗因はボールのサイズで愚直にやってしまったこと。指数だけ見りゃよかった。
(ボール合体時は指数+1すればいいだけだから。
balls.append(tmp*2) って気づいて書いてたのに。。。)

以下NGコード。TLEやらMLEやらREやら出てました。
ほぼ正解だったのに。10^9とかありうるバカでかい数字を指数に使っちゃいけませんね。
(2**A[i]がすべての現況)
この後前回貪欲法を知らずに2完で終わってしまった悔しさに惑わされて
貪欲法で解く方針に迷走してタイムアップ。

NG.py

'''
空の列
N個のボール
i番目のボールのサイズは2^Ai

N回の操作を行う
i回目の操作では、i個めのボールを列の右に足す(stack,append)
その後、以下の操作を繰り返し行う
  1. 列のボールが1つ以下なら終了
  2. 右から1番目と2番目のボールのサイズが等しくないなら終了
  3. 右から1番目と2番目のボールをサイズが等しいなら、それらを取り除き、二つのボールの和のサイズのボールを列の右に足す

N回の操作を終えた後の列に残るボールの個数を求める
'''

N = int(input()) # ボールの個数
A = list(map(int, input().split())) # ボールのサイズ

balls = []
for i in range(N):
    balls.append(2**A[i])
    while len(balls) > 1: # ボールが1つ以下なら終了
        if balls[-1] == balls[-2]: # 右から1番目と2番目のボールのサイズが等しいなら
            balls.pop()
            tmp=balls.pop()
            balls.append(tmp*2)
        else: # 右から1番目と2番目のボールのサイズが等しくないなら終了
            break

#print(balls)
print(len(balls))

OKコード。なおpop2回からのballs.append(tmp+1)でなくて、balls[-1] += 1でもいい。
ただpoppopappendのほうがすこーしだけ早い？

OK.py

'''
空の列
N個のボール
i番目のボールのサイズは2^Ai

N回の操作を行う
i回目の操作では、i個めのボールを列の右に足す(stack,append)
その後、以下の操作を繰り返し行う
  1. 列のボールが1つ以下なら終了
  2. 右から1番目と2番目のボールのサイズが等しくないなら終了
  3. 右から1番目と2番目のボールをサイズが等しいなら、それらを取り除き、二つのボールの和のサイズのボールを列の右に足す

N回の操作を終えた後の列に残るボールの個数を求める
'''

N = int(input()) # ボールの個数
A = list(map(int, input().split())) # ボールのサイズ

balls = []
for i in range(N):
    balls.append(A[i])
    while len(balls) > 1: # ボールが1つ以下なら終了
        if balls[-1] == balls[-2]: # 右から1番目と2番目のボールのサイズが等しいなら
            balls.pop()
            tmp=balls.pop()
            balls.append(tmp+1)
        else: # 右から1番目と2番目のボールのサイズが等しくないなら終了
            break

#print(balls)
print(len(balls))

以下差分。こんだけ・・・

差分

InputObject                     SideIndicator
-----------                     -------------
    balls.append(2**A[i])       =>
            balls.append(tmp*2) =>
    balls.append(A[i])          <=
            balls.append(tmp+1) <=

A - The bottom of the ninth

B - Spot the Difference

C - Merge the balls

Discussion