最終更新: 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 を仮定しない
」 これこれ。ありがたやありがたや。