/ 最近 .rdf 追記 編集 設定 本棚

脳log[20200428] AtCoder Beginner Contest 164/E 問題 Two Currencies



2020年04月28日 (火) AtCoder から精進する者に報いようとする意思を感じる。解説 PDF でさっさと復習するか。■以前一度だけ読んでみたことがあって、「こうやったら解けるんですよ、簡単ですね」とは書いてなかったけど、「何でそうやってみようと思うのか」とか「そうやったものが答えになるのがわからん」みたいな感想を持った。■まあ、そういうのは慣れてから理解が追いついてくるのを待ってもよいのではないか、というのが今の心境。先を見れば問題文が頭に入ってこないレベルの問題がまだまだ控えている。解説読んだってわからんぜ、ていうか読めないだろうな。

最終更新: 2020-06-15T20:02+0900

[AtCoder] AtCoder Beginner Contest 164E 問題 Two Currencies

日付のあたりに書いた通り解説PDFを読んで実装した。だけどあれ全然答えじゃないね。Chokudai さんのブログで以前読んだような、ちょっとひねってあるのをいかにして典型問題に落とし込むかというタイプの問題だったらしい。ある意味そこまで含めて典型では。でも一度も実装したことのないパターンだから「(現在の頂点, 所持している銀貨の枚数) を状態としてdijkstra 法を適用すると、(略) 解くことができます。」とだけ書かれても、~を状態とするってどういうことですか?

 提出 #12489199 (TLE / 2206 ms / 19760 KB)

Wikipedia の「ダイクストラ法」を読みながら雰囲気でPDFに書いてあった方針で実装しようとした。一応答えは出たがサンプル入力ですら一瞬の間を感じさせる激遅スクリプト。

N 個の頂点と銀貨の枚数を組み合わせて状態にするといっても、訪れなければいけない地点は依然として N 個のままなわけで、そのあたりの状態を集約する手つきが具体化できなかった。最終的に提出したスクリプトで「すべての地点を一度でも訪れた時点で完了」としたところとか、「銭なしの再訪に用なし」とコメントしたあたりがそうだと思うんだけど。

苦しんで何度か書き直すうちに原型を失いつつもすっきり書けて、プロファイルをとりながらの実行もすっきりだったから「どうだ!」と提出したら、AC の中1つだけが TLE で脱力。これ以上は無理ですよ。

この段階で他の人の提出を見た>「すべての提出 - AtCoder Beginner Contest 164」。

Ruby での全提出は1ページに収まるほどで、AC していたのは2人だけ。TLE 仲間の提出を覗いてみれば、自分が TLE になった入力(とサンプル)だけ AC していたりして、line_2.txt が何と癖の強い入力であることか。

 提出 #12498094 (AC / 205 ms / 14528 KB)

ダイクストラ法に立ち返らないといけないかと思っていたが、diff をとらないと判らないレベルのチューニングでなんとかなった。不思議。

要修正その1
M.times.map の .map がいらない。
.each の短縮形として .map と書くことがあるみたいだけど、.times (ブロックを受け取る)があるのでここではただの無駄。定数 E で map を受けていたときのなごり。
要修正その2
PQ#deq の変数名 max は min の誤り。
プライオリティキューが必要になるたびにこのとき(20190916p01)の max-heap を使った実装を書き換えて使ってるせい。必要になるのはほぼ min-heap。符号を反転させてそのまま使うのと手間はどっこいどっこい。

 ところで、Python (3.8.2) で今一番速いのがこれ>提出 #12430772 (140 ms)

すっごく読みやすいんだよなあ。何をやっているのか手に取るようにわかる(笑)。配列総なめが嫌だからって冗長なカウンター変数を用意するところまで。

自分に欠けていた工夫が2つあって、

  1. ある頂点から出る辺を予めソートしておいて、除外条件に一度引っ掛かれば以降の辺をまとめて無視してる。
  2. 効果のないちまちました両替をひとまとめにしてる。(ソートした辺がここでも役に立っている)

特に2番目は効果が大きいんじゃないかなあ。キューへの出し入れがボトルネックだから、エンキューをひとつ節約するごとにそこから波及する複数のエンキューが節約されるのは大きい。

