/ 最近 .rdf 追記 設定 本棚

脳log[2020-06-20~]



2020年06月20日 (土) 進化論にかこつけて憲法改正をあおる自民党の広報マンガが誤っていると突っ込まれている。「唯一生き残ることが出来るのは変化できる者である。」(だから憲法を変えよう)とか言ってるけども、こちらが進化論になぞらえて読み取るメッセージは「勝てば官軍」であるので、なんだ何も間違っていないな(とっとと負けやがれ)。■「二階氏「ダーウィンも喜んでいる」 進化論の誤用問われ:朝日新聞デジタル」 マンガが子供にも失礼な子供だましなのよりも、この聞く耳のなさ、反省のなさが問題だと思うんよな。多様な意見への寛容さをアピールしたそうに見えるけど、そういう話ではない。それがわからないなら愚か者だし、わかってまぜっかえしてるなら不誠実だ。あ、それが平常運転でしたね。■日本心理学会@jpa_psych「日本人間行動進化学会「「ダーウィンの進化論」に関して流布する⾔説についての声明」 hbesj.org hbesj.org/wp/wp-content/… 6:14 - 2020年6月27日


2020年06月15日 (月) [AtCoder] 「【競技プログラミング】青コーダーが灰~茶コーダを緑diffの問題をACに導く Part1【考察過程】 - YouTube」■すごく、すっごくもどかしい。でも自分がもどかしい側に立っていることを知っている。実際、教えている青色の人が一瞬で問題を掴んで解法の見当をつけたところでは問題の理解が完了していなかった。教わっている人がサンプルの答えとなる数列を列挙している時間と図を使って、見ているこちらでも具体的な解法がわかった。実のところ題意を満たす満たさないを問わない部分列の全列挙がそう簡単なタスクではない。開始位置と終了位置の組み合わせで特徴付けられると気がつくまで、本当に網羅できているか不安があった。問題の輪郭と扱っている対象がはっきりしてくるまでに、手の運動と、目への刺激と、時間が必要なのだ。■「累積和」という単語で2つめの解法を新たに知った! 最初に N 要素を順に足してメモして、それは増加列だから二分探索で題意を満たす最小の範囲が確定できる。題意を満たしているかは引き算で。■■■高校3年生ですって。人生2周目でも追いつけないよ!「超高速!多倍長整数の計算手法【前編:大きな数の四則計算を圧倒的な速度で!】 - Qiita」■■■@2020-06-19 今日は蟻本で BIT(Binary Indexed Tree) という構造について読んだ。とりあえず累積和を記録するのに使えることがわかったけど、普通に配列にそれまでの総和を記録していくのと比較した強みがなんなのかがはっきりしなかった。たぶん更新がないなら普通に総和を記録していくのでいいと思う。定数時間で値の取得ができるし(BIT なら対数時間)。BIT を使いたいのは値の更新があるときだろう。普通に配列にある要素までの総和を記録していた場合は、値を更新するのにある要素より後ろのすべての要素が関わってきて線形の時間がかかる。BIT なら値の更新も対数時間で済む。


