/ 最近 .rdf 追記 設定 本棚

脳log[2020-10-19~]



2020年10月19日 (月) どうしてあの人はいつもいつでも人の動線を遮るような邪魔な場所に物を置くのかという疑問に対する完璧な答え。人が通らない所の床はすでに物で覆われている。


2020年10月18日 (日)

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

[AtCoder] AtCoder Beginner Contest 180/D,E

 D 問題 Takahashi Unevolved

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

 提出 #17475334 (WA)
 提出 #17517315 (AC)

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

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

対数を使って強さの増加量が逆転する境目を求めたのだけど、それは 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 になるのがわかっていたが、ビギナーはワーシャルフロイド法が書けただけで満足なのです。これ以上は解らないのです。

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

 提出 #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[都市1][全都市網羅]。ゴールに初期値以外のコストが設定されているとき、それは全都市を経由してから現在は都市1にいる(またそれにかかるコストがいくらか)ということなので、スタートが NP[都市1][都市1] でも NP[都市1][無] でも関係はないかな。

 提出 #17524559 (AC / 1283 ms)

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

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

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

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

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

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

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

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

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

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

 提出 #17557645 (AC / 852 ms)

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

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

 提出 #17558093 (AC / 769 ms)

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

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

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

 提出 #17563476 (AC / 627 ms)

経由地を記録したビットフラグ(v)から0のビットを抽出して真ん中のループと一番内側のループに利用したら、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 で構わないのだった。比較されない。

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

    01 = [[[0],[]],[[],[0]]]
    (1...N1).each{|n|
    	01.concat 01.map{ next (_1<<n)[0,_1.size-1],_2+[n] }
    }
    (1<<N1).times{|v|
    	c = CV[v]
    	0,1 = 01[v]
    	0.each{|f|
    		f2 = C[f]
    		CV[v|1<<f][f] = 1.map{|t| f2[t]+c[t] }.min||s2[f]
    	}
    }

2020年10月17日 (土)

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

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

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

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

116 MiB / 3 分

127 MiB / 3 分


2020年10月16日 (金) Twitter で LED シーリングライトの焦げ(?)に関する話題を読んでいたら、「さすが業物様」とか「業物さんの影響力」とかのやりとりが目に入って、どこの2人目のギョーブツたんかと思ったらアイコンが電柱から半身でそのものだった。なつかし。■中の人が同じかまでは知りようがないけど、偶然の名前かぶりではないということへの感想>なつかし。


2020年10月15日 (木)

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

[AtCoder] HHKB プログラミングコンテスト 2020E 問題 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 通りを網羅しているのだから、照明の置き方を考える必要がない。あるマスを照らす照明の置き場所が何か所あるかを数えることにする。

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

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

 Ruby によるすべての提出

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

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

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

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

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

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

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

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

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

  1. ユニークな色数の累積和で……
  2. だめだめ、始点の位置によってユニークさが変わる。
  3. じゃあ色ごとに直前の出現位置を記録して……
  4. でもクエリごとに区間をスキャンして区間内でユニークな色を数えるわけにはいかない。
  5. 始点か終点を固定してよければ定数時間で答えるためのデータを用意できる。
  6. でも始点も終点もクエリごとに移動する。
  7. 始点用のデータと終点用のデータの2本を組み合わせて答えを出せないか。
  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&-ii&=i-1 に代えて演算子を1つ減らしたり、といった泥臭い改善の成果で AC。

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

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

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

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

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

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

* この「空間」と「時間」はユニバーサルな表現ではなかったかもしれない。三次元に囚われた話者の感覚に根差した主観的な意味が込められていて、理解する前提条件になっていると思う。


2020年10月12日 (月) [AtCoder] Twitter での企業コンの話題。自分も最初は企業コンは対象外だと思ってスルーしていた。■知らなかったこと1。企業コンに ABC 級と ARC 級があること。社長さんのツイッターで知りましたよ。■知らなかったこと2。ARC と企業コン(の難しい方)が別物だということ。最近 ARC 開催の土壌が整ったとかで立て続けに開かれたけど、自分が AtCoder に参加して1年以上も ARC が途絶えていたから、ARC は終了した名前で、企業コン(の難しい方)として存続しているのだと理解していた。ABC 級の企業コンがあることも知らなかったし。■知らなかったこと3。問題の難しさを A~F ではなく配点で予測すること。配点が(見積もりとはいえ)絶対尺度だということ。AtCoder をはじめたての頃は恐ろしいことに、AGC の A 問題と ABC の A 問題を区別する基準を持っていなかった。「A 問題よりは難しい B 問題」とか「たかだか B 問題に一日散々苦しんでおいて」とかの感想がそれを反映している。700点問題と500点問題なんだよなあ……(最近は400点問題も解けない)。