それはそれとして、Python は AC だけに限っても5ページの提出があるのがうらやましい。傾向として判で押したように似たような提出が多くはあるが。理由のひとつはヒープ(データ構造)とかダイクストラ法とか、名前のついたアルゴリズムが簡単に利用できるところにある。

 Ruby (2.7.1) のこの提出>提出 #12467639

読めない記述がある。この行

  (v = V[n]&.&SM) ? (next if v>=s || v>2500) : R << [n,t]

演算子(に見えるがメソッド)をドット記法で呼び出せる(それが結合規則を変えるのでゴルフに使える)というのは読んだことがあって、たとえば 1&31.&(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 を返す

&.& が何だったかと言えば、nil テストを含んだ & 演算だったと。Swift とか C# にあるやつじゃない? どっちも使わんしよう知らんけど。

 提出 #12550661 (AC / 154 ms / 14520 KB)

51 ms 縮まったけど本質的な改善ではないと思う(配列4とか比較が雑で適応が限られるし、ない方がいいかも)。シンプルさも失われていいことない。しかも Python (140 ms) に負けてる! Ruby のバージョンが 2.3 から 2.7 になって、実行前のオーバーヘッドが 40 ms ほど大きくなったと思うんだよなあ(それでも勝ちたい。ユーザー数で負けても質で勝ちたい)。

 参考にされた!>提出 #12916854 (146 ms)

嬉しい! 自分で解釈して手を動かして理解してる! 立派! 自分で好き勝手書くより他人の考えをトレースする方が難しいものよ。

タイムが縮んでるのはホットスポットである PQ#up_heap (PriorityQueue#update_heap_to_up) で配列アクセスを減らしてるからなんだろうか。キューが長くなるほど効果があると思う。

あと自分は意味まとまりのある変数群を一行で定義するために多重代入を多用するんだけど、実は字数が減るわけではないし、多重代入式に対応する配列値が作り捨てられているとしたら、もったいないことをしてる。

地味に変数の定義位置をずらして無駄な計算を減らしたりもしてる。自分は変数の定義をひとつにしたいがために効果のない値([0,0] とか)を使用して効果のない加算を実行してたりするんだけど、贅沢ではある。関連>20181029

 改善点みっけ

(自分の提出だよ)

	z, y = 2[v]+a, 3[v]+a # z < y
	if z < s
		c, d = s < y ? X[v][s-a,3[v]] : [0,0]

X[v] が返す関数が受け取る引数2つ(s-a3[v])はその差だけに意味があるから、両方に a を足して、X[v][s,y] とすると引き算1つと配列アクセス1つが省略できる。そもそもが引数が2つある冗長性から生じた無駄であるな。

こういう楽しみがあるのはスクリプトならではなんだよなあ。C++ コンパイラにかかると本質的でない差異は全部同じにされてしまう。そこに性能を犠牲にせずに読みやすい表記を追求する余地があるとも見られるんだけど。

 即セルフツッコミ「C++ コンパイラにかかると本質的でない差異は全部同じにされてしまう。」

もう一度asmコードをよく読むと不要なはずの配列の初期化が走ってる模様. デフォルトcstrは空のはずなんだけどと自分のコードを見直すと、FpDblクラスだけ配列の初期化が入っていた.

うっかりいれちゃっていた模様. 削除するとgcc-7.5で13%高速化. おおこいつのせいだったのか. それでもclang-8より4%ほど遅いけど気がすっきりした. でも配列の初期化で1割変わるというのは(clangは速いだけに)何か変なことしてるのかな.

プログラマに指示されたらコンパイラは無視できない(こともある? clang の場合をどう解釈する?)。結果に影響しない表面上はささいに見える違いが思わぬペナルティを生むことも。

 実装比較。この件>>20200428p01.07

  • 提出 #13001464 (1349 ms) 自分のプライオリティキュー実装を利用した richvote さんの提出。
  • 提出 #13001205 (1273 ms) 自分のプライオリティキュー実装を基にした? yappy0625 さんの実装を利用した richvote さんの提出。

プライオリティキューの実装が違うだけで、メインループは共通して richvote さんのオリジナル。

richvote さんの提出は、自分が最初唯一の TLE を食らった line_2.txt という入力が際立って他のケースより速いため、明らかに異なる部分に着目して探索の優先順位を決めている。

それはさておいて、俺の目には2つのプライオリティキュー実装に違いがあるとは見えないんだけど、俺の書き方の方が遅いという傾向が間違いなくあるようだ。

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 化について勘違いしているのか。