関係ない写真を間に入れまくる、内容のないblog特有のフォーマット」「
リテラシー高めのエンジニア向け記事だとマイナスに働く効果のが大きいかなー、と思ってた」■たしかちょっと前に似たようなつぶやきが、それも AtCoder 界隈であった。動画かテキストかという話。自分はこういう派>「わからない。提出 #13147757 (WA)。解説 PDF で考え違いを教えてもらおうと思ったら解説動画しかなくて、うんまあ、じゃあいいや。」 テキストでぱっぱっと要点だけ知りたいし、まだら模様の理解度に合わせて時間を配分したいし、動画はそれができないから時間の無駄だと思ってる。それが言い過ぎだとしても、効率が悪いのはたしか。■過去に何度か書いたけど、自分は画像処理が苦手でアイコンをほとんど識別しないし、現実や画面を通した映像から読み取れることがごく限られているし、テキスト処理に特化している。人間(の集団)が嫌いである種の実写がきついというのがまた別にあるけども。AtCoder の解説動画がどんなものかはまだ確かめたことがないけども。誰々がすごく丁寧な解説をするという評判だけ聞いてるけども。■Web メディアがページを無駄に(※主観です)細かく分割するのも必ずしも広告がらみの理由ではないらしいし、マスにリーチするということは、その過程が見えるということは、とりもなおさずターゲットが自分から離れていくことを意味するのだともはや承知している。逆にターゲットが自分の方に近づいてくるとき、その過程は見えない。まだ自分にリーチしてないからね。だから好き嫌い(※主観)ではあっても善し悪し(※客観)ではないんだろう。■あと「エンジニア」っていってもピンキリで、ピンはごく少数なので……。Web サービスでユーザーが増えると質の平均が下がったと嘆きが聞こえてくるのはあるあるなので。■パソコン通信は知らないインターネット老人会からでした。
最終更新: 2020-07-09T19:28+0900
WA(Wrong Answer)の記憶なんてないまま新鮮な気持ちで挑戦したら普通に解けた。過去の提出を見直してみたらまあ、解答の構成がびっくりするほど瓜二つ。
では二者の分かれ目はどこに？
WA の方はすべての人について一度だけ、その友達リストを処理している。AC した方は深さ優先探索で再帰的に処理している。なぜ再帰が必要か？
ある人 A と B が友達で、また C と D が友達であるとする。この時点で２つの友達グループがある。ここで A と C の両方と友達である E さんを処理するときに、A と C と E を繋ぐだけでは不十分で、すでに A や C とグループを作っていた B と D の所属グループまで更新しなければいけない。これをするためには配列を通り一遍に処理するだけではダメで、友達グループを記録した配列を何度もなめなめするか、再帰的に処理をする必要がある。
今ではこういう処理を Union-Find と呼ぶことを知っているし、グループの大小を管理することで書き換え処理が軽減できることも知っている。検索したらこれは序の口で、まだまだ奥が深いらしい。読んでないよ>「素集合データ構造(Union-Find)」「UnionFindTree に関する知見の諸々 - noshi91のメモ」
インタープリタ型言語は基本的に書けば書くほど実行に時間がかかるものだし、一般化して構造化すれば無駄が生じる。多く書いてそれが速いなら、アルゴリズムが優れていることに他ならない。
ところで、つい先月の新しい提出にすごいのがありますね。「Ruby(2.3)によるすべての提出(実行時間昇順)」
tamura2004 さんの提出 #13758236 (AC / 915 Byte / 291 ms / 12292 KB)
def size(a); -@data[find(a)]; end @data ひとつでグループとサイズの両方を記録している。@data[b] = a によって b グループを a グループに併合している。事前の比較により a グループの方が b グループより小さくないことが保証されている。しかし同時に行っている @data[a] += @data[b] の意味がわかりにくい。これは @data のもう一面、大きさを合計している。@data[a] < 0。負になるのはルートに対応する要素の値で、ルートにぶら下がる要素は 0 以上の値で他の要素をポイントしている。@data 変数ひとつであれもこれも済まそうなんて、なんてケチで欲張りなんだ。
コンピュータで処理するものなのだから、現実的制約は無視できない。集合演算と整数の引き算(+α)のコストの差。十分過ぎて必要のない情報にコストをかけてはいけない。
引き合いに出した ARC097 の D 問題の AC 提出は去年の10月のものだった。３月時点ではそれを糧にできていなかったのだな。
さらに言えば ARC097 の D 問題には AC 提出の前に１つ TLE になった提出があったのだけど(#8121130)、TLE の原因がグループを表現するのに集合を使っていたから。３月の提出が TLE なのと同じ理由。まるで成長していない……(それどころか WA まで)。去年の10月は TLE のままで終わらなかったのが偉くて、30分くらいかけてグループの中で一番小さいインデックスにグループを代表させることにしたらしい。それがどうして３月に生きなかったのか……。
しかし今日の日記を書く過程でさらに省メモリかつ高速なスクリプトへの手がかりを見つけられたのはもっけの幸い。わずか２日での進歩である。
tamura2004 さんの提出を参考に。同じ問題に対する#10479576ではなくて、さっき引き合いに出した#13758236の方。
出力形式も変えたけど、ジャッジがスペース区切りと改行区切りを区別しないらしいのは kotatsugame さんの何かの提出で知った。これって kotatsugame さんの記事なんだけど……「AtCoderで実行時間0msを狙う - Qiita」
「どうしても1ケースだけ1msかかってしまう……せや！テストケース特定したろ！
」「ちょっとくらい……探索サボってもバレへんか
」「進む方向を定めるのに、ベクトル(sin(r),cos(r)) (r=0,...,99)を使っています。根拠はないです。
」
「根拠はないです」やあらへんでまったく。ゴルファーでもあるこんな人がジャッジの細かい仕様を知らんはずないんだよなあ。
それに問題を読み直したら「答えを空白区切りで順に出力せよ
」と書いてあって、たしかにスペース区切りの出力例は出力形式の一例に過ぎないといえる。
最終更新: 2020-09-01T19:43+0900
コンテスト本番では問題文を読むところまでたどり着けなかったし、仮に読んでいても TLE は免れなかったろう。
しかし今や蟻本でセグメントツリーについて読んだので何の問題もない。適切なデータ構造を扱えますか、というだけの問題である。それと時間内に実装できますか、という……(BITを使おうとしてた時間を含めて３時間くらいいじくってた)。
内部データサイズが単なる 2N に見えるのが不思議。添字の扱い方はヒープに見えるけど、２の冪乗じゃないと階層が崩れて右が左に左が右になりそうなものだ。さっぱりわからん。
蟻本の著者の一人のスライドを見つけた。
実際には，この実装なら n が 2 の累乗でな くても動作する
値の更新の方はこのままではダメで，同様の 手法で再帰関数で書けば OK
- ただし，配列サイズは MAX_N * 2 - 1 では 足りない – MAX_N * 4 取れば十分
まだわかりません。それに Python による fold 関数とスライドにある query 関数は引数の数が全然違うんだよね。片方は再帰ですらないし。
一方の提出ご本人による記事である。「いわゆる非再帰実装
」「N = 2^n を仮定しない
」 これこれ。ありがたやありがたや。
唯一生き残ることが出来るのは変化できる者である。」(だから憲法を変えよう)とか言ってるけども、こちらが進化論になぞらえて読み取るメッセージは「勝てば官軍」であるので、なんだ何も間違っていないな(とっとと負けやがれ)。■「二階氏「ダーウィンも喜んでいる」 進化論の誤用問われ：朝日新聞デジタル」 マンガが子供にも失礼な子供だましなのよりも、この聞く耳のなさ、反省のなさが問題だと思うんよな。多様な意見への寛容さをアピールしたそうに見えるけど、そういう話ではない。それがわからないなら愚か者だし、わかってまぜっかえしてるなら不誠実だ。あ、それが平常運転でしたね。■日本心理学会@jpa_psych「日本人間行動進化学会「「ダーウィンの進化論」に関して流布する⾔説についての声明」 hbesj.org hbesj.org/wp/wp-content/… 6:14 - 2020年6月27日」
ちなみに「ぼく」はIQ+30くらいの設定です。」というのがよく解らないけど、自分は対面だと IQ にマイナス100補正がかかります(元が100以上あるかは知らない。小学校でそれっぽいのを受けたけど結果は教えてくれなかったよね)。考えながら話せない。会話に脳のリソースを100%持っていかれる(つまり能力が足りていないということだからあわあわする)。なんなら見られているだけで何も考えられなくなる。隣に人が立つだけで小便が引っ込むような。■(ダミー問題だけど)履歴の管理。いきなりだと面食らうだろうなあ。まず問題のコンテキストがわからない。そのあたりはブログ筆者も同じとみえて質疑が参考になる。とりあえず配列で持って、現在位置を示すポインタを増減するかな、ということを自分で考えてから記事を読み直したらさっきより内容がよく掴めた。■計算量の話題。配列だとメモリの再確保で履歴の追加が最悪 O(N) とか、そんなことまで気にするの？ 「
「まあ、一般的な使い方なら大丈夫だろうけどね。これを解決するにはどうする？」」 えー、聞くの？ ブラウザの進む・戻るボタンの履歴なんてタブとともに捨てられるんだから気にする必要なくない？ 適当に上限を100にしてリングバッファにしても普通の利用者は上限の存在に気がつかないだろうから、それで。■「
ところで、仕様追加をしたいんだけど。古い履歴は自動で捨てるようにしたい」 あっ、これって進む・戻るボタンに留まらない履歴管理の話だった(読み返したから思い出せた)。そうすると複数のウィンドウと複数のタブから報告される訪れたサイトと時刻のペアをどんどん追記していく感じになる。タイムゾーンとか文字コードはいい感じに。進む・戻るボタンの履歴はタブのセッション記録に別途保存しておくだけでいいでしょう。■「報告される」(※自分で書いた)ってなんだ？ そんなサーバープロセスは存在しない、こともないか。Firefox は１タブ１プロセスなんてことはない。仮に履歴ファイルの排他が Web ブラウズのレスポンスを低下させるなら、プロセスごとに仮の履歴ファイルを作るようにして、プロセス終了に合わせて統一履歴ファイル(places.sqliteみたいな)にマージするようにするかな。それだとウィンドウごと、タブごとに見られる履歴の内容が最新でなく異なるって？ じゃあプロセスの終了を待たずに随時バックグラウンドでマージすればいいじゃない。クラッシュ耐性も上がるよ。■「仮に履歴ファイルの排他が Web ブラウズのレスポンスを低下させるなら」(※自分で書いた)←こんな状況は考えられない。ブラウザの使用者は１人だよね。人間ミューテックス。
最終更新: 2020-06-15T23:25+0900
第三回まで過去問をやったけど(20200607p01、20200607p02)、やはり順当に解けるのは K 問題まで。L 問題が自分にとってのチャレンジ。そこまでの問題が漏れなく時間内に解ければ上級認定。今回時間をかけてでもこれが解けたのは、今日たまたま読んでいた蟻本で紹介されていたデータ構造を雰囲気で実装してみたことによる。(この日記は今日書いた>20200602p02.03)
ヒープ構造を使って冗長な情報を削ったら同時に保険がなくなって、雰囲気実装のふんわりした理解の穴が露呈してバグに苦しんだ。AC と AC のあいだに 3WA。
二分木におけるLCA
木の構造が定まっているので、bit演算で計算できる。
こんな感じでうまいことできないかずっと考えていたのだけど、バグが取れてみれば、１つか２つのノードを見るだけでは済まないみたいなのでもとから無理だったっぽい。
他の人(Ruby では２人いる)の提出を見ていたら不備に気がついた。
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 のサイズが２のべき乗でヒープの最下段にきっちり収まるとき、なぜか倍のサイズを確保してしまってる。
例えば A.size == 8 のとき、ヒープサイズは 8+4+2+1 の 15 で十分だけど、上の BL の定義ではヒープ H のサイズが 31 になる。無駄のない定義は BL=1<<(A.size-1).bit_length。-1 がキモ。
これはうまくないみたい。今回は値の更新がなかったけど、更新を遅延させて値の取得に合わせて伝播させるためには、上から下っていかないといけない。
更新を遅延させるとか、考えてもみなかった。
それに最下段の要素に直接アクセスできたのは今回の問題に限った特殊条件ではある。範囲が配列の添字、０から連続する離散値だっていう。
必要になるまで考えないでいいことは考えない方針で。
上に上るにしろ下に下るにしろ、自分が左右どちらの枝にいるかは考える必要がなくて、右ないし左に移動してから隣の階層に移動するだけで次の判断がつく。
右(左)に移動するとは、兄弟もしくは従兄弟ノードに移動するということ。最初に右の枝にいたか左の枝にいたか、そして右に移動したか左に移動したかで関係が違ってくるが、気にする必要がない。そのうえで上の階層に移動するとは、元のノードから見て親か伯叔父ノードに移動するということ。いとこの親ならおじさんである。
具体的なコードは次で。
| 提出 | コード長 | タイム | メモリ |
|---|---|---|---|
| とりあえず AC | 660 Byte | 1293 ms | 93824 KB |
| ちょっときれいに AC | 740 Byte | 870 ms | 61964 KB |
| 十分に詰めて AC | 707 Byte | 700 ms | 51032 KB |
単純にタイムを縮めるだけなら他に優れた解法がある。これは次にこのデータ構造を使う準備みたいなもの。
すっごく読みやすいね。実は答えを保持するスタックに push/pop するだけで答えになるらしい。しかも速い。
自分の最初の提出(TLE)がこれで、#14163100、素朴なやり方では無理なんだと思っていたのだけど、どういう違いが AC(速い) と TLE を分けたのか。
もっともらしいことを想像で書こうとしたのだけどよく解らなくなった。バグで無限ループしてるという方が納得できる。だって K の大小や D の大小に応じて、最小値を求める区間や回数はしっかり反比例してる。たしかに重たいケースで TLE になってるみたいだけど、他のケースの10倍20倍も時間がかかるというのは解せない。
D が小さくて A 数列がほぼ昇順に並んでるときに、N の上限の20万要素ちかい範囲から何度も最小値を選ばされる地獄を見ることがあるのか。いやあ、そんな意地悪な入力を与える人はいないと信じるよ。
最終更新: 2020-06-09T19:05+0900
答えを出すだけなら簡単。社長を頂点とするピラミッドを遡るあいだに上司として出くわすかどうか確認するだけ。こういう問題は好き。逆にいつまでも数が合わない数え上げ問題は嫌い>禁止された数字への自分の提出。そもそもサンプルへの答えがいつまでも一致しないから、提出に至らないスクリプトが山ほど隠れている。
簡単ならどこが問題か。
N の上限が15万だから、そして組織が非効率の極み直列15万階層だったなら、１つのクエリに答えるために15万マイナス１回階層を上らなければいけない。クエリは最大10万個ある。
そこは一応読めていたので、社員ごとに社長から何階層下にいるかという情報をメモしておいて、社員間の階層の隔たりと同じ回数だけ上司をたどれば答えが出せるようにしていた。でも TLE と RE。最悪の場合はやっぱり15万マイナス１回たどらなければいけないのだから、TLE はまあ当然。
社長から始めて決まったやり方で社員を一列に並べていったら、ある社員とその部下と部下の部下以下末端までを一定の連続する範囲で表せるのではないかと考えた。なんのことはないそれって深さ優先探索と同じ順番だったのだけど。
それで TLE はすべてなくなった。１度だけ15万マイナス１階層をたどってしまえば、あとはすべてのクエリに定数時間で答えられる。
しかし TLE はどれも RE に変わっていた。最初の提出からかなりの数存在しているこの RE は何だ？ RE ってだいたいはヌルポだからよくある配列の範囲外アクセスが原因だろうと、考えるのを後回しにしていた。しかし目を皿のようにして調べてもその可能性はなかった。
再帰呼び出しをやめてスタック変数を……というと意味が違う。スタック構造を持つ変数をスタックの代わりに使うようにしたら通ったので、呼び出し階層が深すぎたのが RE の原因だった。最悪で15万マイナス１階層は深すぎるだろうなあ(最初から読んでおけ)。
しかし実行時間は変わらず。「Ruby によるすべての提出(実行時間昇順)」を参考にすると、
ということが言えると思う。他に差がつく要素があるだろうか。
最終更新: 2020-06-26T13:37+0900
やはり解けたのは K 問題までだった。ただし第一回と違って途中で１問落としたりはしていない。もうひと踏ん張りで80点を超えて上級だけど、残された問題の予想される難しさと裏腹に考える時間が残ってないんだよなあ(本番じゃないので途中でお風呂に入って本を読んだりしていたけども)。
第一回、第三回に共通する問題の傾向として、数学的応用的な要素が抑えられていて、愚直に効率的なコードが書ければ解けるものが選ばれている印象。よく知らないけど、一般的なお仕事コーディングに寄せていこうとしてるのかな。基礎的な知識とその初歩的な運用に漏れ抜けがないことを確認しようとしてるのかな。(緑色以下のコーダーには保証できることがない、というツイートを見かけたので。このへんとか>https://mobile.twitter.com/chokudai/status/1274756588624965632)
Python で解けることは運営元で確認してるらしいので(⇒)、Ruby でも方法はあるはずなんだよなあ。
タイムだけちらっと見た>Ruby でのすべての提出。提出数は４つで、ユニークユーザーは２人。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 回のループで４回ずつ行う二分探索の時間に影響する。N は棚の数だから商品数(メモリ)と商品の検索(時間)の両方に響く。問題が「手前から ai 番目までにある商品を見た後、見た商品のうち最も消費期限の値が大きいものを選んで棚から取って購入します
」だから、棚を選ぶ検索は避けられない。方法があるとしたら、予めうまいことソートしてしまってループの中では検索しないか、４回を２回に減らすか……。
半分以上がTLE。ACも17個あるからやり方は間違ってないと思う。しかし PAST の問題が考察よりも実装重視の傾向を持っている以上、TLEに甘んじるわけにはいかない。でも無理ぽ。
TLE がすべて WA か AC になりました。C++ のちから。TLE の陰に WA が隠れていたということで、やり方が間違っていた。
Visited フラグを立てるタイミングを誤っていたのと、訪れなければいけない街と街のあいだの移動コストを計算するときに、訪れなければいけない別の街を通ってしまう場合の考慮が抜けていた。
この問題を Ruby で、試験時間内に解けるなんてことがある？ ちなみに現在 Ruby で AC 提出はない>Ruby によるすべての提出。
ところで、1695 ms は C++ 最遅だった。C++ を使うなら２桁msで解けるらしい。
さっき「訪れなければいけない街と街のあいだの移動コストを計算するときに、訪れなければいけない別の街を通ってしまう場合の考慮が抜けていた
」と書いた。その対策として、関心のない街を迂回するルートを２街間の最短経路として採用するようにした(たぶんルートなしにした方が良かった)。もし他の街を中継するルートの方が結果的に低コストなら、そのルートは２本以上の２街間最短ルートの組み合わせとして現れてくるので。
でもこのステップで求めるものを、２街間の移動コストに加えてその際に通過する街と定義したなら、もっと速くゴールにたどり着けていたかもしれない。
解答は２パートに分かれているが、どうやら後半は幅優先探索ではなく DP でやるものらしい。もちろんその方が最遅より速くなるだろう。
でもまだ……。一度通過した街に戻るのにも移動コストがかかるから、状態や遷移には現在位置が関わってくる。それをベルトコンベヤ式に取り扱って答えにたどり着けるイメージが湧かない。二次元の遷移が解らない。
https://mobile.twitter.com/atcoder/status/1273915562989502465
気がついたこと
(たぶんルートなしにした方が良かった)。もし他の街を中継するルートの方が結果的に低コストなら、そのルートは２本以上の２街間最短ルートの組み合わせとして現れてくるので。」と書いたが、あれは嘘だった。
注目している K 地点間の移動コストは K*(K-1)/2 通りを調べるのではなく、K 通りを調べるのが良さそう。
終点を K 地点に限って試行回数を増やすより、終点を N 地点から限らず試行回数を K 回に留めるということ。
後半はワーシャル-フロイド法に見える３重ループ。
ただし街と街を結ぶ中継地点(一番外側のループ)は街ではなく経由地のリスト。