2020年06月12日 (金) GAFAコーディング面接こんな感じでした - yambe2002’s diary」■「ちなみに「ぼく」はIQ+30くらいの設定です。」というのがよく解らないけど、自分は対面だと IQ にマイナス100補正がかかります(元が100以上あるかは知らない。小学校でそれっぽいのを受けたけど結果は教えてくれなかったよね)。考えながら話せない。会話に脳のリソースを100%持っていかれる(つまり能力が足りていないということだからあわあわする)。なんなら見られているだけで何も考えられなくなる。隣に人が立つだけで小便が引っ込むような。■(ダミー問題だけど)履歴の管理。いきなりだと面食らうだろうなあ。まず問題のコンテキストがわからない。そのあたりはブログ筆者も同じとみえて質疑が参考になる。とりあえず配列で持って、現在位置を示すポインタを増減するかな、ということを自分で考えてから記事を読み直したらさっきより内容がよく掴めた。■計算量の話題。配列だとメモリの再確保で履歴の追加が最悪 O(N) とか、そんなことまで気にするの? 「「まあ、一般的な使い方なら大丈夫だろうけどね。これを解決するにはどうする?」」 えー、聞くの? ブラウザの進む・戻るボタンの履歴なんてタブとともに捨てられるんだから気にする必要なくない? 適当に上限を100にしてリングバッファにしても普通の利用者は上限の存在に気がつかないだろうから、それで。■「ところで、仕様追加をしたいんだけど。古い履歴は自動で捨てるようにしたい」 あっ、これって進む・戻るボタンに留まらない履歴管理の話だった(読み返したから思い出せた)。そうすると複数のウィンドウと複数のタブから報告される訪れたサイトと時刻のペアをどんどん追記していく感じになる。タイムゾーンとか文字コードはいい感じに。進む・戻るボタンの履歴はタブのセッション記録に別途保存しておくだけでいいでしょう。■「報告される」(※自分で書いた)ってなんだ? そんなサーバープロセスは存在しない、こともないか。Firefox は1タブ1プロセスなんてことはない。仮に履歴ファイルの排他が Web ブラウズのレスポンスを低下させるなら、プロセスごとに仮の履歴ファイルを作るようにして、プロセス終了に合わせて統一履歴ファイル(places.sqliteみたいな)にマージするようにするかな。それだとウィンドウごと、タブごとに見られる履歴の内容が最新でなく異なるって? じゃあプロセスの終了を待たずに随時バックグラウンドでマージすればいいじゃない。クラッシュ耐性も上がるよ。■「仮に履歴ファイルの排他が Web ブラウズのレスポンスを低下させるなら」(※自分で書いた)←こんな状況は考えられない。ブラウザの使用者は1人だよね。人間ミューテックス。


2020年06月10日 (水)

最終更新: 2020-06-15T23:25+0900

[AtCoder] 第二回 アルゴリズム実技検定 過去問

 自分のすべての提出

第三回まで過去問をやったけど(20200607p0120200607p02)、やはり順当に解けるのは K 問題まで。L 問題が自分にとってのチャレンジ。そこまでの問題が漏れなく時間内に解ければ上級認定。今回時間をかけてでもこれが解けたのは、今日たまたま読んでいた蟻本で紹介されていたデータ構造を雰囲気で実装してみたことによる。(この日記は今日書いた>20200602p02.03)

 L 問題。清書しようとしたらバグに苦しめられた。

  • 最初の AC 提出 #14164516 (AC / 1293 ms / 93824 KB)
  • 清書した AC 提出 #14183943 (AC / 870 ms / 61964 KB)

ヒープ構造を使って冗長な情報を削ったら同時に保険がなくなって、雰囲気実装のふんわりした理解の穴が露呈してバグに苦しんだ。AC と AC のあいだに 3WA。

二分木におけるLCA

木の構造が定まっているので、bit演算で計算できる。

こんな感じでうまいことできないかずっと考えていたのだけど、バグが取れてみれば、1つか2つのノードを見るだけでは済まないみたいなのでもとから無理だったっぽい。

 せっかく清書したけど

他の人(Ruby では2人いる)の提出を見ていたら不備に気がついた。

B,BL = A.map.with_index.to_a,1<<A.size.bit_length
H = [nil]*(BL-1) + B + [B[-1]]*(BL-B.size)

こんな感じで配列 A のビット長をもとにしてヒープのサイズを決めてるけど、例えば A のサイズが2のべき乗でヒープの最下段にきっちり収まるとき、なぜか倍のサイズを確保してしまってる。

例えば A.size == 8 のとき、ヒープサイズは 8+4+2+1 の 15 で十分だけど、上の BL の定義ではヒープ H のサイズが 31 になる。無駄のない定義は BL=1<<(A.size-1).bit_length。-1 がキモ。

 値の取得を最下段から遡ってやってるけど

