AtCoder ABC221 挑戦！

ABC221、コンテスト3回目の挑戦です！
ついにC問題を落としてしまう。
着眼点は良かったが、抜け漏れがあった。悔しい。。。

ABC221A

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

# 32**{(A-1)-(B-1)}=32**(A-B)が答え。
print(32**(A-B))

そのまま算数の問題。

ABC221B

#長さ2以上100以下の文字列 S, T
S=input()
T=input()

Flag=False #判定用のフラグ
#全探索する
#並び替えずに一致するか
if S==T:
    Flag=True
    print('Yes')
#一致しない場合は、隣り合う文字について入れ替えて、一致するか判定
else:
    for i in range(len(S)-1):
        ex_S=[_ for _ in S]#最初の文字列Sのリストで初期化
        ex_S[i],ex_S[i+1]=ex_S[i+1], ex_S[i]
        ex_S_join=''.join(ex_S)
        # print(ex_S_join)
        if ex_S_join==T:
            print('Yes')
            Flag=True
            break
        else:
            pass
if Flag==False:
    print('No')

手間取った部分が、文字列の入れ替え。
文字列については、S[i]でSのi番目を取り出せるので、それで入れ替えられると思っていたのだが、エラーが出てうまくいかず、やむなくリストに取り出してから、入れ替えて再結合した。

ABC221C_一部AC

N=int(input())

#Nの数字の配列をつくる
N_list=[]
for i in range(len(str(N))):
    N_list.append(int(str(N)[i]))
# print(N_list)

#降順に数字を並び替える
sorted_N_list=sorted(N_list, reverse=True)
# print(sorted_N_list)

#A, Bに大きい順に数を分割する。
A, B='', ''
for i in range(len(sorted_N_list)):
    if i%2==0:#iが奇数のとき
        A+=str(sorted_N_list[i])
    else:#偶数のとき
        B+=str(sorted_N_list[i])

C, D='', ''
for i in range(len(sorted_N_list)):
    if i%2==0:
        if i==2:
            D+=str(sorted_N_list[i])
        else:
            C+=str(sorted_N_list[i])
    else:
        if i==3:
            C+=str(sorted_N_list[i])
        else:
            D+=str(sorted_N_list[i])

# print(A, B, C, D)
print(max(int(A)*int(B), int(C)*int(D)))

C問題。結果は、AC16個、WA14個で、取れず。
探索数がオーバーしそうだったので、工夫した。(実際は、探索する方法もあったっぽい。早々に諦めてた。)

着想

・積を最大にするので、数字が大きい方から、桁数の大きいもの同士に使っていくのがよい
・また、サンプルケースで試していくと、どうやらそのままだと積は最大にならない。(ここがふわふわしてコードに落とし込めていなかったため、WAだった)
→サンプルケースの例
123の場合:
A=3, 1 B=2 で31*2=62
A=3, B=2,1 で3*21=63
で後者の方が大きくなる。

998244353の場合:
A=98432, B=9543で98432*9543=939336576
A=95432, B=9843で95432*9843=939337176
でこちらも後者の方が大きい。メカニズムはよくわからんが、おそらくちゃんとやれば証明できるんだろうね。

WAの要因: 抜け漏れがあった。

具体的には、5桁目以降で違う数字が表れたときに、入れ替えができていないので、正しい答えが出ない。
9999321などの場合:
9931*992=9851552
9921*993=9851553

上記を落とし込むと下記の様になる。
コンテスト後に、提出すると、無事ACだった。

ABC221C_AC

N=int(input())

#Nの数字の配列をつくる
N_list=[]
for i in range(len(str(N))):
    N_list.append(int(str(N)[i]))
# print(N_list)

#降順に数字を並び替える
sorted_N_list=sorted(N_list, reverse=True)
# print(sorted_N_list)

#A, Bに大きい順に数を分割する。
A, B='', ''
for i in range(len(sorted_N_list)):
    if i%2==0:#iが奇数のとき
        A+=str(sorted_N_list[i])
    else:#偶数のとき
        B+=str(sorted_N_list[i])


#初めて異なる文字が出てきた部分を入れ替える。
for i in range(min(len(A),len(B))):
    if A[i]!=B[i]:
        list_A=list(A)
        list_B=list(B)
        list_A[i], list_B[i]=list_B[i], list_A[i]
        #入れ替え後のA, Bをjoinで作る。
        A=''.join(list_A)
        B=''.join(list_B)
        break
    else:
        pass

print(int(A)*int(B))

上記のコードでも、B問題の文字列の入れ替えが出てきて、いちいちリストに変換して入れ替えるのがおっくうだった。なんかうまいコードとかあるんだろうか。

3回目にして、ついにC問題が取れませんでしたが、惜しいところまではいけたので悔いはありません。実際、時間内にエラーを解消するのは厳しかったと思います。

来週も頑張りましょう。お疲れさまでした。