最終更新: 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 が選べるんですか？
最終更新: 2021-04-06T17:58+0900
昨日あった ABC。今晩には ARC があるので復習が忙しい。
正規表現を乱用する問題だと決めつけて考えた。使える限り最善でなくてもかえって難しくなっても正規表現を使う。
パターンには改良の余地がある。たぶん /^([a-z][A-Z\n])+$/ で良かった。
$ は改行の前でも文字列の末尾でもマッチしたと思ったけど、フラグの影響がどう出るかが不確かだ。そして Ruby のフラグは JavaScript のフラグと比べてあべこべな雰囲気がしてわかりにくい。
入力が英大文字小文字だけだから大小の判別は１ビットを見るだけでいいんだけど、正規表現だから関係ない。
C 問題にしては……と疑いをもったが、テキトーに大きい桁を与えてもいけるみたいだったので問題の通りに関数 f を定義してシミュレーションした。本当はテキトーに大きいだけだとすぐに桁数の少ない値に収束してしまいかねなくて、そうではない嫌らしい値が与えられるかもという疑いがまだあったのだけど、とりあえず投げてみるスタイル。
最近誰かがツイートで Integer#digits メソッドに言及していたので初めて使ってみた。適所では？ そういえば D 問題でも使っていた。
やってきました因縁の D 問題。前回の虐殺劇が記憶に新しい>20210206p01.02。今回も E 問題が緑色なのに対して D 問題が水色だったりして、正答数に逆転があったもよう。
あれ？ やるだけ？ という感想はあまりに素直。たしかに優秀な人は目をつぶっていても答えにたどり着けるのかもしれないが、凡人は周到に落とし穴を探し出さなければいけない。
それは１の位についてだけ当てはまらない。基数が３でも４でも５でも、数１は０より大きい１番目の数で変わらない。
そしてこれが、基数の種類を答える問題でないことの傍証になる(そういう誤読が多かったらしい)。無限大の答え方が問題文中にないからだ。
二分探索の下限に d+1 を、上限に M+1 を設定していたのだけど、M+1 の方が d+1 より小さいことがあるから、答えを導く引き算の結果が負の数になるケースがあった。
手で計算しているときは自然と自然数の範囲でものごとを考えてしまって例外ケースを無視してしまいがち。
早期に AC を得ていた複数の人が上限を定めない二分探索を行っていたようだ。kotatsugame さんがこの奇妙な二分探索の振る舞いについてツイートしていたので存在は知っていたが、自分で使えるほどには知らないし思い出さない。
7 WA のあとの AC。どちらの落とし穴もテキトーな入力を与えて出力を見るデバッグで発見した。１桁のケースはタイプするのも簡単だし、それでいて境界に近くてバグが潜みがち。嗅覚を働かせよ。
えびま @evima0
(D 実はもともと「9 1」っていうサンプルがあったんですが、出題の意義が 1/3 くらい消滅する (「1 9」だと 2/3 消滅) ので消してもらいました) https://t.co/NNcbAu6GjF
このツイートはもっともで、そうでなければ D 問題としては易しすぎて出題されなかったと思う。といってもこれだけいくつも罠があって目配りが要求されるなら、AGC の A 問題といった風情もある。
自分より上位の人は仮に D 問題の罠にはまったとしても、さくっと E 問題を片付けてから帰ってきて、結局 E も D も通してしまうというムーブができてしまう。(そもそも罠にはまらないか)それができるからこそそのレイティングなのだ。自分がそれをやろうとすると虻蜂取らずになるのが目に見えているので、１時間かけて D 問題を通しました。今回の成績はABCDの４完最遅レベルでレートは横ばい。
競技プログラミングをするフレンズ @kyopro_friends
フェネック「もともとD問題でXが1文字のケースを、アライさんは2個か3個しか用意してなくて、それだとWAのケース数でコーナーケースがバレそうだからたくさん増やすようにアドバイスしてみたんだけど、どうだったかな？」https://t.co/FxcvbhUJNL
AC が出るまでは WA の数を見て方針を疑ったり挫けそうになったりしたけど、１アイディアで 7 WA が 1 WA にまで減ったりしたから、まあこういうことなんだろうと予想はしていた。まんまと手のひらころころ。
プライオリティキューを書くだけの問題。まあその「書くだけ」ができなくて 2 WA するのが自分なのだけど。
……だと思ったら、Ruby で最も速い複数の提出が Hash を待ち行列に使っていた。keys.min で最小値を都度取り出す使い方で、それでいて速い。えええ？
あと、久しぶりにプライオリティキューを書いたから速度改善テクニックを１つ忘れていた。ヒープを整理するときに都度都度要素を交換しながら上昇(下降)するのでなくて、ローテーションする感じで、いくつかの要素を順番にスライドさせてできた空きに追加要素を置くのがいい。
最終更新: 2021-05-07T14:00+0900
先週末の ARC。ABの２完でレートは横ばい。ちょっと背伸びして C 問題が今やっと解けたので日記にする(べつに考え続けていたわけではなくて、オラクルが降ってくるのを待っていたのです)。
一応制約は掛け算していたんだけど、まずは素直に数えて確実に答えを……TLE。見れば一次 の k のΣなので機械的に変形して……AC。
間違った式の変形に５分以上の時間をかけてもしゃーないので、TLE は避けられない。今は(ARC の１問目に対しても)ステップを刻まなければ、答えにたどりつくことさえ覚束ない。
どれだけ１円を払っても数の種類は１しか増えないので、基本となる操作は何回２円を払って絶対値を変化させられるか。±B が境界として存在していて、|B| から 0 へ向かう変化と -|B| から負の無限大へ向かう変化が考えられる。反対側の値は１円余らせておくだけでいい。0 を挟んで -B から B の範囲を数えるのが面倒か。親切にも B=0 となるコーナーケースがサンプルのひとつになっている。もうひとつのコーナーケースが C=1
2 WA のあとの AC。±B と 0 と、それらで区切られた４つの区間を愚直に数えた。
翌日になって機械的に式を整理したもの。できれば if による分岐を消したかったのだが。
問題の見通しは難しくない。表のスコアと裏のスコアと、手番を渡すか否かのフラグ(子孫ノード数(=スコア計)の偶奇)があって、それらを葉からボトムアップで積み上げていけば先手、後手のスコアが即座に解る。
制約の 1≤ の解釈に一瞬詰まったけど、p_v<vp_v の上限が v であることで、逆向きにスキャンするだけで子から親へ順序よく処理できる親切設計だとわかった。
最後まで解らなかったのは青木君高橋君が採用する最適な行動がいかなるものであるか。二人が何を指標にしてどの子を選ぶのか、それが解らないでどうしてコーディングができる？ 何をコードにする？ 自分はこの、先攻後攻が決まった瞬間に勝ち負けが見えるゲームを、きっと楽しくプレイできるんだろうなあ。
odd.sort_by!{ _2-_1 } と even.each(...) がキモ。これが二人の戦術。
最後まで見えなかった even.each についてもう少し。
even は潜って戻ってきたときに手番が入れ替わらない子ノードを集めた配列。表のスコアが裏のスコアより高いものは手番(※広辞苑にはテツガイの見出ししかない。テバンは業界用語か？)を持っている方がさっさと潜って表のスコアを得てしまえばいい(裏のスコアは相手に渡る)。では裏のスコアの方が高いものは？
裏のスコアの方が高いものは、できることなら相手の手番で相手に選ばせたい。そうすれば表のスコア(低い)が相手のものに、裏のスコア(高い)が自分のものになる。それが可能になるのは、潜って戻ってきたときに相手に手番が渡る子ノード(odd 配列)が奇数個ある場合。手番というババの押し付け合いに勝てる。
Ruby の他の AC 提出(今のところ２つ)と比べて遅かったので出し直し。100 ms 縮んで遜色がなくなった。省メモリを目論んだが結果的に増えている。配列の配列の配列がよくない。
ところで、再帰呼び出しを行っている解答を手元で実行してみたらいくつかのケースで stack level too deep (SystemStackError) が出て速度比較ができなかった。PC が貧弱なんだな(環境変数か？ その解決法はドーピングぽい)。
人類の手には多少余るとしても、プログラマを信頼し、力を与えてくれる言語が好きだ。安全のためと称して枷をはめようとする言語は選ばない。安全な」■git は素直でパワフルな道具>20181118p01。リンカは素直で馬鹿な道具>20181102。Nintendo Switch の UI>「「あまりに親切すぎるUIは冗長になる」という考えのもと、プレーヤーを信頼して意図をはっきりさせたかった」。ユーザーの意図を反映するかわりに押しつける道具>20150410。鈍 は退屈だ。
while queue.empty?.! というループを見つけて、二度見では理解できなくて三度見直した。見たことのない字面だから nil許容演算子(&.)なのかと最初は思った。ドットノットが出てくるのってすごい。最初に while ! queue.empty? が浮かぶでしょう？ そうしたらそこから until queue.empty? へも至るでしょう？ 演算子にドットを付けて呼び出そうっていうステップが割り込む余地はないように思う。そういう書き方のパターンを考えたことがなかった。いやまあ自分は最初に until が浮かぶので(「キューが空になるまで繰り返す(until queue.empty?)」)、引き出しのひとつとして蓄えたうえでしまいっぱなしにするんだけど。最終更新: 2021-05-07T14:21+0900
今日の ABC の C と D はちょっと傾向が違ったよね(E と F は時間切れで読んでいない)。C はむしろ復古的かもしれないけど。
どこに着目すれば数えられるのか、わかりますか？ わかりません。
テキトーに注目して数えて、(÷２では)ダメだとわかって(÷３で)やり直して、31 分かけて鬼の羅列である。
(構造の)理解に頭が必要ないという意味で、これも可読性に優れた読みやすいソースコードの例なんですよ。似たような例にすべての繰り返しを for ループで書くなんてありますね。for さえ解れば鬼に金棒、馬鹿の手にハンマー。目に入るすべては釘。打つべし打つべし。
だけどプログラムは構造化と抽象化を(必要である限り)繰り返して、人間はよりハイレベルな意味を読み取らなければいけないんです。あれをどーしたこーしたなんて作業手順を(人間に向けて)仰々しく並べ立てることに意味はありません。それはソースコードの役割であって、人間に向けたコメントには意味のあることを書いてください。
これって、黒のマスが１つの塊(ドーナツではない)であって、黒の内部に白のマスが島になっていることがない(逆に黒のマスはたった１つの島になっている)ってことだと読んだ。そのあとで補足的に「白に塗られた任意の 2 マスは、辺を共有するマスへの移動を繰り返し、白に塗られたマスのみを通って互いに到達可能である(マス目の一番外側のマスは全て白に塗られていることに注意してください)
」ともあるし、問題文は慎重に
書かれていたと思う。
多角形の解釈についても、色が塗られたグリッドであって座標空間上の点列ではないのだから、書かれていないものを見ようとして見るべき角が見えていなかっただけでしょう。
数学の言葉で書かれた制約の読解に普段苦労するので(20201122p01)、今回の問題文に文句はない。
すごくいい。そうか、ドット絵師と 3DCGモデラーがいただけなのか。
図形です。
制約が 10^5 だからどうかなーと思ったけど、普通に数えられる範囲だったみたい。手元ではサンプルに２秒以上かかってたんだけど、ジャッジサーバーは速かった。
１時間かけて、コンテスト終了１分前の提出。よかった……よかった……。
格子点を数える問題で、入力を小数で受け取るのはやっぱり怖い。小数点以下第４位までって書いてあるので、(文字列のまま) 10000 の下駄をはかせて、ついでに諸々の座標が正の範囲に収まるように平行移動した。負の数が混じると整数除算の丸め方向が期待と異なっていて面倒くさい。
# 0 を足すと答えが変わります。難しすぎるでしょ？ -1/2 #=> -1 0-1/2 #=> 0 # 1 (イチ)が変数 l (エル)で、中身が正の数だったり負の数だったりすると、もう予測できないでしょ？
上記は Ruby の挙動。仲間はずれらしい>「整数同士の除算演算子の挙動 (C言語、C++、Scala、Java、Rust、Go言語、PHP、JavaScript、Perl、Python、Ruby、Elixir) - Qiita」 Python の整数除算(//)も同じく負の無限大方向に丸められるとか。
他の人の Ruby での提出を見ると、入力を to_r するものが多かった。r は Rational の r. 使ったことがないと使えないし、思いつきもしないのだ。
二分探索の探索範囲をちまちま限定したところで、倍の違いが試行１回の違いにしかならないのだから、２つのループは１つで十分でしたね。これは円を４分割して数えられないか考えていたのが尾を引いている。
競技プログラミングをするフレンズ @kyopro_friends
アライグマ「D問題は、円の中の格子点のx座標としてありえる値の範囲がX-R～X+Rだから、x座標を決めたときの格子点の個数が求められればいいのだ！ 誤差が大変だから整数で計算して、負の数の切り上げや切り捨ての計算に気をつけて……、罠がいっぱいあって大変なのだ」https://t.co/6z8erFU3Ym
実は二分探索がいらなかった>画像。三平方の定理！ 中学生！
三平方の定理。速い！ 短い！
Integer#sqrt なんてニッチなメソッドを使ってみた。
ところで、やっぱり **2 は遅いみたい。引き算を２回評価することになっても覆らないくらいに。
Ruby での提出を早い順に見てるんだけど、どの人もどの人も平方根をとって計算で格子点の数を求めていた。10行以下のスクリプトで。それが間違いなくすごいんだけど(だって開始後30分ぐらいでの無駄なく短い提出だ)、それらをことごとく撃墜した３つの入力(handmade_marginal_{01|03|05}.txt)が、今回はいい仕事をしていたなと。単に to_f を to_r にしたところで、三羽烏のひとつしか超えられないみたいですよ。
Rational だけでなく BigDecimal の存在も忘れていた。これは「任意の精度で 10 進表現された浮動小数点数を扱えます。
」 to_d の d は (big)decimal の d. to_f を to_d にしてもやっぱり３つのうち２つが WA になるようなのは、BigDecimal#sqrt を使わないで Math.sqrt を使っているのが良くないんでしょうか。Math モジュールは、標準とはいえ require が必要な添付ライブラリである BigDecimal を知らないのが普通だと思う。
提出して確かめようとしてわかった。BigDecimal#sqrt を使うとサンプル３で既に TLE が避けられない。
入力は Rational で受け取っている。Math.sqrt の結果を検算して条件を満たす限り±１の微調整を施し続けている。そして大事なことは、±１した結果の正当性も確かめている。
単純に±１するだけ、しっぱなし、では、handmade_marginal_{00|04}.txt に捕まってしまうようだ。
書き方を洗練させた結果がたぶんこの提出 #20009989 (kyoshida さん)。find メソッドと count に加算する前の nil チェック。
左右の点のうち１点が二分探索で見つかりました。左右の点の中間座標は円の中心に由来して明らかです。ではもう１点は？ a1 = x*2 - a0
違いは１行だけ。Math.sqrt の結果を(floor ではなく)小数点以下第５位あたりで丸めていたらどちらも AC だったんだろうかダメです。
これが Integer.sqrt の実装らしい。
def isqrt(n):
x, y = n, (n + 1) // 2
while y < x:
x, y = y, (y + n // y) // 2
return x
Math.sqrt とは別に用意する価値があるからこそ存在しているのかな。ニッチとか言ってしまったが、こちらが使い所を知らないだけなのか。
自分は今回も Sqrt Inequqlity のとき(20200316p01)も、浮動小数点数を単純に嫌ったり怖がったりして難を逃れたけど、こういう風に限界を見極めて対応できるの、かっこいいよなあ。
B 問題の出力例はスペース区切りだけど、問題文は「A′ の要素を空白区切りで順に出力せよ。
」という表現になっている。
ここを参照すれば間違いないという定義があるわけではないけど、空白が white spaces の意味なら、ここに改行もタブも含まれると考えるのが普通(※要注意ワード)。自分は「スペース」(ASCII 0x20)と「空白文字」を使い分けているし、AtCoder にもそのように期待している。
というわけで、わざわざ .join(' ') はしない>提出 #19962733。
ダメです handmade_marginal_{00|04}.txt に捕まってしまう。Math.sqrt のアルゴリズムに起因して誤差が蓄積するらしい？
最終更新: 2021-05-04T20:49+0900
先週末の ABC。例によってお風呂で考えるも頭が爆発して無理だと思われた F 問題が、なぜか今日取りかかってみれば解けたので日記にする。
すごく難しくて、じっくり 10 分の時間をかけた。
Aoki と Takahashi の文字列を２回書いているところに余裕のなさが見える。間違えるくらいなら全パターンを網羅して並べればいいんですよ(言っていることが違う>20201101p01.03)。
A 問題より簡単だった。条件を満たすものが１つでもあればいい。Array#any? メソッドの出番です。
ところで空配列に関して、[].all? は true を返し、[].any? は false を返す。この違いによってメソッドの選択が制限されることがあるかなと一応警戒するんだけど、特にそういう違いは生まれないみたい。むしろそうならないようにデフォルト値が選ばれている。罠があるとしたらそこではなく、穴に落ちるときは all? を選んでも any? を選んでも落ちる。
制約が K に関して全探索しろと言っている。
Ruby で最も速い提出(492 ms)より倍以上遅いんだけど、どういうことなんでしょうね。
本当は今日は F 問題をやるつもりはなくて、この C 問題を速くするつもりで取りかかったのだけど、優先順位をつけた深さ優先探索でやろうとしてうまくいく見通しが立たなかったのだった。
45 分考えた。等差数列の和の公式に２種類あることはこのときに確認済みなので(20201101p01.02.01)、今回は使いやすい方を選ぶことができた。
珍しく解答の中にコメントがあるのは、書いておかないと脳みそからあふれて何度でも最初から考え直しになるからです。紙と鉛筆を用意すべきなんだよなあ。
本番中は残り時間が 30 分しかなかったので問題文が短い F 問題に先に取りかかっていた。同じように考えたかどうかはわからないが、E 問題より F 問題の方が多くの人に解かれていたようだ。自分はどちらも解けなかった。
制約が３重ループを許すと言っている。
解答の後半はもう３回目になるあの形。実行速度にハンデを背負った Ruby でのタイムの詰め方は、このときに研究し尽くした>E 問題 Traveling Salesman among Aerial Cities。
惜しい。とても惜しい。時間制限が２秒なのだけど、実行を打ち切られたときは 22xx ms というタイムになる。32 ms 詰めれば AC になるぞ。
ハッシュ表を使っていたところで配列を使ったら余裕の AC。
必然性があってハッシュテーブルを選んでいたわけではなくて、Hash のデフォルトプロックありきでスクリプトを構成していたから、使っていた。TLE は邪道の報い。
実は唯一の TLE は最も重いケースではなかった。この提出では TLE だった 21_large.txt のタイムが 135 ms だ。
前半部分で選ばれた魔法石がどうがんばっても連結できないとわかれば、後半の３重ループはスキップできる。そういうこと。
前半部分で距離の確定を双方向からやらずに片方向で済ませてみたら、平均的には速くなったけど、一番遅いケースでは 25 ms しか違わなかった。
Integer#times を while ループにするだけで 200 ms 縮んでやんの。そんなに違うの？ times はイテレータの中では速い方だと思ったけど。
転倒数って固有名詞なのかな。公開された PAST の過去問をやったときに見た>20201111p01。K 問題。それが解いてあった(提出 #18029328)からといって、何かが役に立ったということはない。残念。
最初に、k を増やして数列の初項を最後尾に送り込んだときに、転倒数がどのように増減するかがわかった。わかったからわかったとしかいいようがない。こねくっていたら、転倒数の増減が簡単な計算で求まることがわかった。
それから、転倒数の初期値の求め方を考えた。BIT で殴るのではない、頭のいい方法があるのではないかと考えたが、思いつかなかった。
BIT です。Ruby や Python で速い提出も同じだったので、転倒数はこう求めるのだ！ という頭のいい方法はないのかも。
実は A 数列をスキャンして作成していた配列 I は不要だった。
BIT を使って転倒数を求める手順も、考え方次第でひと通りではないということ。ソート列を必要とする方法よりは必要ない方法を、BIT へのお伺い(対数時間)が２回になる方法よりは１回で済む方法を選びたい。脳みそはタダだけど計算資源は有限。