これはうまくないみたい。今回は値の更新がなかったけど、更新を遅延させて値の取得に合わせて伝播させるためには、上から下っていかないといけない。

更新を遅延させるとか、考えてもみなかった。

それに最下段の要素に直接アクセスできたのは今回の問題に限った特殊条件ではある。範囲が配列の添字、0から連続する離散値だっていう。

必要になるまで考えないでいいことは考えない方針で。

 図を見てたらまだ理解が不十分で無駄なところがあった。

上に上るにしろ下に下るにしろ、自分が左右どちらの枝にいるかは考える必要がなくて、右ないし左に移動してから隣の階層に移動するだけで次の判断がつく。

右(左)に移動するとは、兄弟もしくは従兄弟ノードに移動するということ。最初に右の枝にいたか左の枝にいたか、そして右に移動したか左に移動したかで関係が違ってくるが、気にする必要がない。そのうえで上の階層に移動するとは、元のノードから見て親か伯叔父ノードに移動するということ。いとこの親ならおじさんである。

具体的なコードは次で。

 まとめ
提出コード長タイムメモリ
とりあえず AC660 Byte1293 ms93824 KB
ちょっときれいに AC740 Byte 870 ms61964 KB
十分に詰めて AC707 Byte 700 ms51032 KB

単純にタイムを縮めるだけなら他に優れた解法がある。これは次にこのデータ構造を使う準備みたいなもの。

 L 問題。Python で速い人の提出 #12961808 (279 ms / 61868 KB)

すっごく読みやすいね。実は答えを保持するスタックに push/pop するだけで答えになるらしい。しかも速い。

自分の最初の提出(TLE)がこれで、#14163100、素朴なやり方では無理なんだと思っていたのだけど、どういう違いが AC(速い) と TLE を分けたのか。

もっともらしいことを想像で書こうとしたのだけどよく解らなくなった。バグで無限ループしてるという方が納得できる。だって K の大小や D の大小に応じて、最小値を求める区間や回数はしっかり反比例してる。たしかに重たいケースで TLE になってるみたいだけど、他のケースの10倍20倍も時間がかかるというのは解せない。


D が小さくて A 数列がほぼ昇順に並んでるときに、N の上限の20万要素ちかい範囲から何度も最小値を選ばされる地獄を見ることがあるのか。いやあ、そんな意地悪な入力を与える人はいないと信じるよ。


2020年06月09日 (火) 今日「高襟(ハイカラ / high collar)」という言葉と当て字を仕入れた。はいからさんってそういう……(知らなかった)。


2020年06月07日 (日) PAST とエロゲは同じ値段。AtCoder 緑色は初級と中級に分かれるらしいが()、第一回なら中級の目があった>自分の提出。わざわざ初級認定をもらいたくはないが、中級なら。無料だった第三回は昨日終わっている。第一報があったときに確認したサンプル問題は明らかに難しくて、「取るべき問題をすべて取って、さらに2、3問のまぐれ当たりを上乗せしてやっと中級」という感触だったんだ。それで見逃した。

最終更新: 2020-06-09T19:05+0900

[AtCoder] 第一回 アルゴリズム実技検定 過去問K 問題 巨大企業

答えを出すだけなら簡単。社長を頂点とするピラミッドを遡るあいだに上司として出くわすかどうか確認するだけ。こういう問題は好き。逆にいつまでも数が合わない数え上げ問題は嫌い>禁止された数字への自分の提出。そもそもサンプルへの答えがいつまでも一致しないから、提出に至らないスクリプトが山ほど隠れている。

簡単ならどこが問題か。

 最初の提出 #14088806 (RE と TLE)

N の上限が15万だから、そして組織が非効率の極み直列15万階層だったなら、1つのクエリに答えるために15万マイナス1回階層を上らなければいけない。クエリは最大10万個ある。

そこは一応読めていたので、社員ごとに社長から何階層下にいるかという情報をメモしておいて、社員間の階層の隔たりと同じ回数だけ上司をたどれば答えが出せるようにしていた。でも TLE と RE。最悪の場合はやっぱり15万マイナス1回たどらなければいけないのだから、TLE はまあ当然。

 2番目の提出 #14089327 (RE)

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

