最終更新: 2021-09-14T21:45+0900
別個に知っているが関連があるとは思っていなかった二つの Webサイト、「ときどきの雑記帖 再起編 2012年2月(中旬)」から「Problem 191 - もうカツ丼でいいよな」へのリンクがどういう観点で張られたのか、確かめるために*リンク先を読みたいがネタバレはいかん。との思いでがんばった。
まず問題がおかしい。欠席は３連続でなければ許されるのに遅刻は１回までとか⁑。まあどうでもいい。それより問題文が難しかった。punctuality(無遅刻)と forfeit(権利の喪失)の２単語は辞書を引いたし、カンマや関係詞で連続する文は主語述語修飾関係がわかりにくいので、細かいことを考えずに流れに注意して４、５回読み直した。81という数字がどういう経緯で出てきたのか(※OALの３文字で作る長さ４の文字列=3^4通り)、説明があれば問題文を理解する一助となったろうに、そんなものはなかった。
Half_period_strings行以降のバグてんこ盛りのぐだぐだは一重に処理時間と消費メモリを節約することが目的。正規表現でやることは最初からの方針だったのだけど改行で連結した 30-period stringsを検索しようとしたら Rubyがメモリ不足で落ちる。ワーキングセットが 2GiBを超えたあたりだったと思う。ならばと一行分ずつ逐一処理しようとすると時間がかかりすぎる(30分はかからないが)。Threadで分散してみようとしたが Ruby(1.9)には GVLとかいうのがあって CPUを 33%までしか使ってくれなかった。Fiberもそういう期待には応えてくれないみたい。プロセス間通信は面倒。時間が許すなら、
Thirty_period_strings = Joint_period_strings[
Fifteen_period_strings, Fifteen_period_strings
]
p Thirty_period_strings.inject(0){|count,tristr|
count + 1 + tristr.scan(/A|(?<=AA)O|(?<=A)O(?=A)|O(?=AA)/).length
}
これ(を配列を要求しないように書き換えたバージョン)だけで済んでしまうことなのに、15-period stringsと 30-period stringsの間には処理すべき量に雲泥の差があった。
戦略は、
以下、偶然なのかなんなのか、答えは出たが説明できないスクリプト(ピリオドの置き方が Ruby 1.9専用みたい)。実行時間は１秒未満。
# PE 191
Letters = %w(O A).freeze
Re_filter = /^(?:(?!AAA).)*$/
Joint_period_strings = lambda{|*args|
return args.first.product(*args.drop(1))
.map{|_| _.join('') }
.select{|_| _.match(Re_filter) }
}
Three_period_strings = Joint_period_strings[
Letters, *Array.new(2){ Letters }
].freeze
Six_period_strings = Joint_period_strings[
Three_period_strings, Three_period_strings
].freeze
Fifteen_period_strings = Joint_period_strings[
Six_period_strings, Six_period_strings, Three_period_strings
].freeze
Re_score = /A|(?<=AA)O|(?<=A)O(?=A)|O(?=AA)/
IndexedScore = Struct.new(:num, :sum)
Half_period_strings = Fifteen_period_strings
l_index = Hash.new{|h,l_back| h[l_back] = IndexedScore.new(0,0) } # by ending codon. {'OOO'=>IndexedScore,'OOA'=>,...}
r_index = lambda{|r_front| return l_index[r_front.reverse] } # by starting codon. {同上} (実体はl_indexと共有)
Half_period_strings.each{|str15|
score = l_index[str15[-3,3]]
score.num, score.sum = score.num+1, score.sum+str15.scan(Re_score).length
}
p l_index.keys.product(l_index.keys).inject(0){|count,_| l_back, r_front = *_
joint = l_back + r_front
next count if Re_filter !~ joint
l_score, r_score = l_index[l_back], r_index[r_front]
joint_score = [joint, l_back, r_front].map{|_| _.scan(Re_score).length }.inject{|a,b| a-b }
next count + l_score.sum*r_score.num + r_score.sum*l_score.num + (1+joint_score)*l_score.num*r_score.num
}
p Process.times
他所を見て回った。得たヒントは「漸化式」「DP」「scoreは Oを数えるだけ」「prize stringは Lの出現回数(0-1)と先端部の Aの連続数(0-2)で classifyできる」。
実際、どちらでもいけた。だけど下の方が良いのは明らか。ビットを数える処理にも置き換えられるし、joint_scoreは不要になるし。
score = tristr.scan(/A|(?<=AA)O|(?<=A)O(?=A)|O(?=AA)/).length score = tristr.count(?O)
このヒントを基に以下のスクリプトができた。実行時間はコンマ１秒未満。１０倍高速。早く書けてバグが無くて実行が速くて、昨日と一昨日の自分が何に頭を悩ませてたのか不思議になるよね。この着想に独力でたどり着けないところが己の限界。
# coding: utf-8
# PE 191
Extend_prize_strings = lambda{
L,A,O = 1,1,1
A0L0, A0L1, A1L0, A1L1, A2L0, A2L1 = *0..5
return lambda{|prize_strings| ❦=prize_strings
return [
# a=0; l=0
❦[A0L0]*O + ❦[A1L0]*O + ❦[A2L0]*O,
# a=0; l=1
❦[A0L0]*L + ❦[A0L1]*O + ❦[A1L0]*L + ❦[A1L1]*O + ❦[A2L0]*L + ❦[A2L1]*O,
# a=1; l=0
❦[A0L0]*A,
# a=1; l=1
❦[A0L1]*A,
# a=2; l=0
❦[A1L0]*A,
# a=2; l=1
❦[A1L1]*A
]
# a=3 (prize forfeited)
❦[A2L0]*A
❦[A2L1]*A
# l=2 (prize forfeited)
❦[A0L1]*L
❦[A1L1]*L
❦[A2L1]*L
}
}.call
Period = 30
# index of prize_strings: i = (a<<1)|l
# a = consecutive As at a prize string head. (0,1,2)
# l = occasion of L. (0,1)
# starting state(=prize string length is zero): a=0;l=0;prize_strings[i]=1
prize_strings = [1,0,0,0,0,0]
Period.times{
prize_strings = Extend_prize_strings.call prize_strings
}
p prize_strings.inject(&:+)
p Process.times
C++11だとコンパイル時に答えを出してしまいそうだ。再帰30回だし。