脳log[2020-10-23～]

最終更新: 2020-10-31T00:45+0900

♪ [AtCoder] AtCoder Beginner Contest 180／D,E

 D 問題 Takahashi Unevolved

数弱さんには頭が痛い問題だった。

 提出 #17475334 (WA)

 提出 #17517315 (AC)

経験値１を加算して増える強さを A と B で比較する。

強さが増加するに従って必ず A を掛けた方が B を足すよりも強さの増加量が増える。(A が１より大きい整数だから)

対数を使って強さの増加量が逆転する境目を求めたのだけど、それは A,B,X の関数であって、Y による制限が考慮されない。

WA だった提出では Y を考慮して上限を定めていたのだけど、境目が負になる場合を考慮して下限を 0 に規正することができていなかった。

コンテストが終わってから問題を明らかにするテストケースが見つかってデバッグができたが、遅すぎた。

10^{18} という制約の大きさにびびって対数を持ち出したけど、A が最小の 2 であっても 10^{18} <= 2^{60} だから、A を使用した方が得する境目は高々 60 なのだった。頭痛の種を自分で作り出していた。

いや違う。比較対象は上限が 10^9 の B だから、境目の上限は高々 30 か 29 だ。

どちらにしろ簡単なループで求められたのだな。同じ手は食わない>#17612685 (翌週の ARC にて)

 E 問題 Traveling Salesman among Aerial Cities

コンテストが終わってから問題文を読んだ。イメージが湧きやすくていい問題名だと思う>Aerial。

 提出 #17485932 (TLE×13 / AC×13)

2**17*17*17(=約3800万)回のループであり、サンプルですら TLE になるのがわかっていたが、ビギナーはワーシャルフロイド法が書けただけで満足なのです。これ以上は解らないのです。

以前解けなかった問題で参考にした提出。「後半はワーシャル-フロイド法に見える３重ループ。ただし街と街を結ぶ中継地点(一番外側のループ)は街ではなく経由地のリスト」。これをチラ見しながら書いた。

 提出 #17516238 (AC / 1933 ms)

ダイクストラ法でコスト順に点を繋いでも時間がかかりすぎるのは確かめていた。問題に合わせたチューニングが何かできないか、そもそも総当たりのワーシャルフロイド法で可能なチューニングがあるのだろうか、と考えていたが思い付かない。コードを眺めてみよう。

1. 一番内側のループで変化しない配列参照をループの外に出せばちょっとは良くなるかも。
2. 一番内側のループで処理をスキップするための判断を加えるのは無駄。
3. 一番内側のループから真ん中のループに外出ししてきた変数を使って処理をスキップすれば最内ループが丸々スキップできておいしい。

という感じの苦肉の策で AC をもらった。E 問題だからこんなものかも(というのはコンテスト中に解いてから言おうね)。

集合 S をビット表記により 0,1,…,2N−1 までの自然数にエンコードしてしまうと、S=0,1,2,… 順にループするだけでトポロジカル順序が守られることなどから、実装が簡潔になります。

自分はこの条件を知らないままなんとなくでうまくいく方法を真似しているだけだなあ。

頂点0からスタートするが、訪問済み頂点集合を考える上で頂点0は最初は含めない

こうすることで「訪問済み頂点集合が全集合になった」時「頂点0に戻ってきた」ことを意味するので、戻り道も含めた問題条件に適用できる

これを考慮するなら自分の AC 提出の 10 行目を NP[0][0] = 0 としなければいけないが、実際にそうしなければいけないだろうか。

NP = Array.new(N){ [Float::INFINITY]*2**N }
NP[0][1] = 0

NP[現在地][経由地] = 移動コスト であり、ゴールは NP[都市１][全都市網羅]。ゴールに初期値以外のコストが設定されているとき、それは全都市を経由してから現在は都市１にいる(またそれにかかるコストがいくらか)ということなので、スタートが NP[都市１][都市１] でも NP[都市１][無] でも関係はないかな。

 提出 #17524559 (AC / 1283 ms)