それで TLE はすべてなくなった。1度だけ15万マイナス1階層をたどってしまえば、あとはすべてのクエリに定数時間で答えられる。

しかし TLE はどれも RE に変わっていた。最初の提出からかなりの数存在しているこの RE は何だ? RE ってだいたいはヌルポだからよくある配列の範囲外アクセスが原因だろうと、考えるのを後回しにしていた。しかし目を皿のようにして調べてもその可能性はなかった。

 3番目の提出 #14090337 (AC / 394 ms / 22832 KB)

再帰呼び出しをやめてスタック変数を……というと意味が違う。スタック構造を持つ変数をスタックの代わりに使うようにしたら通ったので、呼び出し階層が深すぎたのが RE の原因だった。最悪で15万マイナス1階層は深すぎるだろうなあ(最初から読んでおけ)。

 4番目の提出 #14102282 (AC / 394 ms / 21500 KB)

  • N 回繰り返す前処理のループで if を取り除いた。
  • if を取り除いたことでスタックを社長で初期化するときに検索がいらなくなった。一石二鳥。
  • 変数 T,L,R は一列に並べた組織構造(T)と、そこに張った社員ごとのインデックス(L,R)という役割だったのだけど、実は T は配列である必要がなくカウンタ変数で十分だった。(RDB でもインデックスに情報がすべて載っていて表がいらないケースがあるよね)

しかし実行時間は変わらず。「Ruby によるすべての提出(実行時間昇順)」を参考にすると、

  • 回答の出力を一行ずつではなくまとめた方が速い。(システムコールを減らす、の類だと思う)
  • スタック(変数)に一度に要素を詰め込まない方がたぶん速い。
  • p メソッドが puts メソッドより遅いかもしれない。

ということが言えると思う。他に差がつく要素があるだろうか。

最終更新: 2020-06-26T13:37+0900

[AtCoder] 第三回 アルゴリズム実技検定 過去問

 自分のすべての提出

やはり解けたのは K 問題までだった。ただし第一回と違って途中で1問落としたりはしていない。もうひと踏ん張りで80点を超えて上級だけど、残された問題の予想される難しさと裏腹に考える時間が残ってないんだよなあ(本番じゃないので途中でお風呂に入って本を読んだりしていたけども)。

