/ 最近 .rdf 追記 設定 本棚

脳log[2020-06-24~]



2020年06月24日 (水) 読まれるブログフォーマットと読者のリテラシーと好き嫌いの話。https://mobile.twitter.com/chokudai/status/1275308912896405507■個人的にはとってもわかる。「関係ない写真を間に入れまくる、内容のないblog特有のフォーマット」「リテラシー高めのエンジニア向け記事だとマイナスに働く効果のが大きいかなー、と思ってた」■たしかちょっと前に似たようなつぶやきが、それも AtCoder 界隈であった。動画かテキストかという話。自分はこういう派>「わからない。提出 #13147757 (WA)。解説 PDF で考え違いを教えてもらおうと思ったら解説動画しかなくて、うんまあ、じゃあいいや。」 テキストでぱっぱっと要点だけ知りたいし、まだら模様の理解度に合わせて時間を配分したいし、動画はそれができないから時間の無駄だと思ってる。それが言い過ぎだとしても、効率が悪いのはたしか。■過去に何度か書いたけど、自分は画像処理が苦手でアイコンをほとんど識別しないし、現実や画面を通した映像から読み取れることがごく限られているし、テキスト処理に特化している。人間(の集団)が嫌いである種の実写がきついというのがまた別にあるけども。AtCoder の解説動画がどんなものかはまだ確かめたことがないけども。誰々がすごく丁寧な解説をするという評判だけ聞いてるけども。■Web メディアがページを無駄に(※主観です)細かく分割するのも必ずしも広告がらみの理由ではないらしいし、マスにリーチするということは、その過程が見えるということは、とりもなおさずターゲットが自分から離れていくことを意味するのだともはや承知している。逆にターゲットが自分の方に近づいてくるとき、その過程は見えない。まだ自分にリーチしてないからね。だから好き嫌い(※主観)ではあっても善し悪し(※客観)ではないんだろう。■あと「エンジニア」っていってもピンキリで、ピンはごく少数なので……。Web サービスでユーザーが増えると質の平均が下がったと嘆きが聞こえてくるのはあるあるなので。■パソコン通信は知らないインターネット老人会からでした。


2020年06月23日 (火) 免許を更新した。更新手続きの休止期間が長引かなくて余計な面倒がなかったのは幸い。今日に備えて10年来の眼鏡を新しくしていた。ボーダーについてはなぜか 0.6 だと勘違いしていたのだけど、0.5 から 0.8 までいろいろ基準があっても 0.6 はないみたい。眼鏡屋さんが 0.7 だと言うのはしかたがない。自分の事情は自分で知っておく必要がある。いつまでも慣れない深視力は 10.0 mm、5.9 mm、0.9 mm で余裕(20mm3回より悪くなければいい)。■通知ハガキの記述と異なっていたのだけど、まず、4桁の番号は1つだけしか入力しなかった。ハガキには2組と書いてあったけど、1つは免許センターの機械が勝手に決めた。もう1点はハンコがいらなかったこと。用意するものに含まれていたから持っていったけど、そういえば使わなかったなと。

最終更新: 2020-07-09T19:28+0900

[AtCoder] AtCoder Beginner Contest 157D 問題 Friend Suggestions

 成長の記録

WA(Wrong Answer)の記憶なんてないまま新鮮な気持ちで挑戦したら普通に解けた。過去の提出を見直してみたらまあ、解答の構成がびっくりするほど瓜二つ。

では二者の分かれ目はどこに?

 友達の友達ネットワークの把握 (WA の理由)

WA の方はすべての人について一度だけ、その友達リストを処理している。AC した方は深さ優先探索で再帰的に処理している。なぜ再帰が必要か?

ある人 A と B が友達で、また C と D が友達であるとする。この時点で2つの友達グループがある。ここで A と C の両方と友達である E さんを処理するときに、A と C と E を繋ぐだけでは不十分で、すでに A や C とグループを作っていた B と D の所属グループまで更新しなければいけない。これをするためには配列を通り一遍に処理するだけではダメで、友達グループを記録した配列を何度もなめなめするか、再帰的に処理をする必要がある。

今ではこういう処理を Union-Find と呼ぶことを知っているし、グループの大小を管理することで書き換え処理が軽減できることも知っている。検索したらこれは序の口で、まだまだ奥が深いらしい。読んでないよ>「素集合データ構造(Union-Find)」「UnionFindTree に関する知見の諸々 - noshi91のメモ

 例えば ARC097 の D 問題 Equals
自分の提出 #8121358 (AC / 310 Byte / 340 ms / 16252 KB)
何も考えず小さいインデックスにグループを代表させている。
betrue12 さんの提出 #2497462 (AC / 1004 Byte / 315 ms / 15116 KB)
rank(木の高さ)の小さい方を大きい方に接続している。

インタープリタ型言語は基本的に書けば書くほど実行に時間がかかるものだし、一般化して構造化すれば無駄が生じる。多く書いてそれが速いなら、アルゴリズムが優れていることに他ならない。

ところで、つい先月の新しい提出にすごいのがありますね。「Ruby(2.3)によるすべての提出(実行時間昇順)

  • tamura2004 さんの提出 #13758236 (AC / 915 Byte / 291 ms / 12292 KB)

    1. UnionFind クラス唯一のインスタンス変数 @data 配列の初期値は -1 であり、これはすべての要素がサイズ1のグループを作っていることを意味している。def size(a); -@data[find(a)]; end @data ひとつでグループとサイズの両方を記録している。
    2. unite メソッドでは @data[b] = a によって b グループを a グループに併合している。事前の比較により a グループの方が b グループより小さくないことが保証されている。しかし同時に行っている @data[a] += @data[b] の意味がわかりにくい。これは @data のもう一面、大きさを合計している。
    3. find メソッドの再帰停止条件は @data[a] < 0。負になるのはルートに対応する要素の値で、ルートにぶら下がる要素は 0 以上の値で他の要素をポイントしている。

    @data 変数ひとつであれもこれも済まそうなんて、なんてケチで欲張りなんだ。

 必要なのは中身ではなくサイズ (TLE の原因)

