最終更新: 2020-06-05T20:36+0900
# @param {Integer[]} rating # @return {Integer} def num_teams(rating) n = rating.size l,r = [:each, :reverse_each].map{|m| a,b = [],[nil]*n rating.send(m).with_index{|p,pi| i = a.bsearch_index{|_| p<_ }||a.size b[pi] = [i,a.size-i] # [# of lower, # of upper] leftside/rightside of p. a.insert(i,p) } next b } r.reverse! return n.times.sum{|pi| (ll,lu),(rl,ru) = l[pi],r[pi] ll*ru + lu*rl } end
最初はこのとき(20190907p01)の解答で使用したデータ構造のどれかが応用できないかとこねこねしていたが、どうにも適合しなかった。そこで改めてこの問題について考えることになったのだけど、たぶんそれはイチから考えるというのとはちょっと違ったと思う。
AtCoder の問題に対して、貪欲法で解ける、DP で解けるというようなことがよく言われるけど、これって実は実際の解法について具体的なことは語っていない。貪欲法とか DP とかいうのは解法の型のようなものでしかない。
二次関数の解について、実数の範囲では場合分けが必要ですよ、ということを教えているようなもので、解の求め方は教えてくれていない。
<脱線>だけど型だけでなく個別具体的なアルゴリズムまで教えてくれないと解けないのです。嘘です。「「"(現在の頂点, 所持している銀貨の枚数) を状態としてdijkstra 法を適用すると、(略) 解くことができます。"」とだけ書かれても、~を状態とするってどういうことですか?」 ここまで教えてもらってもまだ解らないのです。</脱線>
話を戻すと、20190907p01において問題を解くためにインデックスデータを用意した、そのインデックス自体は流用できなかったけど、解答の型は同じだったということ。問題も似てるし。
どういうサイトなんだろう。フォーラムがあるのは結構だけど、Submission を晒す方法がわからない。Count Number of Teams - Submission Detail (32 ms) - LeetCode.pdf 。Facebook でシェアとか、閲覧にログインが必要とか、ボタンがあってもまったくもって無意味なので。
余談:ll(rl) と lu(ru) はどちらか片方だけを記憶すれば十分。pi と n を使った引き算で求められる。でもちょっとだけ遅くなった。Count Number of Teams - Submission Detail (36 ms) - LeetCode.pdf
さっきより遅くなりましたよ……。Count Number of Teams - Submission Detail (52 ms) - LeetCode.pdf。最初が 32 ms で、今度が 52 ms。NlogN と N^2 の違いか。
# @param {Integer[]} rating # @return {Integer} def num_teams(rating) n = rating.size return [rating,rating.reverse].sum{|r| up2,up3 = [0]*n,0 (0..n-2).each{|i| ri = r[i] (i+1..n-1).each{|j| next unless ri < r[j] up2[j] += 1 up3 += up2[i] } } next up3 } end
ヒントだと思っていたものはフォーラムの書き込みのひとつだった。Python で DP ってやつ。公式のヒントはコレ! 「BruteForce, check all possibilities.
」 男前だね。
# @param {Integer[]} rating # @return {Integer} def num_teams(rating) n1 = rating.size-1 rs = [] # rating[] sorted rating.each_with_index{|r,i| j = rs.bsearch_index{|_,| r<_ }||i rs.insert(j,[r,i,j]) } t = 0 rs.each_with_index{|(r,ln,ll),nl| # nl = # of lower ratings than the r. # ln/rn = # of ratings on the left/right of the r. # ll/rl = # of lower ratings on the left/right of the r. # lu/ru = # of upper ratings on the left/right of the r. rn = n1-ln lu = ln-ll rl = nl-ll ru = rn-rl t += lu*rl t += ll*ru } return t end
最初の版も対称形が美しいと思うのだけど、だからこそズルをする余地があるような気がした。
今度のは捨てていたソート済みのレイティング配列を活用することで二分探索の回数を半分に減らしたもの。ループが2つあるけどどちらのループ変数も単なる添字以上の意味を持ってるのがいい感じ。
しかしメモリ使用量が数十 KiB 減っただけで実行時間は 32 ms のまま変わらず。Ruby で定数倍の改善はちまちました四則演算で相殺されてしまうのか、それとも単に N が小さすぎてスクリプト実行のオーバーヘッドが見えているだけなのか。「Constraints: 1 <= rating.size <= 200
」 32 ms はRuntime Distribution のグラフから左にはみだしてるもんね。
Count Number of Teams - Submission Detail (32 ms, less mem) - LeetCode.pdf
これ以上できることがあるとしたら、愚直な Σ 計算をまとめて計算するようなことか。Σk = n*(n+1)/2
みたいに。
O(NlogN) かと思っていたが配列への挿入が O(N) だから O(N^2) になりそう。やってることが挿入ソートと同じだからそうなんだろう。二分探索のためのランダムアクセスと線形よりましな時間での挿入が両立しない。
平衡二分木があれば O(NlogN) が達成できるんだろうか。実は名前しか知らないんだけど。木なら対数時間で適切な位置に挿入できそうだし、平衡を維持するためには左右配下のノード数を知っていなければいけないはずで、そうすると木をたどるついでに左の枝をカウントしていけば木の中での順序が知れる。たぶん。
名前だけを頼りに insert と each と rebalance メソッドだけ持つ木を作ってみたけど、それを利用して元のスクリプトと同じ答えが出るのは確かめたけど、平衡を保つのが難しいということがわかった。
これまで持っていた雑なイメージでは根っことその左右の子供の間でローテーションするだけでバランスが取れるような気がしていたのだけど、全然そんなことはなかった。芋づる式に全域に渡って枝を付け替えなければいけない雰囲気。
しかも Ruby の組み込み配列を使うのよりくっそ遅い。何十倍も遅い。実装がダメで平衡が保てていないのを差し引いても時間がかかりすぎ。N を大きくしても勝ち目がない。
最終更新: 2020-06-18T09:50+0900
ちょっと日記に書きたくなるような、適度に歯応えのある問題だった。問題は、例えば
2 4 6 1 3 5
のような数列が与えられたときに、
1 2 3 4 5 6
のように昇順に並べ替えるためには、いくつの要素を移動する必要があるか、その最小を答えるというもの。
例えば、「2 4 6」「1 3 5」の並びは2要素間の関係において増加しているのでそのまま温存して答えにできるのではないか、逆に、「6 1」の並びは減少しているので必ず介入して解消しなければいけない。
しかし2つの増加列の関係に注目すると、「2 4 6」と「1 3 5」の位置関係が前後しているために、 2 と 4 と 6 の3要素または 1 と 3 と 5 の3要素を移動しなければ答えになりそうにない。
たとえば初期数列が以下の通りだったら、
5 6 7 1 2 3 4 8 9
できるだけ長くなるようにピックアップした増加列は「5 6 7 8 9」と「1 2 3 4 8 9」の2本で、最長は6。
移動せずに済ませられるのが6要素で、他は必ず(ちょうど挿入ソートがソート列の中に挿入先を探して移動するのと同じように)移動させられる。仮に長さ6の増加列が2本あっても、移動せずに済ませられるのは6要素だけ。
たとえば、以下の初期数列に対して、先頭の要素から順に継ぎ足して木を作るとする。
1 3 2 5 4 6
しかしこれは網羅してないながらすでにして冗長。(画像ソース:verbose graph.dot)
ここが思案のしどころ。
[1,2,4,6]
になる。2番目の深さにおいて最善の要素は 2 であり、その他の 3, 4, 5 の後ろが 2 の後ろより長くなることはない。新しい要素は作業配列の末尾に付け加えられたり、既存の要素をより小さい値で置き換えたりする。
数列を先頭から処理するときの作業配列の変遷:[1]
→ [1,3]
→ [1,2]
→ [1,2,5]
→ [1,2,4]
→ [1,2,4,6]
提出一覧を見ると 227 ms というのはいかにも遅い。
ちらちらスクリプトの中身を見てると、二分探索の使用が目につく。それで気をつけて作業配列を見てみると、どの時点でもソート済みの状態が保たれているようだった。
できるだけ増加列の長さを伸ばしたいから、作業配列の末尾から更新位置を探していたし、更新位置が見つからない場合も想定していたけど、どちらにも無駄があった。位置探索はソート済みなのを活かして対数時間で済ませられるし、書き込む位置は必ず見つかる。
たぶん値の重複のあるなしで二分探索の使い方が変わるけど、この問題では重複なしが制約に含まれている。最近「bsearch_index の使い分けが見事」と評したのはこの提出>#13393878。lower_bound とか upper_bound とか -1 とか。Ruby には区別がないけど。
凡人は一足飛びに答えにたどり着いたりはしない。しかしたどり着ける難易度ではあり、さらには提出した後でも発見があった。思わず日記に書きたくなる楽しさ。
特になんということもなかった。作業配列を深さ優先探索のあいだ使い回しするだけだった。
問題名で解説記事を検索してみると、LIS(※) に関して色々な方法があるなかで、自分が唯一知っている方法がぴたりとはまる幸運があったと言えそう。
※トランプ挿入ソートの解説記事を読むといやでも目に入るよね>LIS。ストレートな知識問題だって書いてるところがあったけど、知らなくても解けるし、むしろ問題を通して教えてもらえる、ありがたくも教育的な問題だった。
最終更新: 2020-07-10T21:58+0900
2番目が 60 ms のところ、1番速い提出が 16 ms で済ませてしまっている。いったいどんな魔法を使ったのか、読んでみた。
といっても、require 'matrix'
して pow
(power 累乗) して mul
(multiply 乗算) してるだけに見える。優れたコードはストレートで無駄がない。あえて mul を定義しているのは途中で mod を取りたいからなのかなんなのか。
require 'matrix'
には NArray や NumPy で得られるような恩恵はないと思う。累乗の高速化手法に掛け算の回数をおよそ log2(N) 回に減らす方法があって、最初の掛け算で2乗を作り、次に2乗と2乗で4乗を作り、という感じに倍々で N 乗に迫っていく。
途中の式がどんな掛け算と足し算と係数になるか想像もできないけど、トリボナッチ数列の第 N+3 項を求めるための N 回の計算を約 log2(N) 回に縮めるための行列であり、pow メソッドであるのだと思う。
これぞ線形代数って感じ(すくなくとも自分がイメージできる範囲の)。
素朴な手法から順番に紹介されている。1.再帰 2.配列メモ 3.三変数使い回し 4.行列の累乗
実際は自分の到達点の低さの反映に過ぎない。
最初に読んだときは動的計画法のラッシュで頭がパンクして「もういいです……」と本を閉じた。
その次に開いたときは実装したことのあるグラフアルゴリズムの登場に気をよくしていたところで、ここからが中級だ、と新しいチャプターが始まって、「もう無理です……」と本を閉じた。
182ページのコラムから
もっと高速な漸化式の計算
実は、m 項間漸化式の n 項目は行列を用いるのではなく、各項を初項の線形結合で表して繰り返し二乗法を行うことにより、O(m^2log(n)) で計算することも可能です。興味のある人は考えてみるとよいでしょう。
最終更新: 2020-05-31T18:32+0900
こんな非道な仕打ちがあるだろうか。
AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC WA AC AC AC AC AC AC AC AC AC AC AC AC AC
最初の提出(#13737796)が MLE と WA であって、コンテスト終了30秒前で MLE の解消はできたのだけど、ひとつだけの WA が WA のまま残ってしまったと。
600点問題は解ける解けないの山が最初にあって、どちらかといえば時間をかけてもほとんど解けないのだけど、それだけに恨めしい。
N の制約「0≤N≤10^5
」 0 以上
どうしても完全丸ぱくりになるので提出する気がなくなったけど、N=0 の場合を特別扱いせずに対応できるようにループの中身を半分ずらしたり、配列 B を後ろから前から往復して値を埋め込んでいる処理を2種類の累計値を管理するだけで済ませたりできる。そうすると最後の答えを出すのに sum メソッドもいらない。
f(x) = f(x+B)
ではなく「B を周期として第一項と第二項が一致します」という、感覚に基づいたふわっとした理解になる。精確さに欠けるし、残念なおつむで把握しきれる具体的で単純小規模の対象しか扱えない。
最終更新: 2020-05-26T21:01+0900
解説PDFが奮ってる。これが全文。
x 座標・y 座標それぞれを重複を除いてソートし,十分なサイズの2 次元グリッド上に各線分を刻 み込んでからBFS すれば,O(NM) 時間となって十分間に合います.
座標値(-10^9
以上 10^9
以下の整数)でなく座標値の序列(N個以下とM個以下)でグリッドを作るって発想が出てこないんだよなあ。
そんなこと知らずに、重なってる線分を連結して、交点を列挙して、閉路(多角形)を見つけ出して、包含関係を判定して、多角形の面積の引き算で求めようとしてた。しかも閉路の列挙に関するバグが取り切れなくて完成しない。完成しても間違いなく TLE(Time Limit Exceeded) だし。
名前が出てこないと検索も何もできないよね、この前の「逆元」「モジュラ逆数」みたいなもので(20191118p01)。自分は弧度法への変換だけして Ruby の Complex クラスに投げた(polar, 引き算, abs)。組み込みクラスなので使ってあげよう。
方針を教えてもらっても実装できるかどうかは別問題なわけで……。座標のグリッド化に際して線分の端点を切り詰め忘れて大量の WA。
2番目の提出はデバッグ出力を消し忘れて全部 WA だった。デバッグ出力を標準エラーに出すようにするといろいろ捗るらしいが。
線分の切り詰めバグを修正したら WA だったものがすべて AC か TLE になった。メモリ使用量が百数十MBを超えるテストケースがすべて TLE になっており、AC ケースのメモリ使用量は概ねそれ以下。無限ループ内でメモリリークでもないと思うから、単純に時間が足りないだけだと思いたい。
555 ms!>「すべての提出 - AtCoder Beginner Contest 168」
diff をとらんとわからんくらいの微修正で全部 AC。バグはなかった。
TLE になった手法はこのときの成功体験を再現しようとしたものだった>20191006p01。たぶん今回は問題の規模が大きすぎて裏目に出たんだろう。
Ruby で2人目の AC なのは嬉しいけど、こちらは 2489 ms もかかってるんだよなあ。ソースコードも長いし、メモリも余計に使ってる。早期に INF を判定して終了すれば一部のケースで速くなるかもだけど、最悪ケースの改善にはならないんだよなあ。事前にデータを作り込むんでなく、インテリジェントなアクセス関数を通して仮想的なデータにアクセスする手法ならレイテンシは下がりそう。スループットも下がりそうではあるが。そんなこんなより面積4倍のオーバーヘッドが効いてるんかなあ。
555 ms は驚異のタイムだよなあ。移動可能判定を検索でやってるのがまずダメなんだけど(メモリ使用量は減った)。
Python の AC 提出一覧がこちら>「すべての提出 - AtCoder Beginner Contest 168」 ほぼ一人の独壇場なんだけど、タイムの縮みかたがエグい。2488 ms から始まって 131 ms に至る。
「[AtCoder 参加感想] 2020/05/18:ABC 168 | maspyのHP」
さっきの提出は一から書き直して面積4倍確保を解消したけど、面積4倍のグリッドを作ったままでもグリッド線上を飛び越えて移動するようにすればデメリットは解消する。牛がグリッド線上にいる場合にだけ注意すれば。
特別な工夫は見つけられなかったけど、必要のないことはやってない印象。bsearch_index の使い分けが見事。
翻って自分のスクリプト。o を埋めたり、Infinity を埋めたり、座標丸め関数を4方向分用意したり、各グリッドの面積をすべて事前計算して記憶したり、省けるなら省きたいところに文字数と処理時間とメモリを費やしている。未熟で不安があるから冗舌になる。『テスト駆動開発』(ケント ベック)の表現を借りれば「ステップを刻む」「歩幅は変えられる」。今の自分は細かく刻まなければ進めないということ。
ぱくりです。写経。見比べて書いたわけではないけど、アイデアが同じなら同じになるでしょう。後で見たら PyPy3 で速い提出も同じ道具立てだった。
接続してる線分をまとめたり、交点のない線分を取り除いてからグリッドを作りたい気持ちがあるけど、見込まれる処理の重さに比して改善する度合いが入力依存でゼロになるとあって、何かのついでで棚ぼた的に交点一覧とグリッド座標化された線分一覧が手に入らないかなと夢想してる。