最終更新: 2021-06-08T15:01+0900
昨日あった ABC。D 問題は覆面算。たまたま何か月か前に「FDCAJH × IBCFEH = FBAECIIJEGIH」というのを解く機会があったのだけど、時間制限がないせいで雑に総当たりをして済ませてしまっていた。
本番中は TLE で終わってしまった。E 問題を 15 分で片付けて戻ってきたけど、ついに通せなかった。
制限時間が大盤振る舞いの５秒なんだよね。
桁を１つ２つ減らすだけで時間がだいぶ違うだろうという予測はできたけど、減らし方がわからなかった。なんといっても目の前に文字で書かれた式があるわけではなく、色々なケースが入力されるわけなので。
TODO: Array#all? の中のテストは l<=r より l==r||l+1==r の方が厳しくて良い。
TODO: 和の先頭の桁が１だとすぐにわかる場合がある。
TODO: 列挙してから弾くより列挙しない方がいい。(確定桁が１つあったとして、未確定桁(=文字種-1)の順列の数だけ弾くのは手間だから)
TODO: ループの中の処理がシンプルになるように入念に事前準備をした方がいい。
現在 Ruby での AC 提出は 20。実行時間が 109 ms から 4845 ms までと幅広い。中央値は３秒台です。
たとえば(４桁 ms では最も速い)約 1.6 秒のこの提出>#21688714
先頭桁が０のケースを弾くと同時に、末尾の桁が一致するかどうかだけ特別にチェックしている。一致しないケースでは文字式の全体を数値化する無駄がスキップできる。このひと手間が効果的なのだと思う。
それと、全くの想定外だったのだけど、文字が 11 種類以上使われている式が入力されるケースがあったのだろうか(上の 1.6 秒の提出がチェックして UNSOLVABLE を出力している)。AtCoder の問題は入力や条件がきれいに整理されていて枝葉の手間が省けるように作られているだろう、という甘えがあるのは否めない。
３つある３桁 ms の提出が何をやっているのかは、さっぱりわかりません。
４つの TODO を意識して書いたけど、妥協した部分もある。
とはいえ、これを深さ優先探索で妥協なく書き換えただけで２桁 ms になる？ そう、Ruby で現在最速の提出は 71 ms になっている。
根本的なところで、列挙してから弾くか、可能性のある組み合わせだけを列挙するかという違いがあるのかな。そっち方面で書こうとしたときは、ある桁を見たときに未確定文字が０なのか、１個あるのか２個か３個か、未確定文字があるのはどの項か、繰り上がりはあるのか、ということを考えるのが面倒くさくなって(=脳のキャパシティをオーバーして)、書けなかったんだよね。
書けなかったのをがんばって書いた。時間は申し分ないけども１つの WA。たぶん答えがないケースだと思うんだけど……。
WA の原因は非ゼロチェックが１つ抜けていたこと。それと、想定外だと書いた「文字が 11 種類以上使われているケース」はサンプル４がそうだった。コピペするだけで全然読んでいない。
雑に総当たりしていたのを反省して(TLE は嫌だ！)、数か月ぶりに書き直した。提出 #21743445 をベースにして、掛け算に対応させた。prd の計算が難しかったのですよ。ありえたかもしれないもうひとつの筆算のかたち。すっごく縦長になるけども。
A = 'FDCAJH'.bytes.to_a # to_a is for Ruby 1.8/1.9
B = 'IBCFEH'.bytes.to_a
P = 'FBAECIIJEGIH'.bytes.to_a
C2D = [nil]*91
D2C = [nil]*10
NZ = [-1]*91; NZ[A[0]] = NZ[B[0]] = NZ[P[0]] = 0
F = lambda{|i,carry,aa,bb,zz|
next carry<1 if i<-P.size
a = (c = A[i]) ? C2D[c] : 0
b = (c = B[i]) ? C2D[c] : 0 if a
next D2C.each_with_index.any?{|e,d|
next if e || d==NZ[c]
C2D[c],D2C[d] = d,c
next F[i,carry,aa,bb,zz] || C2D[c] = D2C[d] = nil
} unless b
prd = a*bb+b*aa+a*b*zz+carry
if p = C2D[c=P[i]]
next p==prd%10 && F[i-1,prd/10,a*zz+aa,b*zz+bb,zz*10]
else
p = prd%10
next if D2C[p] || p==NZ[c]
C2D[c],D2C[p] = p,c
next F[i-1,prd/10,a*zz+aa,b*zz+bb,zz*10] || C2D[c] = D2C[p] = nil
end
}
raise unless F[-1,0,0,0,1]
puts [A,B,P].map{|a|'%*d'%[P.size,a.inject(0){|b,c| b*10+C2D[c] }]}