コンピュータで処理するものなのだから、現実的制約は無視できない。集合演算と整数の引き算(+α)のコストの差。十分過ぎて必要のない情報にコストをかけてはいけない。

 「成長の記録」とか見出しをつけたけど……

引き合いに出した ARC097 の D 問題の AC 提出は去年の10月のものだった。3月時点ではそれを糧にできていなかったのだな。

さらに言えば ARC097 の D 問題には AC 提出の前に1つ TLE になった提出があったのだけど(#8121130)、TLE の原因がグループを表現するのに集合を使っていたから。3月の提出が TLE なのと同じ理由。まるで成長していない……(それどころか WA まで)。去年の10月は TLE のままで終わらなかったのが偉くて、30分くらいかけてグループの中で一番小さいインデックスにグループを代表させることにしたらしい。それがどうして3月に生きなかったのか……。

しかし今日の日記を書く過程でさらに省メモリかつ高速なスクリプトへの手がかりを見つけられたのはもっけの幸い。わずか2日での進歩である。

tamura2004 さんの提出を参考に。同じ問題に対する#10479576ではなくて、さっき引き合いに出した#13758236の方。

出力形式も変えたけど、ジャッジがスペース区切りと改行区切りを区別しないらしいのは kotatsugame さんの何かの提出で知った。これって kotatsugame さんの記事なんだけど……「AtCoderで実行時間0msを狙う - Qiita

どうしても1ケースだけ1msかかってしまう……せや!テストケース特定したろ!」「ちょっとくらい……探索サボってもバレへんか」「進む方向を定めるのに、ベクトル(sin(r),cos(r)) (r=0,...,99)を使っています。根拠はないです。

「根拠はないです」やあらへんでまったく。ゴルファーでもあるこんな人がジャッジの細かい仕様を知らんはずないんだよなあ。

それに問題を読み直したら「答えを空白区切りで順に出力せよ」と書いてあって、たしかにスペース区切りの出力例は出力形式の一例に過ぎないといえる。

最終更新: 2020-09-01T19:43+0900

[AtCoder] AtCoder Beginner Contest 157E 問題 Simple String Queries

 成長の記録(2回目)

コンテスト本番では問題文を読むところまでたどり着けなかったし、仮に読んでいても TLE は免れなかったろう。

しかし今や蟻本でセグメントツリーについて読んだので何の問題もない。適切なデータ構造を扱えますか、というだけの問題である。それと時間内に実装できますか、という……(BITを使おうとしてた時間を含めて3時間くらいいじくってた)。

提出 #14702134 (AC / 835 Byte / 449 ms / 39004 KB)
セグメントツリーを初めて実装したのがこのとき>20200610p01。今回は更新があったのと、ツリーを根からたどったのと、2の冪乗になるように詰め物をしなかったのが初めてのこと。
提出 #14702414 (AC / 774 Byte / 350 ms / 38728 KB)
最初の提出では本を見ながらそれにならって値を根からたどって取得したけど、そうしなければいけない理由はなかったのだった。以前の雰囲気実装と同じく葉から始めて値を取得するバージョンがこれ。速いよね。fn メソッドをインライン化したらもうちょっと稼げると思う。
提出 #14702882 (AC / 708 Byte / 333 ms / 38948 KB)
fn メソッドをなくしたけどあんまり変わらない。ループの中で多重代入というのが影響することも知ってるけど(20200428p01.08.01)、表記の簡潔さはゆずれない。
ST#[]= メソッドのために1個だけ詰め物をしたけど効果がなかったので(#14702766 RE)、詰め物の意味はない。消し忘れ。
スクリプト言語での popcount は二進文字列化して "1" を数えるものが多いみたいだった。高々26ビットだということがわかっているので log2(32) セット(=5組)のビット演算で済ませる魔法があるらしいし、そういう提出もあった。その他にも色々と『ハッカーのたのしみ』で紹介されている。ループを回してるのは芸がないね。

 Python によるこれらの提出。提出 #14610743提出 #10774518

内部データサイズが単なる 2N に見えるのが不思議。添字の扱い方はヒープに見えるけど、2の冪乗じゃないと階層が崩れて右が左に左が右になりそうなものだ。さっぱりわからん。

蟻本の著者の一人のスライドを見つけた。

  • 実際には,この実装なら n が 2 の累乗でな くても動作する

    値の更新の方はこのままではダメで,同様の 手法で再帰関数で書けば OK

  • ただし,配列サイズは MAX_N * 2 - 1 では 足りない – MAX_N * 4 取れば十分

まだわかりません。それに Python による fold 関数とスライドにある query 関数は引数の数が全然違うんだよね。片方は再帰ですらないし。

 追記@2020-09-01 「Segment Tree のお勉強(1) | maspyのHP

一方の提出ご本人による記事である。「いわゆる非再帰実装」「N = 2^n を仮定しない」 これこれ。ありがたやありがたや。


2020年06月22日 (月) [AtCoder] かなりの期間その存在を知らなかったし、今でも全くアクセスすることのないページが「順位表」。ABC 全完が当たり前でタイムアタックにしか意味がない人にとっては関心が向く唯一の対象かもしれないけど、E 問題も F 問題も、下手したら D 問題も解けない人間には興味も関係もないこと。……ということをわざわざ書くのは、Twitter を見ていて「そうではない人もいるのだなあ」と気付かされるから。コンテスト中に確認したいらしい。


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