最終更新: 2020-06-15T20:02+0900
日付のあたりに書いた通り解説PDFを読んで実装した。だけどあれ全然答えじゃないね。Chokudai さんのブログで以前読んだような、ちょっとひねってあるのをいかにして典型問題に落とし込むかというタイプの問題だったらしい。ある意味そこまで含めて典型では。でも一度も実装したことのないパターンだから「(現在の頂点, 所持している銀貨の枚数) を状態としてdijkstra 法を適用すると、(略) 解くことができます。
」とだけ書かれても、～を状態とするってどういうことですか？
Wikipedia の「ダイクストラ法」を読みながら雰囲気でPDFに書いてあった方針で実装しようとした。一応答えは出たがサンプル入力ですら一瞬の間を感じさせる激遅スクリプト。
N 個の頂点と銀貨の枚数を組み合わせて状態にするといっても、訪れなければいけない地点は依然として N 個のままなわけで、そのあたりの状態を集約する手つきが具体化できなかった。最終的に提出したスクリプトで「すべての地点を一度でも訪れた時点で完了」としたところとか、「銭なしの再訪に用なし」とコメントしたあたりがそうだと思うんだけど。
苦しんで何度か書き直すうちに原型を失いつつもすっきり書けて、プロファイルをとりながらの実行もすっきりだったから「どうだ！」と提出したら、AC の中１つだけが TLE で脱力。これ以上は無理ですよ。
この段階で他の人の提出を見た>「すべての提出 - AtCoder Beginner Contest 164」。
Ruby での全提出は１ページに収まるほどで、AC していたのは２人だけ。TLE 仲間の提出を覗いてみれば、自分が TLE になった入力(とサンプル)だけ AC していたりして、line_2.txt が何と癖の強い入力であることか。
ダイクストラ法に立ち返らないといけないかと思っていたが、diff をとらないと判らないレベルのチューニングでなんとかなった。不思議。
M.times.map の .map がいらない。すっごく読みやすいんだよなあ。何をやっているのか手に取るようにわかる(笑)。配列総なめが嫌だからって冗長なカウンター変数を用意するところまで。
自分に欠けていた工夫が２つあって、
特に２番目は効果が大きいんじゃないかなあ。キューへの出し入れがボトルネックだから、エンキューをひとつ節約するごとにそこから波及する複数のエンキューが節約されるのは大きい。
それはそれとして、Python は AC だけに限っても５ページの提出があるのがうらやましい。傾向として判で押したように似たような提出が多くはあるが。理由のひとつはヒープ(データ構造)とかダイクストラ法とか、名前のついたアルゴリズムが簡単に利用できるところにある。
読めない記述がある。この行
(v = V[n]&.&SM) ? (next if v>=s || v>2500) : R << [n,t]
演算子(に見えるがメソッド)をドット記法で呼び出せる(それが結合規則を変えるのでゴルフに使える)というのは読んだことがあって、たとえば 1&3 と 1.&(3) は同じ意味になる。でも &.& をどう解釈すればよいか。SM はただの数値変数だからブロック引数化の & ではないと思う。
他にもアロー記法だとか、暗黙のブロック変数(_1, _2 とか)だとか、Ruby 2.7 を読むには知識が足りない。ローカルにインストールしている Ruby 2.5 ではまだ使えない記法だったりする。まだ gem コマンドを一度も使ったことがないから、デフォルト添付ライブラリ(prime とか)の gem 化は歓迎できない？。
ブロック変数には悩ましいところがあって、.map(&f) とか .map(&:to_i) とか書けるときには積極的に書いていきたいんだけど、.to_i ではなく .to_i(2) を適用したくなると途端に .map{|_|_.to_i(2)} と書かなければいけなくなる。.to_i に 2 (と self)を予め束縛した関数がサッと(記述コストと実行コストなしに)利用できるといいんだけど、なかなかそうもいかないらしく、とりあえず .map{_1.to_i(2)} と書けますよ、ということ。たぶん。まだ試したことない。
- 引数の評価が行なわれない
- メソッド呼び出しが行われない
- nil を返す
&.& が何だったかと言えば、nil テストを含んだ & 演算だったと。Swift とか C# にあるやつじゃない？ どっちも使わんしよう知らんけど。
51 ms 縮まったけど本質的な改善ではないと思う(配列４とか比較が雑で適応が限られるし、ない方がいいかも)。シンプルさも失われていいことない。しかも Python (140 ms) に負けてる！ Ruby のバージョンが 2.3 から 2.7 になって、実行前のオーバーヘッドが 40 ms ほど大きくなったと思うんだよなあ(それでも勝ちたい。ユーザー数で負けても質で勝ちたい)。
嬉しい！ 自分で解釈して手を動かして理解してる！ 立派！ 自分で好き勝手書くより他人の考えをトレースする方が難しいものよ。
タイムが縮んでるのはホットスポットである PQ#up_heap (PriorityQueue#update_heap_to_up) で配列アクセスを減らしてるからなんだろうか。キューが長くなるほど効果があると思う。
あと自分は意味まとまりのある変数群を一行で定義するために多重代入を多用するんだけど、実は字数が減るわけではないし、多重代入式に対応する配列値が作り捨てられているとしたら、もったいないことをしてる。
地味に変数の定義位置をずらして無駄な計算を減らしたりもしてる。自分は変数の定義をひとつにしたいがために効果のない値([0,0] とか)を使用して効果のない加算を実行してたりするんだけど、贅沢ではある。関連>20181029。
(自分の提出だよ)
z, y = ２[v]+a, ３[v]+a # z < y if z < s c, d = s < y ? X[v][s-a,３[v]] : [0,0]
X[v] が返す関数が受け取る引数２つ(s-a と ３[v])はその差だけに意味があるから、両方に a を足して、X[v][s,y] とすると引き算１つと配列アクセス１つが省略できる。そもそもが引数が２つある冗長性から生じた無駄であるな。
こういう楽しみがあるのはスクリプトならではなんだよなあ。C++ コンパイラにかかると本質的でない差異は全部同じにされてしまう。そこに性能を犠牲にせずに読みやすい表記を追求する余地があるとも見られるんだけど。
もう一度asmコードをよく読むと不要なはずの配列の初期化が走ってる模様. デフォルトcstrは空のはずなんだけどと自分のコードを見直すと、FpDblクラスだけ配列の初期化が入っていた.
うっかりいれちゃっていた模様. 削除するとgcc-7.5で13%高速化. おおこいつのせいだったのか. それでもclang-8より4%ほど遅いけど気がすっきりした. でも配列の初期化で1割変わるというのは(clangは速いだけに)何か変なことしてるのかな.
プログラマに指示されたらコンパイラは無視できない(こともある？ clang の場合をどう解釈する？)。結果に影響しない表面上はささいに見える違いが思わぬペナルティを生むことも。
プライオリティキューの実装が違うだけで、メインループは共通して richvote さんのオリジナル。
richvote さんの提出は、自分が最初唯一の TLE を食らった line_2.txt という入力が際立って他のケースより速いため、明らかに異なる部分に着目して探索の優先順位を決めている。
それはさておいて、俺の目には２つのプライオリティキュー実装に違いがあるとは見えないんだけど、俺の書き方の方が遅いという傾向が間違いなくあるようだ。
loop{} と書くより while 0; end と書く方が速いというように、気をつけておくと得する書き方がまだあるみたい。だけどわからん。
require 'benchmark'
N = 10_000_000
Benchmark.bm{|x|
x.report('多重'){ N.times{ a,b,c = 1,2,3 } }
x.report('代入'){ N.times{ a=1;b=2;c=3 } }
}
これを Ruby 2.5 で実行してみた。
> ruby25 a.rb
user system total real
多重 1.591000 0.000000 1.591000 ( 1.585992)
代入 0.967000 0.000000 0.967000 ( 0.969697)
多重代入遅いなあ。(bm メソッドを bmbm に変更してリハーサルを行っても同じ結果)
あと最近驚いて、確かめてみたら Ruby 1.8 の昔から一貫して同じ挙動だったんだけど、多重代入の評価順って、単純に右辺から左辺とか、カンマで区切られた左から右ではないみたい。次のスクリプトの実行結果に驚いた。
i, a = 0, [0,1,2] # 準備
i, a[i] = 2, i # どうなる？
puts "i=#{i}; a=#{a.inspect}" #=> i=2; a=[0, 1, 0]
最初に右辺を評価して、それから左辺の評価と代入を左から順番に実行していく感じかな？ 右辺の一時記憶が必要？
多重代入は遅くて時々評価順が難しい、というのが現在の評価。
？ 2.6 でデフォルト gem 化というのを読んだんだけど、普通に require 'prime' できる。gem 化されなかったのか、gem 化について勘違いしているのか。
最終更新: 2020-05-06T23:27+0900
コンテストの配点を見るに ABC 互換。B is for Beginner.
入力が整数なので戻り値が Float になる Math.sqrt は使いたくなかった。ふわふわした浮動小数点よりかっちりした固定小数点が好き。三角不等式みたいな高校時代に知ったような単語が思い浮かんだが関係するかは知らない。両辺を二乗して不等号が維持されるかどうかが気になった。すべてルート付きで正の実数だから大丈夫。
で、１つだけ WA(Wrong Answer)。
こういうことだ。ルート付きの元の不等式が成立するとき、両辺を二乗した不等式も成立する。でも逆は？ 二乗した不等式が成立することは提出したスクリプトで確認した。そのときルート付きの不等式はどうだ？
数学とは便利なもので、イメージが湧かなくても途中の式変形で同値関係さえ確認していけば答えにたどり着いた。実は二乗する操作を２回やっていて、２回目のチェックが疎かになっていた。「提出 #10855551」
とっても高校生向けだと思う。大学入試で同値関係の証明を求められるもんね。そのとき一方通行では道半ば。
最終更新: 2020-05-06T23:27+0900
階乗が法外な大きさになるので余りを答える問題。割り算を含む式の余りが求められなかった。もちろん階乗を計算しきってから余りを求めるというのは実行制限に引っかかるので無理。
モジューラ逆数っていうのがあるんですね、これはすごい pow(down,mod-2,mod) 昨日のD問題逆元の計算どうやればいいのかわからなくて1時間くらい経ってしまった
AtcoderのABC145D問題しっかり理解して頭の中整理してすっきりかけた気がする。Python3です。 pic.twitter.com/Dcs3IfoZ95
mod って演習込みでイチから習った記憶がない。「割った余りですよ」以上の理解がない。キーワードすら知らなくてググりようがない。
Ruby には Python と違って「冪剰余 - Wikipedia」が求められる関数が用意されていないみたいなので(※補足訂正)、拡張ユークリッド互除法を使う方の求め方を Wikipedia(ja) からコピペ実装した>https://atcoder.jp/contests/abc145/submissions/8508807。明日には理解できないとしても「モジュラ逆数」というものの存在くらいは覚えておきたい。
速いからには変わったことをしてる。derive_inverse メソッドが理解できない。法のビットを利用しているみたい。理解できないのは本質を掴んでいないから、演繹が働かないからだろう。「冪剰余#さらなる最適化 - Wikipedia」を実装してるのだろうか、雰囲気的に。
pow メソッドを使って実装された derive_inverse がコメントアウトして残されている。
試したら Ruby 2.5 には冪乗余が求められる Integer#pow メソッドが用意されていた。2.6 の「数値関連のメソッドを実際に定義しているクラス一覧」には載ってなかったんだよなあ。Ruby 1.9 時点では pow メソッドはなかった。AtCoder の 2.3 でもまだないかもしれない。
つらつら眺めてると、require 'matrix' して lup.solve で勝手に方程式を解いてもらえるとか、require 'openssl' すると mod_inverse が利用できるとか、知らない方法が色々あるもんだ。でも LUP 分解が解らなければ見ても使うべきときが判らないし、知っても使えない。『[単行本] 平岡 和幸, 堀 玄【プログラミングのための線形代数】 オーム社』は中座してるし、『[単行本] ロナルド・L. グレアム, オーレン パタシュニク, ドナルド・E. クヌース【コンピュータの数学】 共立出版』もちょっと眺めただけ。若いうちに学校で広く浅くでも詰め込んでおくべきなんだよ。基礎がないと何も積み上がらない。
最終更新: 2020-08-27T19:59+0900
解けなかった。まだ解けていない。考慮すべきが漏れてるのか、何か思い違いがあるのか。
とりあえず、完全に並べ替えても題意を満たせないケースに No を返してみた。該当(AC)１件>https://atcoder.jp/contests/nikkei2019-2-qual/submissions/8356932。
N-1 回の交換だと N 要素の A 数列を完全に思い通りに並べ替えられると思った。ぎりぎり１回足りないのが N-2 回なのかな、と。
ぎりぎり１回足りない条件とは？
A 数列のすべての要素があるべき位置から外れた状態にあり、A 数列のすべての要素が数珠つなぎに位置を交換している、だと思った。
ソート済みの A 数列のどの隣接要素を入れ替えても題意を満たせなくなることだと思った。
逆の例は、B 数列に重複する値が存在する場合や、B 数列の最小要素以下の要素が A 数列に複数ある場合など。その場合は A 数列に区別が不要な要素が存在するということであり、交換回数を節約できてしまう気がした。
これもそうではない例を考えると、A 数列が k 要素と N-k 要素の２グループに分かれて位置を交換している場合が該当する。k 要素をあるべき位置に並べ替えるのに k-1 回の交換を要し、N-k 要素を並べ替えるのに N-k-1 回の交換を要するのだから、計 N-2 回の交換で A 数列のすべての要素があるべき位置に納まってしまう。
だから A 数列のすべての要素が唯一のグループを作って位置を交換していなければいけない。その場合に最大 N-1 回の交換を要する。
というのをコードにして提出したのだけど、WA が半分>https://atcoder.jp/contests/nikkei2019-2-qual/submissions/8366469。答えが二択なんだから惜しくもない。わっかんねーなー。
最終更新: 2020-05-06T23:26+0900
もはや毎週恒例。たかだか B 問題に一日散々苦しんでおいてなんだけども、実行速度にハンデのあるスクリプトで、何の工夫もない総当たりを通されては、まったく釈然としない。
Ds 関数１回は10数msで完了するみたい。Ds 関数１回２回でまあまあ AC (accepted) は出る。でも当てもんではないし、なんだかんだ残った WA (Wrong Answer) が潰せなくて総当たりにした結果、最長タイムが 1053 ms になったと、予期していた TLE ではなかったと。何か手を抜く洞察があれば。
Python でひとつだけ抜けた提出が 100 ms を切ってる。事前作成した実行ファイルを書き出して実行したり、コンパイル＆実行したりの飛び道具は使ってないみたいだし、NumPy の文字も見えない。集合演算をよく使っている。ちょっとわかる気がしない。Python という時点で「for 文に else？ これと同じ話？」>「なぜreturn -1にelseはいらないのか」というところから始まるのだが、それが主たる理由ではない。
目新しいアイデアはない。ただ、「あるノードからあるノードへ移動可能かどうか」というデータを「あるノードから移動可能なノードの配列」へと事前処理しただけ。効果はめざましく、600 ms 台だった入力を処理する時間が軒並み２桁msに落ちた。たぶんほとんどのノード間に交通がなかったのだろう。
残る３桁msは３つだけで、それぞれ 100 ms、849 ms、840 ms。特に 800 ms 台の２つの入力がどういう特性を持っているのか(たぶん辺が多い密なグラフ)。対策したい。
目新しいアイデアはない。Ds 関数の中心にある二重ループを効率的に回すことを考えただけ。ループが総体としてどのように歩を進めているかを低レベルで考える。そしてそれを縮約する方法を。やることは関数の仕様を変えない関数内部のコード変換なので、機械になったつもりで意味をはぎ取った記号(ビット列)を操作して、入力と出力を最短で結ぶイメージ。
Ruby は200ビット整数が普通に扱えて便利。その結果できあがったのが DsMax 関数なんだけど、副作用として……
答えには最も遠い点までの距離しか使わないので１点目はいい。-1 パターンを検出するために、１回だけ Ds 関数を呼び出すことにして、それ以外で DsMax 関数を呼び出している。
いやあ、またしても Python に勝ってしまったなあ。(そういうコンテストではないし、コンテストは終了している。でもゴルフを楽しんでる人もいるし、なんでもいいじゃない)
あ、r -= s は r ^= s の方が良かったかも。
こんなん問題も見んと printf("%s", "答え"); してるんかと思うやん？ 普通に二重ループを回してるんだよなあ。でも自分みたいに総当たりをするために三重ループになってしまってはいない。二重ループのある bfs を２回だけ呼び出して済ませてる。
この bfs 関数、すごく既視感があるんだけど、これを２回呼び出すだけで問題が解決する理屈が知りたいなあ。
ベースは２番目のAC。それの総当たりをやめて、２回だけ Ds 関数を呼び出すことにした。キモは、最初の呼び出しで引数に 0 を選んではいけない、ということ。それが WA と AC を分ける。たぶん 0 だと当たりを引いてしまうんだろうなあ。代わりに何を選ぶかは先の「極まってる」提出を参考にした。
正直言ってこれは入力依存のヒューリスティクスなので、時計を見て時間いっぱいまでランダムな試行を繰り返してまぐれ当たりを期待する手法と代わりがない。Ruby で一番に AC を獲得した提出がそういうものだった。
自分にとって真の提出は「３番目のAC」でいい。総当たりで間違いのない答えを求めても、３倍しかタイムが違わないのだから。
３番目のACの改良版。DsMax 関数で -1 を返すパターンを検出できるようにして、Ds 関数を用済みにした。３重ループの総当たりでも、インチキの約２倍のタイムにまで迫ってきた。(でもこれをベースにインチキをしたら……)
短い方がすぐに読み終えられて理解が早いよね(大嘘)。でもね、コードはソルーションなのだから、理解するヒントは問題の中に存在している。問題を見て、答えを考えたら、コードが理解できる。それができないなら、どれだけ注釈があっても理解はできない。読みやすいコメントのおかげで理解した気になれるだけ。……というのが、20191002からリンクした「わかりやすさについて」からリンクした「C++で３秒だという人のコードを読んでいた」経験からの実感。
同じく20191002からリンクした「ドキュメントについて」に書いたが、ちょっとだけGOLFに走ったコードに足りないのは「基本がわかっている人間に向けた内部を理解する時間を節約するための勘所」だというのが自分の答え。そのために使えるのが意味のある変数名であり、プリミティブすぎるビット演算に意味を与える注釈であり、採用したアルゴリズムや入出力を説明する関数冒頭のコメントなどだ。
但し、但しだ。Easy はコードの性質ではないのだから、Easy なコードという概念はそれ単独では存在しない。猿でもわかる Easy を求めることは理解が伴わないので意味がない。猿を教育するのは自分の役割ではない。求めるのは、第一に「理解すること」。理解しない人間は読者ではないので。第二に「不明瞭な点を浮かび上がらせる質問」。第三があるとすれば「どう書いてあれば理解に要する時間が省けたかという提案」。Easy が主観だからこそ複数の視点に意味がある。
しかしその提案が「ヨーダ記法は目が受け付けないから NG」や「条件演算子は見慣れないから NG」や「unless は一旦 if に変換しないとわからないので NG」や「for や while に付く else は流れがよくわからないので NG」のレベルであれば合意はできないでしょうな。自分だって「大なり記号が混じると条件式が理解しにくくなるから右が正の数直線上に変数と数値を並べるようにしてほしい」とは言わない。そんなのは慣れや癖や縛りの類であり、自分にあるのと同じように他人にも馴染んだルールがあり、それが一部の判断を安全に短絡させ理解を早めるのである。ジャイアニズムには抵抗する。数を恃んで来ようものなら決裂は決定的だ。
俺は数が力だということを否定したいのだと思う(20181228, 20130228)。だから受け入れられなくなる。面白いよね、逆ではないんだ。否定するために受け入れないのではなく、受け入れられない現実が先にあって、その原理に対する理解があとから来る。これをこじつけと言う？
るびまのゴルフ記事がめっちゃ楽しみだった。Rubyist Magazine 0021 号が第一回。著者の日記もゴルフ場もすでに知っていたけどゴルフに興味はなかった。でも解説記事は表層的な意味をはぎ取った言語への(身も蓋もない)理解が深まる楽しい読み物だった。さっき書いた「やることは関数の仕様を変えない関数内部のコード変換なので、機械になったつもりで意味をはぎ取った記号(ビット列)を操作して、入力と出力を最短で結ぶイメージ」にも通じる。「意味」に縛られて「実質」が見えないようでは、「抽象化」が覚束ないと思うのだ。これがまたさっき書いた、「変数名や注釈で意味を与えること」との間でバランスをとるもう一方の考え。
連載を読み直していたら最終回にいいことが書いてあった。「我々が努力して、そして楽しんでいる部分は、基本的なテクニックを抑えた上での膨大な時間を投下して行なう 論理的思考や発想の転換の勝負 なのです。」 基本的なテクニックっていうのが記号盛り盛りの変態的な見た目になってしまうアレ。アレの先にゴルフの真髄があるのだと。
しかし、ゴルフでも Python (191 Byte) に勝ってしまったのだなあ。>「すべての AC (コード長 昇順)」
塗り替えるのが早い！！！ (Python / 182 Byte)
燃えるね。(160 Byte) タイムが約60msから約90msに増えてるのは、入力に対して String#to_i(2) を都度都度呼び出しているせい。ゴルフに魂を売ったようで心苦しい。パフォーマンスを追求する余録で無駄が削ぎ落とされたスクリプトが手に入った、という体でいたい。表記が変態的になるのは「本質」には影響しないから心が痛まないのだけど。
たぶん Perl 勢が参戦してきたらどちらも勝てないね。
ゴルフもまた沼なのか…… (146 Byte)
どっぷりはまっている。(144 Byte)
最終更新: 2020-05-06T23:26+0900
Project Euler の人、という認識の人の日記でこの問題が触れられていた。参加していなかった回。「なんということもない問題」だが Python で TLE とのことなので、Ruby で挑戦。
これが、Ruby の力！(違う)
ICache 変数抜きの提出では見事に(同じ)轍を踏みました>提出 #7886442 (TLE)。
ちなみに Ruby での最速タイムはちょうど３分の１の時間だった>144 ms。文字ごとに出現位置リストを作ってバイナリサーチらしい。魔法は無しか。
あるいはメモリをケチらずに文字列全長に渡って文字種ごとに次の出現位置を……、というのも魔法ではないな。オーバーヘッドでかいし。
最終更新: 2020-05-06T23:25+0900
アルゴリズムがどうとか、タイムがどうとかではない。答えが出たのが嬉しい！ WA (Wrong Answer) はもう見飽きた！
全然実装方針が固まらなかった。何について繰り返し、どうなれば終了していいのか、さっぱりわからなかった。だから初めてまとまった数の AC が出た提出は総当たりだったし、AC でなければ当然 TLE だった。
そのうち N の上限が12と非常に小さいぞ、とか、コスト(a_i)の上限(10^5)は14ビットだぞ、とか気がついて、鍵を32ビット整数(※)にエンコードすることにした。※Ruby の埋め込み整数は32ビットないかもだけど>http://www.a-k-r.org/pub/2016-09-08-rubykaigi-unified-integer.pdf<実装依存ということでスクリプトからは隠されたらしい。
その鍵をどうすれば答えにつながるかという点 は、20110826p01.02の記憶がうっすら影響してる。今回は間違えずに、不安から慎重(無駄)な処理をすることは避けられたと思う。
あとは AC の数より多い WA を潰す長い長い迷路。もうお疲れなのであとは他人の提出を見てネタバレを楽しむのみ。
Ruby でも 500 ms を切ることができるらしい。200バイトちょっとのスクリプトで答えが出るらしい。ネタバレはもうちょっと先にしよう。
タイムとメモリの代表値には最悪の数字が選ばれる。条件式をひとつ付け加えたら、最悪だった 1886 ms が 223 ms に縮まった。これはしてやったり。
鍵の包含関係は気になっていたんだけど(※このときの経験から。「他ののサブセットになってるのがあったら除外できる」)、チェックして除外する適所がわかっていなかった。WA を潰すのでそれどころではなかったし、そのために処理と負荷が増えては本末転倒だし。
あとはこの、完全に手続き指向で長ったらしい解答を根本から覆す天啓が降っては来ないものか。
使われている変数名 dp がすべてを語っているのではないだろうか。このパターンは何度も経験している。「それ DP で」案件だったのだろう。でも DP(動的計画法)の一語で理解できたことがないまま今に至ってるんだよなあ。持つデータに対して頭の整理が追いつかないもので。
平均タイムで見ると自分の解法も悪くないと思う。Ruby の提出で一番速いタイムが 481 ms だから、最悪タイム(565 ms)を記録した最後の入力に対策できれば一矢報いられるのでは？
狙い通りに最悪タイムだった 565 ms が 476 ms に改善した。スクリプトって書けば書くほど遅くなるのが普通だから珍しい。
しかし、多くの入力で実行時間とメモリ使用量が微減している中、02-random-17 という入力だけ特異的に 1788 KB が 3836 KB に増大している。これってつまり何が起こっているんだろう。大量の使い捨てオブジェクト？ どこから？ Array#shift(n)？
桁が違っていて効果に自分でびびっている。「インタープリタ型言語でトップクラスの速さ」。やったぜ。でもやっぱり、ソースが長たらしくて汚い。
(組み合わせではなくコストによる)順序をつけて、不要な処理をスキップし(※nextステートメントの数を見よ。あ、<= にできるところが１か所 < になってる。無駄だ)、ソートにコストをかけないように２本目３本目のキューを細かに操作し(※あ、bsearch_indexの条件が潜在的にバグってる。+ を | にして <= を < にしないと)、答えが見つかり次第打ち切るからこその速さであって、(１本のキューと)手続きが中心になるのは避けられないとは思うが……。
ちなみに、Corvvs という人の提出(https://atcoder.jp/contests/abc142/submissions/7795963)を参考にした(「あ、全適用は S の要素だけでいいんだ」)。この人の ID はもう覚えてしまっていて、この前「あとで知ったのだけど、Ruby には Integer#bit_length という便利メソッドが予め用意されていた」と書いたのだけど、その「あとで」がこの提出だった>https://atcoder.jp/contests/abc141/submissions/7557027。ひと味違った解答を書く人だと思う、それを Ruby で。
そうそう、最初の遭遇はこれだった「Rubyで一番速いのはこれ」。それが「「Rubyで一番速いの」を真似して勉強」へと繋がり、現在の AtCoder との付き合い方が決まった。「自ら取り組み考えた「問題・課題」に対する異なる方向からのアプローチは、よく身に付く貴重な学びの機会」の実践。優れたお手本に事欠かないし、自分の方でもそれを理解する準備が整っている。
最終更新: 2020-05-06T23:25+0900
A 問題よりは難しい B 問題。C, D, E, F は一目見て問題文の理解を諦めたよね。
TLE(時間切れ)は潜在的な AC だという期待が持てるから、はっきり WA (Wrong Answer)だと告げられる方が問題。AC と混在しているあたり、微妙なケースの考慮が漏れている。
問題にあたる方針はこう。長さ K のウィンドウを数列 P に重ねて１ずつスライドしながらウィンドウの中の要素をソートするとする。
スライドに伴いウィンドウからはみ出た要素が直前のウィンドウの中で最小(最大)の要素であったかどうか、また、新しくウィンドウに入った要素が現在のウィンドウの中で最大(最小)の要素であるかどうか。この２点に注目するだけで全体の数列の並びに変化があったかどうかがわかる。
ただしこれだけでは足りない。
pm という変数によりウィンドウ内の要素が最初からソート済みだった場合の考慮を試みている。だがまだ整理し切れておらず、AC が WA になったケースや、逆に WA が AC になったケースがある。
WA がなくなり、AC と TLE のみに。ちなみにこの時点でコンテストはとうに終了している。
答えが得られる main 関数が確定しているのであとは TLE を解消すべく、意味を変えないように注意しながら効率の良い実装に置き換えるリファクタリングに励むだけ。
……なんだけど、３番目より効率が落ちて TLE が増えた。しかし頭の中を整理する役には立った。ウィンドウ内の要素をソートしない手法への転換もこのとき。これが５番目の気づきにつながった。
ウィンドウの中で最大(最小)の要素かどうかを判定するのに、先日の20190907p01.03のデータ構造が使えると気づき、Next メソッドと Gen メソッドをコピペして利用したところ AC に。
ウィンドウ内の要素の並びが最初からソート済みかどうかの判定には、右方向に単調増加の要素がいくつ続くか、というデータを利用した。これを作成するループは、やはり先日の「小細工」としてのデータ LX と RX を作成したものと同じ構造をとっている。
同じく先日の20190907p01.06で使ったインデックスの作成方法とソート方法を利用してタイムを改善した。
係数がいくつでも O(N) だとはいえ、長さ N のフルスキャンを４回も５回もやり、長さ N のデータ配列を10も11も作成すればオーバーヘッドはいかばかりか。一部の入力に対しては初期の提出に比べて３倍の時間をかけているし、メモリ使用量は倍以上。
他からの流用そのままではなく、この問題に最適化した手法であるとか、根本から別物の優れた手法であるとかがないものか。No Idea なんだけども。
主として NextIndex メソッドの無駄と NextIndex メソッドの変数名の間違いを修正したリファイン。ちょっと速くなってちょっと省メモリだが、まあ、小細工。
WA が２つある以外は AC で、タイムもメモリ使用量も優れている。
cnt_up, cnt_k は自分の提出における UP に相当するものだけど、min_deq, max_deq を中心としたその他の大部分は、ちょっと見当が付かないくらい違っていて面白い。どういう着想を持つとこういうコードになるんだろう。
ウィンドウをスライドするものとして扱うのではなく、両端の要素に着目してウィンドウを分類し、カウントしているのだろうか。このあたり(ウィンドウの処理順)、適当な制限条件を付けて最適化が可能な雰囲気がなきにしもあらず。
最大値、最小値それぞれについて待ち行列を用意するものみたい。「Ruby で一番新しい提出」もそう。ポイントは
８番目の提出 (AC / 243 ms / 19124 KB)
いいね。時間もメモリ使用量も「７番目」からさらに改善した。
気がついてる提出を見なかったけど(※主に見たのは Python。Ruby とは提出数が桁違いなんだよなあ)、最小値の方の待ち行列の長さを見れば最初から昇順にソート済みだったかどうかがわかる。
Queue から追い出す処理に while 文が使われてるけど、そこと Array#shift に目をつむると(※)、N 回のループ１つで終わり。余分なメモリ要求も計 2×K 要素の配列だけ。
※キュー１つあたり push がループ全体で N 回なので、pop/shift を合わせた回数も全部で N 回以下にとどまる。Array#shift がどうしても気になるなら、メモリ要求を 2×K でなく 2×N にすれば定数時間にできる。
９番目の提出 (AC / 243 ms / 18428 KB)
Array#shift を定数時間の処理に置き換えようとしたら追加のメモリ要求が 2×N になるどころか N だけになったが、2<=K<=N なので 2×K と N の大小関係は一概には言えない(※最悪の場合がマシだとは言える)。しかも Ruby では速度の改善にはつながらず……。
ところで、C配列のシフト操作と、Ruby の Array#shift の実装が別物なのは言うまでもない。あくまでも原理的な話であって、タダで手に入るオールマイティはないのだから気にして損はないだろうということ。Ruby 1.9 の array.c を見たら内部ポインタのインクリメントで済ませているようだったので、得することもなかったみたい。(そうか。unshift はダメだけど shift は気易く使っていいのか)
最終更新: 2020-05-06T23:25+0900
最初の提出 (TLE)
問題文に書かれた操作をそのままコードにしたらほとんどが TLE で全然ダメだった。ソート済み配列に find_index を使ったのが間違い。
２番目の提出 (TLE)
find_index を bsearch_index に置換したら３つを除いて AC になったが、やはり時間をかけすぎている。
後日の提出 (AC / 221 ms / 30216 KB)
Ruby で一番スマートな解法にくらべてメモリも時間も倍以上かかる力業。例によって例のごとく風呂場で思い付いた。
あとで知ったのだけど、Ruby には Integer#bit_length という便利メソッドが予め用意されていた。Ruby 1.9 にはなかったメソッドだ。しかしこの前ランタイムエラーを食らったから、AtCoder の Ruby(2.3.3) には Array#sum なんていかにもありそうなメソッドがまだ実装されていないことは知っている。参照してるドキュメントのバージョン(複数)も、ローカルにインストールしてる Ruby のバージョン(複数)も、全部がばらばらなんだよなあ。
後日の提出(bit_length を使った版) (AC / 149 ms / 11776 KB)
少し前(20190628)に見かけた MSB 関数をコピペ利用する代わりに組み込みの Integer#bit_length を使うようにしたら、アルゴリズムの優劣は覆せないものの、メモリは同程度、時間は倍に至らない程度にまで改善した。たぶん２回ソートしてるのが良くない。割る２をシフト演算に読み替えて応用が利かなくなってるのに、速さで負けてるあたりがなお良くない。
番外１：最初の提出でソート済み配列の代わりにヒープを使っていたら (AC / 803 ms / 13604 KB)
TLE(２秒越え)にくらべたらまあまあ悪くないタイムでやんの。
訂正：提出したスクリプトに max, min = @h[0], @h.pop という行があるが、min は最小の要素ではない。単に末尾の要素。
番外２：番外１のチューニング (AC / 549 ms / 10252 KB)
これで３割ちょっとの時短。でも JavaScript(Node.js)の提出でもヒープを実装してるのだけど、そちらは 100 ms 台で完了しているのだな。それも値の合計に Q.pop を使用していながら。値の取り出しとそれに続くノードの降下が一番時間を食うというのに。
２本目の待ち行列(FIFO)を用意すればそれをソート済みに保つのは雑作もない(※)、というのがこの問題の肝であった。長さ M を確保しておけば固定長配列で十分でもある。
１本でやろうとするから、余計な面倒と時間コストがかかる。
※やっぱりまだちょっとわかってないかも。割る２をして２本目の待ち行列の末尾に加える要素と、それまで末尾だった要素の大小関係が一見ではわからない。これがわからないから、毎度のソート(順序維持)操作をしてしまう。
たぶん２番目の待ち行列に飛び込むタイミングがキー。そこから導かれる。でも、うーん、はっきり見えない。操作の前後で２本目の待ち行列の全要素が重なりなく前後に位置するというのが。
他人が瞬時に状況を飲み込み、行動することを期待します。優柔不断な人には我慢できませんが、自分が選んだ方針が空理空論で対抗されると、さらにすぐに苛立ちます。特にその異論が重要な詳細を無視している場合はなおさら」「
自分の評判を重んじるのなら、質の高い人間と交際すべし」「
悪い仲間といるよりも、一人でいる方が良い」■不寛容で、体裁を取り繕うことにも意欲がない人間なので、器の小ささ、性格の悪さを露呈させられる、自覚させられる人間からは、距離を置きたいと思っている。■建築家型の性格ページで引用されていた。「意見は認められない。情報に基づいた意見は認められる。誰も無知になる資格はない。――Harlan Ellison」 最高にかっこいいセリフじゃあないか。関連しない？>20190815■■■これもやった。「16Test - 精密性格診断テスト」 結果(443KiB)>「フクロウ型(INTP).png」■解説の「
フクロウ型のように未来や抽象的な世界を常に探求している人」という文言は理解に苦しむ。未来より現実、理論より経験を選んだし、直観型(29%)↔感覚型(71%)の解説はこうだ。「
直観型はイメージや概念を取り扱うことが得意であり、感覚型は五感を通した体験を得意とする傾向があります。」■「かなり高い創造性」の一方「閃き力がない」というのも矛盾するようでどう捉えていいのかわからない。創造性に対する閃きっていうのは即興性に比重があるのだろうか。たしかにそれは皆無。■そして残念なことに性格診断なので「
全動物タイプの中でも最も高い知性を持っていると言われている研究者のようなタイプです」と言われても、知性を計られたわけではなく……。
最終更新: 2020-05-06T23:24+0900
自分は TLE(時間切れ) はおろかひとつの正解にも届いていなかった。
Ruby で１秒未満で終了するのはシンプルな100万回くらいのループだという感覚があるから、100000の２乗になりうるループをそのまま書いても無理だという予想は最初からあった。
たいへん嬉しい。Beginner には Beginner なりの達成があるものよ。
自分は sorted/almost_sorted に対策した余分なデータを「小細工」として追加したけど、この投稿では問題に最適なインデックスを作って利用してるんじゃないかと思う。そこの差が large に分類される入力を処理する時間の差として現れている。
scan メソッドで ps を rs にマップする際に、その処理の最中に、rs の値を利用している。
たぶんここで処理時間に差が出た。
しかし変数jがあまりに謎めいていて、よくわからん。
あ、値としてのjと、添え字としてのjがあるのか。でもわからん。
Pの要素を順になめてインデックスを作成していく。ある要素のインデックスを作成するとき、すでに処理済みの隣の要素を見る。その要素が処理中の要素より大きければ、インデックスでポイントすべきはそれ。小さければ、それのインデックスが指す要素が次に見るべき要素。それが処理中の要素より～(以下同じ)。
中身はパクりだけど形式にはちょっとした違いを加えた。
元のコードの scan メソッドにはひとつ思うところがあって、ref パラメータが実質的にフラグとして機能しているのではないかと、異なる２種類のコードを scan メソッドとしてひとつに融合するために使われているのではないかと、思わないではなかった。
２回分の手続きをまとめたものではなく、関数として抽出できる機能は何かと考えた結果が Next メソッド。Gen メソッドはささいなトリック(※)を自動化するだけ。※Next メソッドの３つのパラメータ _O1, _I, o の多重化に関すること。
時間制限がある中で考えることではないけども。
C++だから速いのではなく、長さ N の一重ループしかないから速い。加えて何がすごいって、C++ なのに Ruby で書いたのより短いこと。
そうなのだ。アホの子は余計なことをして自分から問題を難しくするのだ。
これもループは一重。ただし最初のソートが重い。
戦略は、P の要素を小さい順に処理すること。そういう限定条件をつけることで、LU, RU という自分のこれまでのスクリプトでおなじみのインデックスを、随時局所的にアップデートするだけでも有効性を保ちながら使うことができる。有効性は限定されていて、インデックスの正しい要素を参照すれば正しい結果が得られる、というもの。
まねまね。172ms>https://atcoder.jp/contests/abc140/submissions/7499717
実のところ + [N, N] と + [-1, -1] は完全なるコピペ。+ [N] と + [-1] ではダメだったものがどうしてこれで正しい答えにつながるのか、さっぱり理解していない。RU[N] と LU[-1] に番兵を１個置くのと２個置くのの違いとは。
Pythonので本質は語られている。それに付け加えるのは、P の要素に関する前提知識を利用すればソートにかけるコストを減らせるよねってこと。
99ms>https://atcoder.jp/contests/abc140/submissions/7499891
インタープリタ型言語でトップクラスの速さになった。
| TLE(sorted/almost_sorted) | P の各要素についてナイーブに LU, RU を検索。 |
| 753 ms | ソート済みの入力に対策して LX, RX を導入し、LU, RU の検索を早期に打ち切るように。 |
| 318 ms | LU, RU の検索順を前提に組み込み、それまでの検索結果を利用することで検索時間を短縮。 |
| 172 ms | P の要素の処理順を小さい順と決め、インデックスが有効な対象を未処理の P の要素のうち最小のものに限定することで、インデックスは検索して作成するものではなく、初期化し(決まったエントリを)更新するものに。 |
| 99 ms | P の要素を小さい順に並べるのに、P の要素がとりうる値を利用する。 |
与えられた条件を貪欲に利用することと、データが有効な条件を限定して無駄になることをしないこと、かな。
最初から結論が見えていては自分ほどにはこの問題を楽しめまい。ふっふっふ。