「スタートが NP[都市１][都市１] でも NP[都市１][無] でも関係はない」ということと関係するのだけど、konayuki さんの提出 #17520925 のこの行……

dp[0][1] = 0
for i in 0..goal
  next if i&1 == 0

17 行目は、自分も全く同じように書いたが、スタート地点の初期化。だけど 19 行目のスキップが目新しい。これは経由地点にスタート地点を含まない場合を除外している。当然これに関わるコストを記録した配列の中身は初期値の Infinity で間違いない。

2^N が 2^{N-1} になるだけでループの回数が半分になるのだからこれはとてもうまい。これもひとつのケチビットだな、ということで、メモ配列からもループの繰り返しからも最初から除外しておけば条件分岐すら不要。

ところで、コストを記録するメモは Array[N][1<<N(-1)] よりも Array[1<<N(-1)][N] としている提出がほとんどだった(例外が自分と konayuki さん)。これは「一番内側のループで変化しない配列参照をループの外に出せばちょっとは良くなるかも」の発展として理解できる。行列計算ともたぶん関係する。多重ループの最内ループが多次元配列の何次元目をイテレートするかは性能と無関係ではない。スクリプトにおいても、途中までの配列参照をローカル変数にメモすることでコスト削減が期待できる。

この２点で 1933 ms が 1283 ms になった。

 左にマイナス１ビットシフトは右に１ビットシフト

負数を習う中学１年生らしい言い換え。

さっきの提出で意図せず -1 ビットシフトしている部分があったが、エラーにもならず正しい答えが出ていた。Ruby に助けられた怪我の功名。この仕様は特に明記されていないし知らなかった。

これまでは 1<<N が取り得る値の最小が１だとばかり思っていたから、０にしたい場合を例外扱いしていた。活用したい仕様。

 提出 #17557645 (AC / 852 ms)

「同じ都市を２度以上訪れて得することはない」、という考察を何か所かで読んだので、next if 0 < v[f-1] という条件を真ん中のループに足してみたら、1283 ms が 852 ms になった。わーお。

ちなみに Integer#[] である桁のビット(0,1)が得られるのだけど、最下位(右端)のビットが０番目になっている。負の添字は必ず０が返るっぽいので、今度は意図してこの仕様を利用した。

 提出 #17558093 (AC / 769 ms)

「負の添字は必ず０が返るっぽいので、今度は意図してこの仕様を利用した」とか書いたけど、０は望ましい結果ではなく、結果的にスタート地点である都市１だけは何度も発着を繰り返していた。

真ん中のループの繰り返しから都市１の分を引いて N 回を N-1 回にしたら、852 ms が 769 ms になった。もうこれ以上は無理でしょ。

Integer#times の方が Range#each より速いようだったので Integer#times を使っている。そのせいで f(rom) と t(o) で都市番号への対応付けがずれているのが罠。

 提出 #17563476 (AC / 627 ms)

経由地を記録したビットフラグ(v)から０のビットを抽出して真ん中のループと一番内側のループに利用したら、769 ms が 627 ms になった。さすがにもうこれ以上はないでしょ。

 提出 #17563659 (AC / 583 ms)

TLE を初めての AC に変えた立役者である next if NP[0][-1] <= c0 が、変形を受けながらずっと残っていたのだけど、いつの間にか用無しになっていたことがわかったので消したら、627 ms が 583 ms になった。沼っぽくなってきたぞ。

メモ配列を見たら 0 番目の要素が 0 と Infinity に決まっていて無駄なので、長さ N の配列が N-1 にできるけど、ちょっとした省メモリにはなっても速くはならない感じ。

 提出 #17575125 (AC / 217 Byte / 1731 ms)

沼といえばゴルフ。217 バイト。

(N,),*Z=$<.map{_1.split.map &:to_i}
V,=C=Z.map{|a,b,c|Z.map{(_1-a).abs+(_2-b).abs+[0,_3-c].max}}
V+=[9e9]*N*M=1<<N-1
M.times{|v|N.times{|f|g=N.*v|1<<f-1;w=V[v*N+f];N.times{|t|V[g+t]=[V[g+t],w+C[f][t]].min}}}
p V[-N-N]

