最終更新: 2021-06-11T11:27+0900
以前書いた。「最初に右辺を評価して、それから左辺の評価と代入を左から順番に実行していく感じかな？ 右辺の一時記憶が必要？ 多重代入は遅くて時々評価順が難しい、というのが現在の評価。」「クイズです。a の結果を確認してから予想してカンマを付けたら予想通りの結果になったので驚きはないけど、やっぱり普通の代入とは違うんだなあ」
そしてこの PR が多重代入について>Evaluate multiple assignment left hand side before right hand side by jeremyevans · Pull Request #4390 · ruby/ruby マージされている。
3.1.0 から変わりそう？ 評価順が変わってパフォーマンスがさらにちょっと遅くなる？ 新しい評価順っていうのが、
従来は２が最初にあって、１と３がインターリーブされていた。……ということが PR の概要欄と NEWS の修正に書いてある。
パフォーマンス劣化の理由は左辺の評価結果を一時的に蓄える必要があるからか？
いやあ、あっさり変えるし変えられるもんなんだなあ。まあたぶん、Ruby ユーザーの 1 % も変化に気がつかないだろうとは思う。
非効率だしバグらせやすいし、作り込む価値がないと言っている？
自分はもうこの仕様について(穴にはまった実体験から)知っているので、常に穴を意識して書くし、逆に評価順を利用することもあるけど、これまで幸運にも意識せずに来られた大多数のユーザーが、将来的潜在的には驚きとともに多重代入の評価順の詳細を理解させられるんだろうな、ということを考えると、「作り込む価値はある。ただしうまく実装できる限りにおいては」という評価が妥当かなと思う。
最終更新: 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] }]}
最終更新: 2021-06-02T21:11+0900
緑がほぼ埋まってきて残っているのは解けなかった問題ばかり。そこで水色下位に手を出すも下位とはいえ水色はぱっぱっと解ける雰囲気ではない。あれもこれも行列の問題で、問題のその操作で何ができるのかさっぱりわからない。
だから青色。難しかったん。１年くらい前に ABC004 を埋めようとしたときは力が及ばず C 問題までしか提出に至っていなかった。
今回も一発 AC とはいかなかった。原因はすぐに推測できて、緑色が原点から離れない想定が誤っていたのだと思った。
たとえば赤か青の片方が極端に多いとき、外側に広がっていくよりも中心にある緑色の全体を移動させてでも中心に向けて移動する方が低コストになる分岐点がある。
しかしそれを想定するとコードにするのがさらに難しくなりそうで困った。
ちなみにこの提出の方針は……。赤と青をそれぞれ -100 と 100 を中心にして原点の左右で平らに並べる。原点は超えない。数が多ければ外側により大きく広がる。そのあとで緑色を原点を中心として配置していく。左右のコストを比較して赤と青を押しのけながら。
提出に至らなかった１年前の方針は、RGB の数から重心を求めて云々という感じ。ひょっとすると緑の配置拠点を原点に限らず適切に移動することで、WA だった方針のまま AC に持って行けた可能性が？
「J - 長い長い文字列」(提出 #19035422) とか、「K - 転倒数」(提出 #18029328)とか、脳みそに余裕がなくなるとクラスや日本語変数がソースに現れる傾向があるみたい。今回は両方出てきた。(クラスのメソッドの並びが不揃いなのが気になる。左を先に書くで統一しておきたかった)
イメージとしてはビー玉をざらざらと流し込んでから、抵抗の強弱を感じ取りつつ右に左に均す感じ。最大で900個程度の広がりしか考えなくていいからなんとかなっている。
Ruby の他の提出を見るとゴルフをしていなくても 300 バイト台の短い提出がいくつもあるし、内容も、候補を並べて最小値を選ぶ、二分探索で解(極小値)を探すなど、特に大層な道具は必要としていない。それは、頭の中で十分に理解して整理できているから書けるんだよなあ。
できないからソースコード上でメソッドと複数のインスタンスに分割して整理しています。結果としてひと味違った解法になったと思う。
たぶん抗力の計算が間違ってるんだよね。
押した力を上限として０以上それ以下の力しか発生しないはずだけど、なんだか負の抗力によって隣の障害物に引っぱられていきそうになってる。それだと引っぱってる方はともかく引っぱられる方は、必ずしも安定した、低いエネルギー状態にあるとはいえなくなる。
これが問題にならない理由もわかるけど、それはクラスの外部、インスタンスの利用方法にあるのであって、クラスの、メソッドの定義としては間違っている。
最終更新: 2021-06-08T15:27+0900
ABC の４問目で 400 点問題。しかし青diffではある。
時間制限を 10 秒にしてくれたらたぶん通る。しかし実際の制限は２秒であり、３秒ですらない。慈悲はないのか。
Ruby の提出一覧を見ると AC していても軒並み１秒越えであり、処理量がしんどい問題なのは間違いないのだけど、その中にあって１秒を切っている提出もある。ということは、己の考えが足りないのである。ぐぬぬ。
入力を正負ゼロに分けて、正負ゼロの積がそれぞれいくつ作られるかをまず求めた。
負の積が K 個かそれより多いならば、正の数と負の数のペアを考える。ゼロは特に考えることがない。K 番目が正の積の中に含まれているなら、負の数同士のペアと正の数同士のペアを考える。
これで考えるべき組み合わせが多少は減ったつもりになるが、入力次第では何の足しにもならない。本質的に計算量を削減する方法がわからなかった。
それでどうしているか。
K 番目の数を -10^{18} から 10^{18} の範囲で二分探索している。
ペアを、ある数とそれに掛け合わせるソート数列として持っている。K 番目の数の候補となる数が与えられたとき、その数以下の積がいくつ作られるかは、これまたソート数列を二分探索することでわかる。
ペアの数が馬鹿にならない。N (≦2×10^5) のオーダーで存在する。だから「ある数」と「ソート数列」に注目して、ペアをソートされた状態で持っている。そうすると K 番目の数の候補となる数が与えられたとき、かすりもしないペアを予め除外して考えることができる。かすらないとは２通りあって、すべての積がある数以下となるか、すべての積がある数より大きくなるか。全か無か。ここで累積和と、三度目になる二分探索を使っている。
とまあ、こんな感じ。(３つだが三重ではない)二重の二分探索のあいだに、範囲を絞っているとはいえちまちまと順番に数え上げる線形時間の処理が挟まっているのがいただけない。一番重たいケースで 10 秒はがんばった方だと思うよ。知的方面でのがんばりではないけども。
ソート列とソート列の組み合わせでペアを作っているのに、そのときに一方のソート列をばらばらにしてしまっているのが悪いのか？ (短い方を選んでバラすようにはしている)
この回 は「C 問題が解けなくて大爆死した回の ABC」。その後 C 問題を解いて、F 問題も解いたけど、「F 問題が解けたら D と E も解けたつもりでいいんじゃないかな？」と書いたように、F の後でも D と E が解けていなかった。不思議なもので、D 問題は緑埋めをしていた先月に普通に解いていた(提出 #21267825)。緑がほぼ埋まってきて次なるターゲットは水色下位に移ってきている。E 問題 Logs である。解けない緑より解ける水色なのである。
えー、解けました。解けなかったときは何を考えて行き詰まっていたか。
今日の日記のタイトルは「D 問題 Pairs」です。関連は？
これまで二分探索といえばソート済み配列から特定の閾値をまたぐ値を選び出すのに使用してきたのだけど、実はそれだけではなかった。何もない空中から特定の値(解)を見つけ出すのにも利用できるのだった。順序さえ与えられるなら、解が -10^{18} から 10^{18} の範囲に存在すると判っているなら、たったひとつの意味のある値(解)を二分探索してもいいのである。
という気付きが Pairs を解く過程で(まだ解けてないけど)得られていたので、今度はごく素直に、解を決め打ってから最適な切断をすると切断回数の合計が何回になるかという逆算的な解法を発想することができた。そういうことができるとわかっていた。
二分探索を使った解法でかつて最も衝撃を受けたのは Vacant Seat というインタラクティブ問題に対する提出 #2057817 と #2064531 だった。bsearch メソッドから呼び出されるブロックの中でクエリを行っている。いやね、自分も提出 #7970588 の中で二分探索を使って答えを出してるんだけど、そのことと、対象となる具体的なソート列がないまま空中で二分探索を行う、順序はクエリで動的に決定するということの間に、どれだけの隔たりがあることか。
脳みそが不自由だと存在しない制約で思考が枷をはめられてしまうのだなあ。最も基本的なツールといえる二分探索も、まだまだ使いこなせていないのだった。
ところで 350 ms は Ruby で２番目に速い提出なのだけど、どんぐりの背比べである２番目とそれ以降から頭ひとつ抜けて速いのがこの 提出 #15632506 (sushibon さん / 219 ms)。二分探索は行っていない(ソートはしている)。
二分探索というのは人間が考えることを放棄して機械に試行錯誤させる解法なのだけど、人間が頭を使えば無駄なく速く答えを求めることができるのですね。まあ、何をどう考えればいいのかわかりませんけども。
これも空中二分探索。解を決め打ってから考える。もはやおなじみである。
Ruby では唯一３桁 ms に入った(他は４桁)。log１つ分の差だと思う。Nlog^2 と Nlog。単にソートする方のやり方を思いつかなかっただけなんだけど。
同じ青diffでもこちらのほうが Pairs よりわずかに難しいことになっている。
しかしこれは簡単な Pairs ということでいいんではないか？ だって同じように二重の二分探索の真ん中で線形時間の足し合わせを行っていて、TLE にならないんだもん。
概ね 300 ms から 500 ms の間におさまっているから、自分の 1489 ms は最も遅い部類に入る。Pairs を解くヒントが(Pairs の提出一覧はもちろん)ここにもあるのでは？(だったら読むわけにはいかない)
ループの構成は変わらないまま脳筋的努力を重ねた結果、倍近く速くなった。しかし 300 ms にも 500 ms にも及ばない。やっぱり計算量のオーダーを減らす手がどこかにあるのだろう。それがわかれば Pairs が AC できるぞっ。
やったど。246 ms は Ruby では僅差で一番速い。
どこでオーダーが改善できるか。解法の根幹をなす大外の二分探索の log は欠かせない。入力をなめる N もなくせない。なら内部の二分探索を削るしかないのはわかってたんだけど、「log を削らなければいけません」「はい、削りました」ができるなら脳みそはいらないわけで……。
ヒントはこの問題の前に解いた射撃王にあった。log ひとつの差ってちょっとした違いなんですよ。ちょっと見る角度を変えるだけ……でなんとかなるなら脳みそは(略)
実際のところ、二分探索の代わりに shift/pop を繰り返すようにしただけ。
261 ms の提出を読んだ。A 数列の値から添字を得る逆引きインデックスを事前に作成するのがキモであるようだった。A の値の範囲は 10000 以下なので、それが配列のサイズとなったところで大した大きさではない。
言われてみれば、そうだね、という感じ(だけど思いつかなかった)。313 ms の提出も 328 ms の提出も 329 ms の提出も、同じ下拵えをしていた。
やったど！ たまたまぶつかった別の問題ばっかり３問片付けてきたけど、とうとう本丸の Pairs をクリアしたぞ！ (提出日時を見ればわかるけど、今日は５月の下旬なのだ。日記とは？)
これもやっぱり Handshake と同じように二分探索の代わりに shift/pop を繰り返すようにした。Pairs は Handshake と違って A 数列の値の上限が 10^9 なので、逆引きインデックスを用意しておく方法は使えなかったのではないかと思う。
ところで、ぎりぎり３桁 ms には入ったけど、759 ms には負けました。配列の操作でなく添字の操作をしているところが効いてるのかな？
最終更新: 2021-03-24T16:47+0900
解いたあとで他の人の Ruby での解答を見たらバリエーションがいくつか見られた。
これが一番多かったと思う。公式解説に書かれている通りの手順。
これは Ruby で最速の qib さんの提出 #20369253 (191 ms) の解法。
公式解説にはこう書かれている。
マス i と j の距離を d(i,j) として，マス i の色は d(1,i) ≦ d(N,i) ならば黒，そうでなければ白となる．結論としてマス 1 とマス N の 2 点から幅優先探索や深さ優先探索などを行うことで O(N) でこの問題を解くことが可能である．
解法１はたしかに解説通りの手順ではあるが、解答にあたり具体的な距離まで知りたいわけではなく、距離の大小関係だけ知れれば十分なのだ。
解法２の手順は(スタート地点からの距離を測定する)幅優先探索に則っているのだが、一見すると１手につき１マスしか塗れないゲームのルールに反しているように見えるのが難しい。同じことは解法１にも言えて、「マス i の色は d(1,i) ≦ d(N,i) ならば黒，そうでなければ白となる
」が納得できるかどうかに尽きるのだけど、解法２の手順がなまじゲームに似ているせいで考えてしまう。
フェネックとすぬけくんの行動原理として想定したのは公式解説のものと同じ。見立てだけが異なる。どういう見立てだったか。
フェネック(すぬけくんでもいいが便宜上フェネックを選ぶ)のスタート地点を木の根と定めて、すぬけくんのスタート地点の深さを知る。すぬけくんは移動可能範囲を広げるために根に向かって移動する。フェネックはすぬけくんの移動可能範囲を狭めるためにすぬけくんに向かって移動する。出会うのは中間の深さ。すぬけくんは根に向かって移動できなくなった地点を根としてその子孫ノードだけを塗ることができる(だから一直線に根(フェネックのスタート地点)を目指していた)。
結局のところこの問題は一本の辺を見つけ出す問題だった。頂点集合をフェネック側、すぬけくん側に分ける辺がどれかを見つける問題だった。
その手順として幅優先探索(解法１)とその応用(解法２)と深さ優先探索(解法３)とダイクストラ法(未紹介)と、いろいろな方法があって、実行速度の差があった。同じ線形時間でも１回なめるだけで済ませられるのか、２回か、３回か。
今日@2021-03-23 たまたま取り組んだこの問題が同じ方針で解けそうだった。
２地点から深さ優先探索で陣取りをしていって、中央付近でにらみ合って、それからどれだけ相手陣へ侵攻(自陣へ後退)できるかを数えれば答えになりそうだった。
きっちりと隙を見せない after_contest に撃ち落とされましたとさ。
競技プログラミングをするフレンズ @kyopro_friends
サーバル「ABC148F『Playing tag on tree』にafter_contestを追加したよ！ 不等式に等号を入れるか入れないかを間違ってるコードが落ちるようになったはずだから確認してみてね」https://t.co/jcHP4lHFhg
不等号などなかった。先攻後攻を入れ替えたのと、自陣へ逃げ込もうとしてうっかり中立地帯へ迷い込まないように道を塞いだ。
当初方針のまま after_contest に対応したが、どうにも不自然に頑張ったようなコードになってしまった。この問題に関しては、想定解法通りに２通りの距離表を見比べて答えを選び出すのが良かっただろう。
ところで ABC148 はオンタイムで参加していた。A-D まで灰 diff で、E 問題に至ってもギリギリ緑という低難度回。F 問題でやっと水 diff 中位だったらしい。当時１時間を残していながら解けなかったのがこの F 問題。何を考えて解けなかったか。
木の上で追いかけっこをする２人がすれ違うことができない、ということが認識できていなかった。だから偶奇が適切な部分木を選んで逃げ込むことで追跡が躱せるような気がしていた。それじゃあこの但し書きが嘘になるのにね。「なお、ゲームは必ず終了することが証明できます。
」 そんなん考えたら青 diff 上位の「DFS Game」より難しくなるってのにね。
最終更新: 2021-03-15T22:56+0900
本日の ABC。１時間かけて ABCD の４完で、残り40分考えて E 問題が解けずに終わった。ゲーム問題苦手。勝ち筋とか必勝法とか、さっぱり見えない。「自分はこの、先攻後攻が決まった瞬間に勝ち負けが見えるゲームを、きっと楽しくプレイできるんだろうなあ。」
本番中に E 問題が行き詰まっている最中に F 問題をタイトルだけチラ見していた。Coprime の単語が見えた瞬間にあきらめた。別の問題だけど先々月に「Coprime はまた解けなかった。」 完全に苦手意識を持っている。素数とか見たくない。
割と大きめのサンプル３が通ったのでいけると思ったが TLE だった。
考えたことを順番に。
このとき(緑diff精進３問)解いた問題の１つが「ABC 115 D - Christmas」なんだけど、素直に問題の通りに書いた最初の版が明らかに TLE を免れなくて、ださいけど if を使って２回の再帰呼び出しを１回に節約するパスを追加することで AC になっていた。
倍倍ゲームになりうる再帰構造には特別な警戒が必要だということと、それが反転したときに改善効果が劇的だということを学んでいた。今回も最後の lambda F に２行追加して AC。
たぶんグループの作り方が間違っていた。二次ペア三次ペアと芋づる式に相互グループを作るのでなく、それぞれの数ごとに一次ペアのグループを作って、そのサイズでクラス分けをすれば、計算で答えが求まったのではないか。計算の材料にする数字が誤っていたから求まらなかったのではないか。いやでもそのクラスには公倍数の情報が抜けてるのか……。
組み合わせた結果をフィルタリングするよりも、フィルタリングした結果を組み合わせるべきだったのではないか。SQL がそうでしょう？ JOIN する前に WHERE で絞るべきなんだ。WHERE に似ていても HAVING では遅いんだ。
全探索がダメでもある種の探索が許されていたあたり、今日の制約には優しさが感じられるなあ。
これに関連した @kyopro_friends さんのツイートを考えていた。
競技プログラミングをするフレンズ @kyopro_friends
アライグマ「F問題は、COLOCON2018C『すぬけそだて――ごはん――』の難しい版なのだ！ gcd(x,y)=gcd(x-y,y)≦|x-y|だから、72以下の素数の倍数が重複しないようにすればよくて、どの素数の倍数をもう使ったかでbitDPすればいいのだ！」
「
」ってつまり……gcd(x,y)=gcd(x-y,y)≦|x-y|
というような発見があった。ものがよく見えていないと「新発見」が多い。ユークリッドの互除法まで見つけてしまった。開拓者か研究者に向いているのではないか。
最終更新: 2021-03-23T20:00+0900
解説を読んで ABC をコンプリートしようシリーズの１回目。ABC192 で残っているのは F 問題。いわゆるポーションって portion とはスペルが違ったのね。
２回目があるかはわからない。１回目にして解説を読んでから２日間苦しんだ。DP だったんだけど、人類が扱うには次元が高すぎるのではないかな？ 自分には無理。
ソースコードの冒頭にも引用したけど、解説の要諦が次の一文。
dp[i][j][k] = i 番目までから j 個選んだときの和であって、mod C で k に等しいようなものの最大値
自分は最初これを次のように解釈した。
dp[i][j][k] = i 番目までから j 個選んだときの和であって、mod j で k に等しいようなものの最大値
微妙な違いがわかりますか？ mod C と mod j の違い。うっかりミスではなく、理解できる範疇を超えていたから、これってこういう意味だよね、と一段次元が低い誤った理解しか生まれなかった。
引き回すデータ配列の構成を教えてもらってさえ遷移が書けるまで一日かかったんだけど、いざ完成したらこの微妙な勘違いのせいで時々答えが合わなかった。時々。答え合わせに使ったのは次のナイーブな解答スクリプト。N が 30 を超えると実行時間が現実的でないので生成する入力の N は小さめに。テストケースはまだ利用できない。
N,X,*A = $<.read.split.map(&:to_i)
p (1..N).filter_map{|c|
k = X%c
m = A.combination(c).map(&:sum).sort.reverse_each.find{|m| m%c == k }
(X-m)/c if m
}.min
要するに、これを時間制限に収まるように書き直しましょう、という問題だった。それが難しい。
結局一度完成したと思ったスクリプトを囲うようにもうひとつループを重ねた。法が変わると余りは再利用できない。最初から目的地(C)を定めて j を変化させなければいけない。dp 配列の添字 k の上限は j でなく C である。無理だよ、明日にはもう自分でこの文が理解できないよ。
DP であることでナイーブな解答より有利になる点は次の２つ？
j+1 個の組み合わせを生成するのに j 個の組み合わせ結果が利用できる。
その際にキーとなるのが添字 i (「i 番目までから j 個選んだときの和であって
」)。j 個の組み合わせ結果を i (1～N-j)によって分類しておくことで、j+1 個の組み合わせを作るのに利用できる。
たぶんこれって DP のひとつの典型なんだと思うけど、配列の型を示されてさえこの種の遷移(何を残して何を再利用するか)を見つけるのに１日かかった。
見つけた遷移は具体的には、「j を C まで増やしながら、ある j について i 番目の要素(A[i])を i の大きい順に考える。A[i] を採用しないときに dp[j][i] に対応する C 要素の配列は dp[j][i+1] のものと同じ。A[i] を採用するときは dp[j-1][i+1] に記録された C 個の値と組み合わせる」 i と j が解説とは入れ替わってら。
dp[j][i] の値を作るのに dp[j][i+1] (最内ループの直前の値)と dp[j-1][i+1] (中間ループの直前の値の１要素)を再利用している。
勘違いして見えていなかったのは、j=C であり j を 1..N の範囲で変化させる過程で各 j(C) に対応した答えが見つかる……のではなく、C=1..N について j を 1..C の範囲で変化させなければいけないということ。
提出 #20486969 (TLE×11)
主にイテレータを使って書き直したので遅くなるのはわかる。
Array#min の代わりに Array#[] でダイレクトに最小値を取得するようにしたので、special_xx.txt 以外のケースでは改善している。
提出 #20486969 (TLE×11)
同じように Array#min を使うのをやめたのと、イテレータを使わず全て while で書いた。special_xx.txt 以外のケースで上よりさらに少し改善しているが、TLE は TLE。
Ruby って整数演算が足す引く剰余大小比較まで、どれも同じくらい遅い雰囲気。演算コストに差がないなら演算子の数を減らす方がいい？
でもどこに 800 ms も遅くなる要因があった？ もう予測できない。
平均すると最初の提出より１割弱タイムが改善しているけど、意味のある差ではない。
ベースはイテレータメインの提出 #20486969 (TLE×11)。
AC と TLE の分かれ目は４重ループの最深部にあった。
初期値を正の無限大ではなく nil にした。
正の無限大は正常値として扱えるので記述が統一できるのだけど、むしろ異常値として nil や -1 や無限大を設定・検知して、ループをスキップするのが良かった。
ところで、想定上限を整数で表現しようとすると 67 か 68 ビットが必要になる気がして採用できなかった。Float::INFINITY と Bignum の、どちらがいいともいえない。打ち切り条件が ×C ではなく ÷C である理由でもある。
k = m%c や k-=c if c<=k よりも、「実行されないコードが最速」なのだった。負の添字を使った配列参照は組み込まれた機能でありコストは支払い済みなので、使い倒さなければ損になる。いくつかの C について最小公倍数で余りをとれば、より外側のループで DP 配列が再利用できるのではないか。数列 A の偏りと C の組み合わせを調べれば、k が取り得る値が C 種類より少なくなるのを見抜けるのではないか。結局のところ、TLE の原因はおそらく X%C と A%C(の和) がまったくマッチしないせいで４重ループを最初から最後までフル回転させられるせいだと思うから。
「いくつかの C について最小公倍数で余りをとれば、より外側のループで DP 配列が再利用できるのではないか」を実装してみた。話を単純にするために C が偶数の時に j=C/2; i=0 の DP 配列を C=C/2 の DP 配列として再利用した。
たとえば N が上限の 100 のとき、51..100 は普通に DP をする。1..50 は再利用配列を使用して DP をしない。限界は次の２点。
| ケース | X | X (素因数) | A に含まれる 9999999 の数 | 答えが見つかる C |
|---|---|---|---|---|
| special_01.txt | 52142908377193267 | 103×4703×107642319563 | 0 | 1 |
| special_02.txt | 48620189947792921 | 131×2719×18713×7294453 | 1 | 2 |
| special_03.txt | 702276810747319237 | 702276810747319237 | 2 | 3 |
| special_04.txt | 651020109319638361 | 162011×231599×17350549 | 3 | 4 |
| special_05.txt | 611688502818504841 | 82936769××7375359689 | 4 | 5 |
| special_06.txt | 85741517196073082 | 2×11257×32587×116867599 | 5 | 6 |
| special_07.txt | 794433313787770441 | 101×74910361×105001181 | 6 | 7 |
| special_08.txt | 515779426304609041 | 101×5106726993114941 | 7 | 8 |
| special_09.txt | 896297933758956951 | 3×22769×13121611749293 | 8 | 9 |
| special_10.txt | 90842952249996662 | 2×24335153×1866496427 | 9 | 10 |
N はすべて 100。数列 A の要素はほとんどが 10000000 で、０から９個が 9999999 という構成。
special_xx.txt が入力する数列 A の中に値の種類は１から２個しかなかった。C 個選んだ和の余りがとる値は、限られた 9999999 がいくつ含まれるかでしか違いが出なかった。つまり１から10種類。それでも C が 1..N の範囲で変化するうちに余りの数字(k)自体は変化していくし、X%C も変化するんだけど、どうやったらぎりぎり最後までマッチングしないような X が選べるんですか？