2020年10月07日 (水) [AtCoder]「【お知らせ】AtCoderの問題文が表示されない不具合が報告されておりますが、ブラウザのバージョンを最新のものにアップデートすることで、正常に表示されるかと思います。 なお、Internet Explorerはサポート対象外となっております。ご了承ください。」■うん、見えない。atcoder.jp と cloudflare.com のスクリプトだけを許可してたけど、他の、google-analytics.com 以外のスクリプトを許可しても見えない。インストールできる最新版が Firefox ESR 52.9.0 なんだけど、これでは見えない。CSS を切ったら見えたけど、数式が読みにくくなる。■今の段階でエラーになるスクリプトは次の1か所だけで、ページ埋め込みスクリプトの <script>$(function(){$('var').each(function(){var html=$(this).html().replaceAll('<sub>','_{').replaceAll('</sub>','}');$(this).html('\\('+html+'\\)');});});</script> が「replaceAll is not a function.」というエラーになっている。これ1か所だけに対応するコードは String.prototype.replaceAll = function(s,r){ return this.split(s).join(r); }; とか、グローバルフラグを付けた正規表現パターンを第1引数にして String.prototype.replace を replaceAll の代わりに呼び出すとか。■atcoder.jp から送られてくるページの埋め込みスクリプトを書き換える方法がわからなかったので、replaceAll 関数を事前にブラウザに定義することにする(userChrome.js)。しょうもないもんに引っかかってるなあと思うけど、おかげで対策が簡単で助かる。今はまだ?■……と思ったら、「@chokudai「さすがにこの対応状況で入れるのは時期尚早でしょ、ってことでちょっと修正コミット入ったっぽい caniuse.com/?search=replac…


2020年10月03日 (土) 平均寿命と平均余命。■社会科か家庭科か忘れたけど、学校で習ったときは結局よく理解できなかった。教科書には平均寿命とは0歳時点での平均余命である、みたいな定義が書いてあるんだけど、そのことの意味が腑に落ちなかった。今でもうっかりするとあやしい。■どういうことか。今年の発表で日本人の平均寿命が86歳(仮)ですよ、みたいなことが言われるとする。60歳の人が、じゃああと26年は生きられそうだなと考えるのは、概ね間違いではないけど、期待に一方的な偏りがある。現在60歳の人は60年生き延びてきた実績を持つ選ばれし者なので、平均して26年以上生きることが期待される。それが60歳の平均余命であり、0歳の平均余命である平均寿命との違い。たぶんね。■しかし、平均寿命の根拠となるデータは過去のデータであって、生まれたばかりの赤ん坊の寿命はこれからの環境に左右される。平均寿命が当てになる根拠って何だろう。大きな変動がない? トレンドを加味した予想(外挿)?■平均寿命は86歳(仮)ですよ、86歳の平均余命は何年ですよ、というのが最も当てになる数字ではなかろうか。ま、こんな素人考えの及ばないところまで保険会社の人は考えていることだろう。儲けに関わるからな。■平均寿命のイメージって、人口を年齢別に分けて、それぞれに平均余命を足して平均したものって感じ。実際どうなんだろう。


2020年09月30日 (水)