TLE になったら元も子もないので削れない一時変数と -1 がある。そういうのは Crystal (Ruby に似たコンパイル型言語)で投稿するという手があるらしいが知らないので。

 提出 #17667397 (AC / 207 Byte / 1963 ms)

うん、沼だ。207 バイト。

配列の初期化を省いて || で初期値を補うようにしたら 10 文字短くなって 200 ms ほど遅くなった。

(N,),*Z=$<.map{_1.split.map &:to_i}
V,=C=Z.map{|a,b,c|Z.map{(_1-a).abs+(_2-b).abs+[0,_3-c].max}}
(1<<N-1).times{|v|N.times{|f|g=N.*v|1<<f-1;w=V[v*N+f];N.times{|t|V[g+t]=[V[g+t]||9e9,w+C[f][t]].min}}}
p V[-N]

整形すれば普通に読めるあたり変態度が足りないと思うんだよなあ。発想に飛躍がない。

 研究>提出 #17680607 (yamagiri さん / 556 ms)

• ループの回数が何パーセントか少ない。内側のループが 0(potentially 1) to 0 でなく 0 to 1 だから。そうしようとすると初期化にフラグが絡んできて手間がかかると思ったけど、実はそうでもなかった>提出 #17685423。手間を省いた代償として数万回のループの初回にしか関係しない || が二重ループの内にあるけど、大差ないみたい。

• とりあえず大きな数としての初期値に Float::INFINITY を使うと、10**9 のような整数型を使うより比較にコストがかかる。

  余計なコストがかかるはかかるんだけど、今の段階に至っては初期値は nil で構わないのだった。比較されない。

• こんな感じの配列を事前定義すると手元ではちょっと速いようだけど、スマートじゃないので却下。

  ０１ = [[[0],[]],[[],[0]]]
  (1...N1).each{|n|
  	０１.concat ０１.map{ next (_1<<n)[0,_1.size-1],_2+[n] }
  }

  (1<<N1).times{|v|
  	c = CV[v]
  	０,１ = ０１[v]
  	０.each{|f|
  		f2 = C[f]
  		CV[v|1<<f][f] = １.map{|t| f2[t]+c[t] }.min||s2[f]
  	}
  }

最終更新: 2020-10-16T23:56+0900

♪ [WR250R] バイク走行動画 (合計 6 分)

１号線を走るくらいならこういう道を選ぶよね。このルートに仮免許練習中の教習車を送り込むコースが存在している模様(よく見かける)。そんな教習うらやましいにも程がある。

音・サイズ(100 MiB 超)注意。

最終更新: 2020-10-18T20:31+0900

♪ [AtCoder] HHKB プログラミングコンテスト 2020／E 問題 Lamps

D 問題をしばらく考えて、

完全に内 = lambda{|n,a|
	next (1+(n-a).abs).pow(2,M)
}
はみだし = lambda{|n,a,y|
	n,a = a,n if n < a
	y = a-1 if a-1 < y
	next [完全に内[n+y,a]-完全に内[n,a],0].max
}

みたいな関数を書いたりしていたんだけど、ここから詰め切れる見通しが立たなかったので E 問題に手を出した。

 提出 #17317545 (TLE)

方針はすぐに決まった。逆に考える。照明の置き方が 2^k 通りを網羅しているのだから、照明の置き方を考える必要がない。あるマスを照らす照明の置き場所が何か所あるかを数えることにする。

もちろんグリッドを１マスずつ移動しながら４方向に探索を進めるようでは TLE を免れない。N の上限が 2000 の時に 2N^3 マスの走査は認められない。

lambda P が４方向の探索を省力化する工夫なんだけど、２回の P の合計が後半の N^2 のループと同じくらいの重さであり、N^2 の上限が 400 万だということはループの中身がごく簡単な処理でなければ Ruby は１秒２秒で終了しないので、N^2 ×２の結果は TLE だった。

 Ruby によるすべての提出

TLE の山を見てわかる通り、Ruby にとってこれは実装をがんばる問題らしい。そうとわかれば考えるより先に手を動かすのみ。

 後日の提出 #17357029 (AC / 1433 ms)