第一回、第三回に共通する問題の傾向として、数学的応用的な要素が抑えられていて、愚直に効率的なコードが書ければ解けるものが選ばれている印象。よく知らないけど、一般的なお仕事コーディングに寄せていこうとしてるのかな。基礎的な知識とその初歩的な運用に漏れ抜けがないことを確認しようとしてるのかな。(緑色以下のコーダーには保証できることがない、というツイートを見かけたので。このへんとか>https://mobile.twitter.com/chokudai/status/1274756588624965632)

 L 問題 スーパーマーケット

Python で解けることは運営元で確認してるらしいので()、Ruby でも方法はあるはずなんだよなあ。

タイムだけちらっと見た>Ruby でのすべての提出。提出数は4つで、ユニークユーザーは2人。2689 ms < 2726 ms < 2747 ms < 3735 ms。やっぱり方法はある。

TLE のケースはメモリの食い方が特異的に大きい。ざっと 1.5 倍。他のケースを見ると、必ずしもタイムとメモリ消費量のあいだに比例関係があるわけではない。メモリの割に時間がかかるのは M が大きいんだろう。TLE ケースは M も大きいんだろうけど、特に N と K が大きそう。K が大きくても配列の shift はポインタのインクリメントで済むようなので(Ruby-1.9の array.c で確認)、あまり影響がない。delete_at(1) を [1]=[0] and shift に置き換えたら一部速くなったから、やっぱり shift は問題ない(提出 #14129916提出 #14130610)。N が大きいと……、M 回のループで4回ずつ行う二分探索の時間に影響する。N は棚の数だから商品数(メモリ)と商品の検索(時間)の両方に響く。問題が「手前から ai 番目までにある商品を見た後、見た商品のうち最も消費期限の値が大きいものを選んで棚から取って購入します」だから、棚を選ぶ検索は避けられない。方法があるとしたら、予めうまいことソートしてしまってループの中では検索しないか、4回を2回に減らすか……。

 M 問題 行商計画問題

 提出 #14141040 (Ruby / TLE)

半分以上がTLE。ACも17個あるからやり方は間違ってないと思う。しかし PAST の問題が考察よりも実装重視の傾向を持っている以上、TLEに甘んじるわけにはいかない。でも無理ぽ。

 提出 #14144878 (C++ / WA)

TLE がすべて WA か AC になりました。C++ のちから。TLE の陰に WA が隠れていたということで、やり方が間違っていた。

 提出 #14145227 (C++ / AC / 1695 ms / 74616 KB)

Visited フラグを立てるタイミングを誤っていたのと、訪れなければいけない街と街のあいだの移動コストを計算するときに、訪れなければいけない別の街を通ってしまう場合の考慮が抜けていた。

この問題を Ruby で、試験時間内に解けるなんてことがある? ちなみに現在 Ruby で AC 提出はない>Ruby によるすべての提出

ところで、1695 ms は C++ 最遅だった。C++ を使うなら2桁msで解けるらしい。

 問題名で検索した。

さっき「訪れなければいけない街と街のあいだの移動コストを計算するときに、訪れなければいけない別の街を通ってしまう場合の考慮が抜けていた」と書いた。その対策として、関心のない街を迂回するルートを2街間の最短経路として採用するようにした(たぶんルートなしにした方が良かった)。もし他の街を中継するルートの方が結果的に低コストなら、そのルートは2本以上の2街間最短ルートの組み合わせとして現れてくるので。

でもこのステップで求めるものを、2街間の移動コストに加えてその際に通過する街と定義したなら、もっと速くゴールにたどり着けていたかもしれない。

解答は2パートに分かれているが、どうやら後半は幅優先探索ではなく DP でやるものらしい。もちろんその方が最遅より速くなるだろう。

でもまだ……。一度通過した街に戻るのにも移動コストがかかるから、状態や遷移には現在位置が関わってくる。それをベルトコンベヤ式に取り扱って答えにたどり着けるイメージが湧かない。二次元の遷移が解らない。

 色と認定の関係

https://mobile.twitter.com/atcoder/status/1273915562989502465

 現在 M 問題で唯一 AC を獲得している Ruby による提出 #14152776

気がついたこと

  • (たぶんルートなしにした方が良かった)。もし他の街を中継するルートの方が結果的に低コストなら、そのルートは2本以上の2街間最短ルートの組み合わせとして現れてくるので。」と書いたが、あれは嘘だった。
  • 注目している K 地点間の移動コストは K*(K-1)/2 通りを調べるのではなく、K 通りを調べるのが良さそう。

    終点を K 地点に限って試行回数を増やすより、終点を N 地点から限らず試行回数を K 回に留めるということ。

  • 後半はワーシャル-フロイド法に見える3重ループ。

    ただし街と街を結ぶ中継地点(一番外側のループ)は街ではなく経由地のリスト。


2020年06月06日 (土) どこへともなく。GitHub を使ってるなら blame の画面で行番号のすぐ左にアイコンがあって、そのラベルが「View blame prior to this change」。cosmetic なコミットを無視して blame を遡りたいのは、残念ながらあるあるなので……。■blame はいかにもコストがかかりそうな操作だから()、一度開いた画面はあまり閉じたくないかな。blame からコミットを確認するときは新タブで開く。インクルードガードやコピーライトコメントみたいに初版から不変の行が一行でもあると、ログを完全にたどらないといけない雰囲気。


2020年06月05日 (金) タイトルだけ見てスルーしてたけど大間違い。感服しちゃうよ。「【検証】クイズ王は、大喜利の回答からお題を導き出せるのか? | オモコロ」■クイズ王は知識を当然の前提としてその先にいる。知らなかった。コードゴルフの醍醐味を伝えたこの文に通じる。「基本的なテクニックを抑えた上での膨大な時間を投下して行なう 論理的思考や発想の転換の勝負


2020年06月04日 (木)

最終更新: 2020-06-05T20:36+0900

Ruby でやってみた(何を?)。

# @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
  1. i を固定してその右で j を動かす。
  2. rating[i] < rating[j] なら up2[j](= rating[j] が左にあるいくつの rating より大きいか)に、rating[i] の分をカウントする。
  3. その際に up2[i] も参照する。up2[i] は rating[i] が左にあるいくつの rating より大きいかを表しているから、rating[i] より大きい rating[j] はその数と同じだけ、左にある2つの rating より大きい(= i と j ともうひとつで3人組のチームが作れる)。
  4. (備考) up2 はインデックス i までなら完成している。

ヒントだと思っていたものはフォーラムの書き込みのひとつだった。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^2)?

O(NlogN) かと思っていたが配列への挿入が O(N) だから O(N^2) になりそう。やってることが挿入ソートと同じだからそうなんだろう。二分探索のためのランダムアクセスと線形よりましな時間での挿入が両立しない。

平衡二分木があれば O(NlogN) が達成できるんだろうか。実は名前しか知らないんだけど。木なら対数時間で適切な位置に挿入できそうだし、平衡を維持するためには左右配下のノード数を知っていなければいけないはずで、そうすると木をたどるついでに左の枝をカウントしていけば木の中での順序が知れる。たぶん。

 二分探索木

名前だけを頼りに insert と each と rebalance メソッドだけ持つ木を作ってみたけど、それを利用して元のスクリプトと同じ答えが出るのは確かめたけど、平衡を保つのが難しいということがわかった。

これまで持っていた雑なイメージでは根っことその左右の子供の間でローテーションするだけでバランスが取れるような気がしていたのだけど、全然そんなことはなかった。芋づる式に全域に渡って枝を付け替えなければいけない雰囲気。

しかも Ruby の組み込み配列を使うのよりくっそ遅い。何十倍も遅い。実装がダメで平衡が保てていないのを差し引いても時間がかかりすぎ。N を大きくしても勝ち目がない。

Count Number of Teams.rb


2020年06月03日 (水) 全口座にマイナンバー登録「容認できず」共産 小池書記局長 | NHKニュース」■別に共産党がどうのではなく、マイナンバーと口座の紐付けについて。国の管理が強まることは全く賛成できないんだけど、一方で、税金の支払いにコンビニバーコードが利用できなかった以前に、月末近くに送りつけられた振り込み用紙でもって、月内に金融機関で支払いを済ませろと余裕のない要求を押し付けられることにうんざりしていた。■俺は銀行と役所には頼まれたって行きたくない。今でこそ銀行も変わってきていて、フロアにコンシェルジュのような役回りの人が配置されていたりするけど、基本的に俺は彼らの客ではなく、不愉快な思いをすることが常だから嫌いなのだ。■放置すると督促状が送られてきて、口座の差し押さえをするぞ、というような文句が書かれていたりするわけだ。俺にしてみればその方が面倒がない。勝手に持って行けるならさっさとそうすればいいと思っていた。■最初に戻る。気がついたけど、俺は口座とマイナンバーが紐付いて困るたぐいの人間ではなかった。そんなことは保険と同じで全く期待できないけど、情報を利用して該当するあれやこれやの給付金を申請なしで勝手に振り込んでくれて全く構わないのだよ。


2020年06月02日 (火)

最終更新: 2020-06-18T09:50+0900

[AtCoder] AtCoder Beginner Contest 006D 問題 トランプ挿入ソート

ちょっと日記に書きたくなるような、適度に歯応えのある問題だった。問題は、例えば

2 4 6 1 3 5 

のような数列が与えられたときに、

1 2 3 4 5 6

のように昇順に並べ替えるためには、いくつの要素を移動する必要があるか、その最小を答えるというもの。

 1. 連続する2要素に注目して増加しているか減少しているか見てみたら?

例えば、「2 4 6」「1 3 5」の並びは2要素間の関係において増加しているのでそのまま温存して答えにできるのではないか、逆に、「6 1」の並びは減少しているので必ず介入して解消しなければいけない。

しかし2つの増加列の関係に注目すると、「2 4 6」と「1 3 5」の位置関係が前後しているために、 2 と 4 と 6 の3要素または 1 と 3 と 5 の3要素を移動しなければ答えになりそうにない。

 2. 数列全体から最長の増加列(※要素は連続してなくていい)を1つだけピックアップしたものが答えの一部になるのでは?

たとえば初期数列が以下の通りだったら、

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要素だけ。

 3. どのようにして最長の増加列の長さを知るか。ツリーを作る?

たとえば、以下の初期数列に対して、先頭の要素から順に継ぎ足して木を作るとする。

1 3 2 5 4 6

しかしこれは網羅してないながらすでにして冗長。(画像ソース:verbose graph.dot)

ここが思案のしどころ。

  1. ある要素の後ろにいくつの要素が続くかは、その要素の値によって決まる。
  2. だから 4 と 5 と 6 が複数回出現しているが、最も深いところの1つ以外は無用。
  3. くっつけられる場所を見つけるために、そのうちのどこにくっつけるのが最善かを知るために、都度都度葉を根まで(あるいは根から葉まで)たどるのはいかにも無駄。
  4. 知りたいのは深さだけ、それも最大の。中途半端はいらないし、経路もいらない。
  5. どの枝がどれだけ伸びうるかは 1 に書いた通り。さらに言えば値は小さいほど良く、小が大を兼ねる。
  6. 深さごとに最善の要素(最小の値)を1つ記憶しておけば足りる。
  7. たとえば上の画像に対応する作業配列は [1,2,4,6] になる。2番目の深さにおいて最善の要素は 2 であり、その他の 3, 4, 5 の後ろが 2 の後ろより長くなることはない。
  8. 新しい要素は作業配列の末尾に付け加えられたり、既存の要素をより小さい値で置き換えたりする。

    数列を先頭から処理するときの作業配列の変遷:[1][1,3][1,2][1,2,5][1,2,4][1,2,4,6]

 提出 #13936266 (AC / 227 ms / 4348 KB)

提出一覧を見ると 227 ms というのはいかにも遅い。

Ruby による提出(実行時間昇順)

ちらちらスクリプトの中身を見てると、二分探索の使用が目につく。それで気をつけて作業配列を見てみると、どの時点でもソート済みの状態が保たれているようだった。

できるだけ増加列の長さを伸ばしたいから、作業配列の末尾から更新位置を探していたし、更新位置が見つからない場合も想定していたけど、どちらにも無駄があった。位置探索はソート済みなのを活かして対数時間で済ませられるし、書き込む位置は必ず見つかる。

たぶん値の重複のあるなしで二分探索の使い方が変わるけど、この問題では重複なしが制約に含まれている。最近「bsearch_index の使い分けが見事」と評したのはこの提出>#13393878。lower_bound とか upper_bound とか -1 とか。Ruby には区別がないけど。

 提出 #13936659 (AC / 41 ms / 2556 KB)

凡人は一足飛びに答えにたどり着いたりはしない。しかしたどり着ける難易度ではあり、さらには提出した後でも発見があった。思わず日記に書きたくなる楽しさ。

 AtCoder Beginner Contest 165F 問題 LIS on Tree

特になんということもなかった。作業配列を深さ優先探索のあいだ使い回しするだけだった。

 提出 #14435898 (AC / 707 ms / 259260 KB)

問題名で解説記事を検索してみると、LIS() に関して色々な方法があるなかで、自分が唯一知っている方法がぴたりとはまる幸運があったと言えそう。

トランプ挿入ソートの解説記事を読むといやでも目に入るよね>LIS。ストレートな知識問題だって書いてるところがあったけど、知らなくても解けるし、むしろ問題を通して教えてもらえる、ありがたくも教育的な問題だった。

最終更新: 2020-07-10T21:58+0900

[AtCoder] AtCoder Beginner Contest 006B 問題 トリボナッチ数列

Ruby による提出(実行時間昇順)

2番目が 60 ms のところ、1番速い提出が 16 ms で済ませてしまっている。いったいどんな魔法を使ったのか、読んでみた。

 提出 #1163397 (nejiko96 さん / 16 ms / 4732 KB)

といっても、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 メソッドであるのだと思う。

これぞ線形代数って感じ(すくなくとも自分がイメージできる範囲の)。

 Tribonacci Numbers - GeeksforGeeks

素朴な手法から順番に紹介されている。1.再帰 2.配列メモ 3.三変数使い回し 4.行列の累乗

  1. A simple solution is to simply follow recursive formula and write recursive code for it,
  2. Time complexity of above solution is exponential. A better solution is to use Dynamic Programming.
  3. Time complexity of above is linear, but it requires extra space. We can optimizes space used in above solution using three variables to keep track of previous three numbers.
  4. Below is more efficient solution using matrix exponentiation.

 蟻本にはすべてがあるような気がしてくるな。

実際は自分の到達点の低さの反映に過ぎない。

最初に読んだときは動的計画法のラッシュで頭がパンクして「もういいです……」と本を閉じた。

その次に開いたときは実装したことのあるグラフアルゴリズムの登場に気をよくしていたところで、ここからが中級だ、と新しいチャプターが始まって、「もう無理です……」と本を閉じた。

182ページのコラムから

もっと高速な漸化式の計算

実は、m 項間漸化式の n 項目は行列を用いるのではなく、各項を初項の線形結合で表して繰り返し二乗法を行うことにより、O(m^2log(n)) で計算することも可能です。興味のある人は考えてみるとよいでしょう。


2020年05月30日 (土)

最終更新: 2020-05-31T18:32+0900

[AtCoder] NOMURA プログラミングコンテスト 2020C 問題 Folia

こんな非道な仕打ちがあるだろうか。

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 のまま残ってしまったと。

 提出 #13742470 (WA)

600点問題は解ける解けないの山が最初にあって、どちらかといえば時間をかけてもほとんど解けないのだけど、それだけに恨めしい。

 N よ! お前か! 提出 #13747866 (AC / 91 ms / 22960 KB)

N の制約「0≤N≤10^50 以上

 leaf の複数形は leaves です。

どうしても完全丸ぱくりになるので提出する気がなくなったけど、N=0 の場合を特別扱いせずに対応できるようにループの中身を半分ずらしたり、配列 B を後ろから前から往復して値を埋め込んでいる処理を2種類の累計値を管理するだけで済ませたりできる。そうすると最後の答えを出すのに sum メソッドもいらない。


2020年05月29日 (金) コンピューターは、評価を下さないという点で良い指導者である。何かを新しく学ぶ上で恐怖の大部分を占めるのは、他の人の前で失敗することだ。」■AtCoder について。他の人の提出が見られるというのは最上の学びの機会なんだけど、自分の提出が衆目に晒されている(しかも WA(Wrong Answer) を繰り返してたり!)というのは受け入れるのに努力を要する。誰もお前になんか注目していない、自意識過剰だという指摘は気休めにもならない。■努力とは。開き直りと多少の自負(「どうせ私はこの程度ですよ、されどこの程度ではありますよ」)。開き直りには雲の上の存在が一役買っている。自分にとって AGC とは6問中2問目までしか存在してないのと同じだし、その2問だって当たり前に解けるものではない。間違えるのが当然。暖色系 Coder は見栄を張り合う対象ではないし、その足元でどんぐりの背比べこそ恥ずかしい。そういう思いで WA を乗り越えている。