最終更新: 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 も第2引数以降を使って対象範囲を受け付けたらいい。

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

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

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

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

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

  • key の順序(SSet#index(key))と内部配列の添字の変換に何か魔法がないものか。ありそうではないか。
    • 最大値と最小値を蓄えている内部配列における位置は計算で求まることがわかった。
    • ソート列における順序と内部配列における添字という、2つの数字を元にして each メソッドが簡略化できそうな気がする。したい。

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

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

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

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

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


2020年09月26日 (土) 小学校で行われるテストに2種類あって、先生が回収して後日採点済みのプリントを返却するものと、自己採点方式でテストを受けた時間の後半に全員が自身の答案を採点するもの。自分ははっきりと自己採点方式の方が好きだった。解答と結果発表が日をまたいでしまうと、テストの内容に再び興味を持つことが難しい。問題と答えのつながりがはっきり見えるという点で算数が好きだったのと根っこは同じ。■AtCoder のようなオンラインジャッジ方式の学習面での利点がどこかで語られていたけど、小学校での経験に照らしてもそうだったなあと思ったのだった。


2020年09月22日 (火)

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

[AtCoder] ACL Contest 1A 問題 Reachable Towns

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

 最初の提出 #16962327 (TLE)

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

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

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

 3番目の提出 #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 という直線に関わるものでしかありえない。答えを目の前にしながら「わからんなあ」と悩むふりをしていたのだった。下手の考え……。

* ~に沿って、というのはある意味嘘。こちらにゴールがある、という指針だけを手にして考えた結果の式が一致することを確かめただけ。結果が同じなのだから考えたことの軌跡をコメントとして残さなければ完全丸コピと見分けがつかない。コメントを書くのは必然だった。


2020年09月20日 (日)

最終更新: 2020-10-10T17:39+0900

[AtCoder] AtCoder Beginner Contest 179/D,E,F

 D 問題 Leaping Tak

コンテスト時間は D 問題で詰まっているうちに終わってしまった。計算過程で余りをとらないと一部の入力で TLE になってしまうのだが、余りがうまく計算できなかった。何を言っているのか自分でもよく解らない。

 提出 #16922727 (AC / 302 Byte / 282 ms / 15976 KB)

一日経ってみれば普通に AC できた。どこに詰まっていたのか解らない。

もうちょっと書く。方針。

  1. スタート地点1に立って移動可能なポイント(S の要素)を眺める。
  2. スタート地点から(1ステップで)それらの地点へ行く方法は1通り。メモする。
  3. 地点1に一番近い移動可能地点A(1とメモしてあるはず)に移動する。
  4. そこから移動可能なポイントを眺める。移動した分だけスライドしたが地点1からの眺めと同じである。
  5. 地点Aに来る方法が1通りなので、地点Aから行ける地点へ行く方法も1通り増える。メモする。
  6. 以下、3、4、5の繰り返し。
  7. さて、地点 N に来る方法は何通りになったでしょうか。

移動可能地点ひとつひとつに対してメモしていては TLE になる>提出 #16879797

S の要素数は N に準ずるが、S を定義する区間の数は幸いにも最大で 10 に制約されている。メモの仕方を工夫して、絶対値ではなく変化量を記録する。どうせ地点を端から端まで処理するつもりなので、変化量をつどつど加算していけば絶対値は得られる。これでループ1回の書き込み量が区間の両端の数(最大で20)まで減る>提出 #16883620。TLE なのは、途中で余りを求めなかったから多倍長整数の桁数に比例した計算量に押し負けた結果。

ここから途中過程で余りをうまく求められなかった(冒頭に戻る)。

 E 問題 Sequence Sum

D 問題で詰まったのでコンテスト中に問題文は読まなかった。色気を出せば解ける D 問題も解けなくなるので。

 提出 #16923150 (AC / 253 Byte / 68 ms / 15728 KB)

すんなり書き下してデバッグの必要もなかった。N の値が膨大だが M の値がそれなりなので、余りの種類もそれなり。となれば A 数列は途中から循環する。

 F 問題 Simplified Reversi

D 問題で詰まったのでコンテスト中に問題文は読まなかった。色気を出せば解ける D 問題も解けなくなるので。

 提出 #16923745 (AC / 518 Byte / 513 ms / 17472 KB)

すんなり書き下してデバッグの必要もなかった。縦軸横軸それぞれにブロックラインが単調に前進していくだけなので、それを BIT に記録した。

@chokudai「F問題とても好きな問題なんだけど、データ構造でいくらでも殴れちゃうのが残念……O(N)で解いてみてね><

BIT は読み書きともに対数時間なので、さっきの提出は O(NlogN) になる。O(N) で解くというチャレンジ課題がまだある!

 提出 #16937624 (AC / 269 Byte / 254 ms / 17392 KB)

N に比例したループの中で長さ N(-1) の配列に書き込むとしても、書き込む要素の総数が 2N 以下にとどまるなら O(N) なんじゃないかな。かな?

ひと工夫しないと配列への書き込み量が N×N になってしまう罠がある。変数 ii を介在させて書き込みタイミングを一拍遅らせたことが書き込み量削減のキモ。これには以前日記で触れた「Scintilla 方式」が参考になった。その要諦は……「メインのデータ構造はギャップバッファ。そこに張る行インデックスの更新コストの問題。更新が必要なインデックスのエリアはある点から始まり必ず末尾で終わる。ある点をひとつ記憶しておくことで更新範囲をある点とある点の差分にすることができる。

 ところで kotatsugame さんが…… 提出 #16893528 (121 Byte / 198 ms)

ゴルフをしながら Ruby の中で最速タイムを記録していたのだった。異次元過ぎてさっぱりわかりません。

 @2020-10-09 提出 #17269548 (AC / 249 Byte / 243 ms / 17464 KB)

お風呂でなんとなし思い付いた。

メインループのイテレーションごとに X 軸と Y 軸が参照軸と更新軸のどちらかの役割を受け持つ。参照軸更新軸それぞれが N-2 要素のメモを持つ。メインループの中で……

  1. 参照軸のメモを参照したい要素まで(必要なら)埋める。
  2. 参照した値でスコアを更新する。
  3. 更新軸のメモを参照した値の範囲まで(必要なら)埋める。

前回の提出では更新軸のメモが更新の対象だったが、今度の提出では更新の一部が参照軸の参照時に分散している。その結果ループの中がストレートになり、値の大小関係によってあっちの値を参照したりこっちの値を参照したりという場合分けが不要になっている。しかし変わらないタイム差(たぶん配列参照のコストが大きい)。

メインループの中に2つの対称的な書き込みループがあるあたりが kotatsugame さんの提出と共通だと思ったけど、あちらでは一回に片方のループしか実行していなかった。たぶん参照軸のメモだけ更新しているのではないか。もはやこの軸の命名が意味不明であるが……。

更新軸が更新軸である所以はそれが「ブロックライン」をメモする軸であり、今後のスコア(何枚の黒石を裏返せるか)に影響するから必要があって書き込むからなんだけど、何枚の黒石を裏返すことができるかを知るために見る参照軸のメモだけが更新の対象でいいなんて、どうして想像できる?

参照軸のメモは「何枚裏返すことができたか」の記録として捉え直すことができるんだろうな、きっと。それだけわかれば十分だということの理解はまだ。

 提出 #17272161 (AC / 205 Byte / 244 ms / 17380 KB)

更新軸の更新部分に当たる1行を削除してみたが AC のまま。たしかに参照軸のメモだけ更新していれば十分みたいだ。

「ある座標より後ろは何枚裏返せたかの記録がまだない」というのが、参照軸のメモから読み取るべきもうひとつの情報であり、これは変数 ii の意味とほぼ同じ。だから十分。


2020年09月18日 (金) あんちべ「SQL、めっちゃ書ける自信があります(ドヤァ」 同僚A「SQLで素数を列挙して欲しいんですが」 同僚B「SQLでマンデルブロ集合を描けたな確か」 あんちべ「SQL、何もわからない…」」■SQLite3 で考えてみた。create table P (N integer primary key); create view NP as with recursive NI(N) as (select * from (values(2) union select N+1 from P order by N+1 desc limit 1) union select NI.N+1 from NI where exists (select * from P where P.N*P.N <= NI.N and NI.N % P.N == 0)) select * from NI order by N desc limit 1; 素数を記録する表 P と、表 P を参照しながら次の素数を返すビュー NP を定義した。このように使う。insert into P select * from NP; 効率は知らない。SQL っぽく無限集合から素数が湧いてくるように定義できれば、limit, offset で自由に素数が取り出せるのだけど……。自然数の無限集合ならできる(with recursive N(N) as (values(1) union all select N+1 from N) select * from N;)。でも素数は?■マンデルブロ集合を描く SQL は想像もつきません。■あっ、SQLite のページにあった!「The following query computes an approximation of the Mandelbrot Set and outputs the result as ASCII-art」 このページからは全体に、「SQL はチューリング完全!」とか言って嬉しくなってしまうような人の気配を感じる。だめだよ野放しにしては(いいぞもっとやれ)。