構造はほとんど同じ。lambda P の代わりの lambda F が４、５倍速いおかげで AC になった模様。スクリプト言語は自分で書いたスクリプトとランタイムライブラリの処理速度に雲泥の差があるので、プリミティブな処理を自分で書かずにいかに丸投げするかが肝要。

それと、２の冪乗を含む掛け算は展開すると一部がループの中身に関わらない定数になって外に出せる。２のＫ乗を１回だけ計算しておけば、ループの中の２の累乗計算は１回だけでいい。もちろんその計算結果は２回目３回目に備えてメモしている。

最終更新: 2020-10-17T17:20+0900

♪ [AtCoder] AtCoder Beginner Contest 174／F 問題 Range Set Query

C 問題が解けなくて大爆死した回の ABC。「時間内に B 問題までしか解けなかったので今日の日記は C 問題」。F 問題が解けたら D と E も解けたつもりでいいんじゃないかな？

 提出 #17399477 (TLE×4 / 427 Byte)

どういうデータであればクエリに答えが出せるか、どういうデータ構造であればひとつひとつのクエリに妥当な時間で答えが出せるか、とっても考えた。

1. ユニークな色数の累積和で……
2. だめだめ、始点の位置によってユニークさが変わる。
3. じゃあ色ごとに直前の出現位置を記録して……
4. でもクエリごとに区間をスキャンして区間内でユニークな色を数えるわけにはいかない。
5. 始点か終点を固定してよければ定数時間で答えるためのデータを用意できる。
6. でも始点も終点もクエリごとに移動する。
7. 始点用のデータと終点用のデータの２本を組み合わせて答えを出せないか。
8. 無理。
9. う～ん。
10. 色をスキャンしながら現在のユニークな色数とその色がユニークである始まりの点を記録するとする。クエリ区間の入りと出を色のスキャンと同時並行で処理して……

「LOC (last occurrence of colors)」とか「QIR (q in range)」といった名前をとっかかりに部分的に形を作っていった結果、移動する終点に合わせて始点用のデータを(事前に用意するのではなく)継続的に発展させていくやり方に落ち着いていた。

色の列を空間としてではなく時間として処理すること*が振り返ってみての転換点。意識してではなく手探りで進めるなかでの変化だったけど。

でも TLE。ソート列やハッシュ表といった素朴な構造ではダメみたいだ。

 提出 #17400113 (TLE×1 / 622 Byte)

BIT を持ち出しても TLE とは恐れ入りました。ソースコードが長くなるのが仰々しくて嫌だとか言っていられない。

 Ruby によるすべての提出

TLE の山と AC 提出の実行時間を見るに、Ruby にとってこれは実装をがんばる問題らしい。そうとわかれば(略)。

 提出 #17407692 (AC / 600 Byte / 1731 ms)

配列と BIT に余分な要素を付け加えて単項マイナス演算子と引き算の数を減らしたり、配列の初期値を工夫してループの中の if を取り除いたり、1-origin な入力値を 0-origin に加工するのをやめたり、i-=i&-i を i&=i-1 に代えて演算子を１つ減らしたり、といった泥臭い改善の成果で AC。

こういう脳筋的努力は考察不足の可能性がちらつくと身が入らないのだけど、その心配はなさそうなので心置きなく。

 提出 #15667239 (climpet さん / AC / 1696 ms)

これが Ruby で一番速い(しかも Ruby で一番早い AC でもある)。速さの秘密はよくわからない。クラスやメソッドなしですべてが一体だからだろうか。 初めて見たのだけど BIT の初期化をするこの行……

b = (0..n).map{|x|x&-x}

BIT 実装のキーでもある LSB を蓄えるこれは公差１の等差数列を初期数列にしようとすると現れる。蟻本の図を見ていたのだけど、LSB は内部配列の要素が分担する重みに対応している。倍率(公差)は好きに決めたらいいだろう。

BIT の初期化が多少複雑になっても実行時間でペイするのは変数 u の存在がある。自分の提出で答えを設定する式は Ans[q] = r-l+1-Dup[N-l] (変数 Dup が BIT) だけど、BIT の初期値の工夫により -l が消せても +1 も N-l も残る。そもそも BIT を使用する向きが違っているのだ。BIT から２回値を参照するのを嫌って自分は向きを決めたけど(※BIT の操作が一番のホットスポット)、変数 u があれば参照が１回節約できる。参照が同じ１回なら他の部分の有利が生きるということなのだろう。

最終更新: 2021-01-19T03:44+0900

♪ [Ruby] 平衡二分探索木

 前置き

最近こういう記事を読んだ(20200912p01)。「【Python】平衡二分木が必要な時に代わりに何とかするテク【競プロ】 - Qiita」

その少し前に雰囲気で書こうとしたけど、バランスの取り方に対する理解が雑で完成しなかった(20200604p01.04)。

Ruby の標準添付ライブラリにある SortedSet は内部構造がハッシュテーブルでありキーの順序付けが利用できない。ありていに言えばキーの二分探索をしたいができない。「RBTree ライブラリ (https://rubygems.org/gems/rbtree) が利用可能である場合、内部記憶としてハッシュの代わりに RBTree を使用します 」ということが書いてあるけど、RBTree が利用可能だったことがない。

 再挑戦した。sset.rb (3.8 KiB)

• SortedSet と食い違いが見つかるまで無限ループさせてみたけど、限られた範囲のキーと限られた時間では止まらなくなった(こういうときはテストの失敗を疑う。だから最初に失敗するテストを書いて、それを満足させるように実装を埋める)。

• 性能はまったく期待できない。まったく。

  注意すれば省メモリにはなるかもしれないけど、出し入れのたびに配列の全長のおよそ半分を右へ左へ動かしていたのでは、他に何も期待できない。

  注意を要するのは rotate_l/rotate_r の実装。このとき(20200905p01.07)のように、不必要に膨大なメモリ要求が実行速度まで低下させかねない。

  すばらしき(20200912p01.03) Array#fill メソッドにならって、Array#rotate も第２引数以降を使って対象範囲を受け付けたらいい。

• 内部構造は「社長から始めて決まったやり方で社員を一列に並べていったら、ある社員とその部下と部下の部下以下末端までを一定の連続する範囲で表せるのではないかと考えた。なんのことはないそれって深さ優先探索と同じ順番だったのだけど」(20200607p01.02)と書いたときのものと同じ。

  その後の検索で「最小共通祖先 [いかたこのたこつぼ]」というページを見つけて、「LCA」「オイラーツアー」という用語を仕入れている。そんな感じの構造。

  ちょっと待て、このドメイン名は……。20200905p01.03 で参照した AtCoder の ikatakos さんと同じでは？

• 苦労の 70 % くらいは sink と push の２メソッドを見出すところにあった気がする。実装することではなくシグニチャを発見するまでのところに。でも、どういう操作が必要か、どういう操作であれば十分か、実装を始めてデバッグをする過程でしか見つけられないジレンマ。

  以前にも似たようなことを書いている。「メソッド名を決めるまでで 9割が終わってる。」 そのときはその後の検索で「最小全域木」「プリム法」「クラスカル法」という用語を仕入れてクラスカル法で再実装しているが、今回はどうか。AVL木とか赤黒木とか知らないよ？>「平衡二分探索木 - Wikipedia」

• key の順序(SSet#index(key))と内部配列の添字の変換に何か魔法がないものか。ありそうではないか。
  • 最大値と最小値を蓄えている内部配列における位置は計算で求まることがわかった。

  • ソート列における順序と内部配列における添字という、２つの数字を元にして each メソッドが簡略化できそうな気がする。したい。

    つまり、現在の向き(行きか帰りか)と次の添字がわかるならスタックがいらなくなる。開始点(最小値の添字)はもうわかっている。

あっ、これ二分探索のためにあらかじめ並べ替えたソート済み配列だ(いま気がついた)。Array#bsearch_index と Array#insert で済むものをよくも難しく書き直したものだ。

メモリブロックの移動を減らすためにギチギチに詰め込まないでルーズに管理しようとしたら、固定長の大きさを持っていて最大値と最小値で特徴付けられる疎な配列(リスト)の入れ子構造に行き当たって、ピボットはいらないな、そうするとこれ木じゃないな、ただの(入れ子になった)ソート列になっちゃったな、と。じゃあ原点に戻ってあれも(並べ方が素直じゃないだけの)ソート列だな、と気がついた次第。

持っていることも忘れていた『[単行本] K. メールホルン, P. サンダース【アルゴリズムとデータ構造―基礎のツールボックス】 シュプリンガー・ジャパン株式会社』をぱらぱらめくってると、(a,b)-木という構造があって、これは木の各ノードが最長で長さ b の子ノード列を持つらしくて、つまりは入れ子になったソート列なんだけど……。

入れ子になったソート済み配列もやっぱり木？

最終更新: 2020-10-14T18:33+0900

♪ [AtCoder] ACL Contest 1／A 問題 Reachable Towns

ACL は ARC と AGC の中間あたりの位置づけだそうな。この A 問題は 300 点問題。１問目のこれしか解けそうにない。

 最初の提出 #16962327 (TLE)

移動可能な範囲が第Ⅰ象限と第Ⅲ象限に限られるが、移動先の点からさらに移動先を選ぶことができる。双方向に移動可能だし、X と Y の比率を変えながらジグザグに Y=-X 方向に移動することもできる。ともあれこの感じ(「友達の友達は友達」)は UnionFind だと思った。

問題は Union する点の選び方で、見境なく Union したら TLE になった。

見境なくとは言っても、相互に移動可能なら片方向だけを取り扱えば足りるわけで、X 座標の昇順に処理することで X 座標の大きい方から小さい方だけを見るようにしている。X 座標のソートに関してもこの問題で NlogN の時間をかけるのはもったいなくて、線形時間でソート列が手に入る。

 ３番目の提出 #16962544 (AC / 565 Byte / 559 ms)

Union した中で一番条件のいいものだけ代表として残すようにしたら AC。

 Python で一番速い提出 #16928237 (maspy さん / 363 ms)

よくわからないが UnionFind ではない。キーは12行目の if x + min_y == N+1: だと思う。UnionFind で形作られるグループが持つ幾何学的性質が何かあるのだろうか。

右上がりの対角線上に並ぶ場合と右下がりの対角線上に並ぶ場合を対極として、その中間の状態がうまく考えられない。

X 座標と Y 座標がともに 1..N の順列だということから導かれる論理的必然性を何か見落としてると思う。

検索してたら答えらしきものが見えちゃったんだよな、maspy さんのページは避けてたんだけど他の所で。

頂点をソートして x 座標が小さい順に見ます。

頂点 i と頂点 i+1 について、「y1, …, yi が (N,…, N−i+1) の順列」であるときのみ非連結であり、そうでないとき必ず連結になることがわかります（あとで証明かなんかできたらいいな、、）

「わかります」(わかりません)

 提出 #17013139 (AC / 1055 Byte / 326 ms)

maspy さんの提出に沿って*理解したことをひとつひとつコメントにしながら書いた。完全にそのままではなく、「# ymin の最初期化が必要？」とコメントしたように、ループ中の代入をひとつ省略した。(あ、タイポ。最初期化→再初期化)

しかし、ガイドなしの独力でこの道筋が見つけられるとは思わん。

 「UnionFind で形作られるグループが持つ幾何学的性質」

けんちょん(敬称略)のページにわかりやすい図があった。へー、そうだったのか(まだ見えていなかった)。

「ACL Contest 1 A - Reachable Towns (300 点) - けんちょんの競プロ精進記録」

でも図を見てみたらある意味わかって当然の図ではあった(それがわからなかった)。つまり、x + y = N+1 という X と Y の関係式を見て幾何学的性質について考えたのだし、であれば、その性質は y = -x + N+1 という直線に関わるものでしかありえない。答えを目の前にしながら「わからんなあ」と悩むふりをしていたのだった。下手の考え……。