従来の日本語で「重複」と言うと「１つ以外は無駄」というニュアンスで使われることも多かったため知らないと混乱することがあるが(実際ゲーム関連サイトや攻略本などで逆の意味で使われることもあるようだ)、既にかなり定着しているのでそういうものと割り切るしかないだろう。誤解を招きたくない場合は「重複する」を「重ね掛けできる」等と言い替えることも出来る。」 つまり、「効果が重複する」とは「効果が１つ以外は無駄になる」という意味なんだけどゲーム用語では逆の意味になることも多いから「重ね掛けできる」と言い替えた方がいいかもね、と言っている。■ひとつ疑問があります。自分に言わせればトンデモな内容のスクリーンショット(文章)のソースが、検索では見つけられなかった。見つけたら是非、「重ね掛けできる」という用語をゲーム以外のどの界隈で使用するつもりなのか知りたかった。だってゲーム用語としての重複は(そして自分に言わせれば伝統的な日本語としての重複は)もう「
既にかなり定着しているのでそういうものと割り切るしかない」と書かれているのだ。誤解のおそれはない。なら誤解を避けるために「重ね掛けできる」と言い替えた方がいいのは、どの界隈の話なのか。俺はゲーム業界の中のさらに狭いジャンルの中で広まりつつある誤用だと思ってる。課金のように。■たぶんまとめ方が恣意的だっただけで、コメント欄が“そこそこ”まともなことに救いを感じてる。■あ、
ユースケースのコードをオブジェクトよりも上のレイヤーに取り出す、ということをやってみましょう。今、ユースケースのコードは、オブジェクトのクラスの中にあります。このユースケースの部分を、クラスの外側に出すのです。そうすると、オブジェクトの方は基本的なクラスのインスタンスのままなので、とても単純です。しかし、これらは実際のところユースケースの一部にはなりません。では、ユースケースの部品は何でしょうか？ ロールですね。ユースケースの部品は、ロールの中にあります。開発者は、このようなロールの中からいくつかを選んでまとめます。このまとまりを、コンテキストと呼びます。 つまり、コンテキストがユースケースに相当します。」■ゲームの造りにこれと似た構造があるという話。世界があってプレイヤーキャラクターがいて、プレイヤーははしごを登ったり椅子に座ったり運転席に乗り込んだりする。ゲームの造りとしての話だけど、プレイヤーが世界中のあらゆるオブジェクトに対してどう振る舞えばいいのか何が起こるのかを知っているのではなく、逆にインタラクティブオブジェクトの方がプレイヤーキャラクターの動きをプログラムして操っているのだとか。なんか似てない？
if k==2 が最後の TLE 対策。それも含めて思いつきを全部試してみましたみたいな頭悪そうな雰囲気が気に入っている。■if k==2 の中身は Pairs と Handshake の解答のオーダーを改善する過程で出てきた形>20210401p01。
.tr.to_i+.tr.to_i (@2021-06-28 .to_i 一発(相当)で計算できるこんな言語もあるらしい。「2001を2進数で解釈するというのは通常だと意味が通らないが、dcにおいては構わず2×2^3が使われる」)■今日はこの他に取りこぼしていた「045 - Simple Grouping（★6）」を Ruby で通しておいた。組み合わせの総当たりが bitDP でできるというのは初めて知った。Avoid War がまだ通せないとは 20210622 で書いたけど、そのときに覚えた部分集合の列挙をビット演算で行う方法(蟻本に載っていた。144 ページ)がさっそく使えた。１つのケースだけ 20 秒くらいかかって TLE になるので、その場合だけ別の方法で答えを出すなど>#23710778 (1087 ms / 同じ内容)。□わずかな時間を削るためにいろいろと猪口才なことをしている。配列の配列を作るときに長さ14で2^{15}個のインスタンスがいいか長さ2^{15}で14個のインスタンスがいいかとか。２点間距離をメモした D 配列がそのまま DP 配列(E)の初期値であるとか(だから本当は３ビット以上立っている数に限って列挙したい)、DP 配列のその他の初期値が最大値ではなく 0 でいいとか、それによって中間ループを K 回回さないで済んでるとか。ループの中で最初から最後まで使われている d 変数の初期化が実は１回だけですよとか。最内ループの C if A && B が多少冗長ではあるがコストの順に並んでいて総合的には得するだとか(少なくともローカルでは)。しかし、点を一列に並べて端っこから２番目の点を無き者にしてループの指数を１減らす試みは失敗した。x^2-1 の(用語不明)が x^3/3 だから、1 と -1 を……どんな式に代入するのか思い出せない。1^3/3-(-1)^3/3 だと思ったけどそれだと 2/3 なので、4/3 (図中)でも 1/3 (訂正ツイート)でもない。■ところで、錐体っていつ習う？ 覚えがない。■ X 軸を無視してるのが良くない気がする。つまり、斜線部っていうのは二次関数だけでなく X 軸と組み合わさってできあがってる範囲なわけだから……(で、どこをどう修正したら 1/3 になる？)。■謎は全て解けた！ x^2-1 の(用語不明)は x^3/3 でなく x^3/3-x だ。微分のつもりで定数項を捨ててはいけない。で、これに……？■ X 軸に沿って積分をする。\int_{-1}^1 dx が幅。高さにあたる値は y=0 と y=x^2-1 の差であり、y=0 の方が範囲内では上だからこう 0-(x^2-1)。面積は縦×横だから \int_{-1}^1 [0-(x^2-1)]dx。(用語不明)して 1 と -1 を代入して、-(1^3/3-1)--[(-1)^3/3-(-1)] = 2/3+2/3 = 4/3。だいぶ思い出したのではないか。1/3 との訂正ツイートは違う部分を訂正していたものと思う(よく見たら 1/3 は「体積」だってね)。最終更新: 2021-06-17T19:54+0900
「実装したことはないけどダブリング(要は繰り返し二乗法でしょ？)で効率的に親を辿る？」と書いたのがつい先月のことだけど、とうとうダブリングを実装する機会が訪れた。
この問題がどうして、選ばれた複数の頂点を決まった順番で環状に並べて隣接する頂点ペアの LCA が辺の本数になって割る２が答え、になるのかは解説３を読む。今は LCA にだけ注目する。
LCA の取り扱いは「巨大企業」や「筆塗り」で経験があるけど、線形より効率的な LCA の検索が案外面倒くさい。「最小共通祖先 [いかたこのたこつぼ]」にいくつか手法がリストアップされているけど、自分が知っている手段はセグメント木だけであり、セグメント木は書くのが面倒くさい。
そこでダブリングです。
間違えた(TLE)。
A = [ps=P.dup]
(D.max-1).bit_length.times{ # １世代上はすでに P としてあるので、１回分繰り返しが無駄かも。
A << ps = N1.times.map{|a| ps[ps[a]] }
}
Ans = lambda{|a,dd|
i = 0
while 0<dd
a = A[i][a] if 0<dd&1
dd >>= 1
i += 1
end
next a
}
A 配列に事前に親、親の親(２世代上)、４世代上、８世代上、とメモしておいて、Ans 関数(Ancestors の略ったら略)で「a の dd 世代上は？」という質問に対数時間で答えられるようにした。Ans 関数がこのようなインタフェースになっているのは、LCA を経由した２頂点間の辺の数を求めたい呼び出しもとで「同じ深さにある２頂点 a,b が初めて祖先を共有する深さは？」という問いを立てて、二分探索でその深さを確定させようとしたから。次のように。
Dst = lambda{|(a,b)|
da,db = D[a],D[b]
dc = (1..[da,db].min).bsearch{|dc|
Ans[a,da-dc] != Ans[b,db-dc]
}
next dc ? da-dc+db-dc+2 : (da-db).abs
}
競プロにおいては対数は定数と言われるけれど、かなり大きな定数ではあり、必要がないところで log をくっつけると TLE に苦しめられたりする>「Pairs」。同じ日記に書いてあるけど、「射撃王」や「Handshake」のように余分な log があっても TLE にならないこともある。
A 配列は正しくはこう使う。共有されている yuruhiya さんの解答 を見ても LCA#lca メソッドが同じ感じだったので、大嘘はついてないと思う。(Dst は Distance の略。D は Depth の略)
Dst = lambda{|(a,b)|
da,db = D[a],D[b]
a = Ans[a,da-db] if db<da
b = Ans[b,db-da] if da<db
A.reverse_each{|ans|
a,b = ans[a],ans[b] if ans[a]!=ans[b]
} if a!=b
next a==b ? (da-db).abs : da+db-2*D[P[a]]
}
実は解説２にはこれを説明する具体的手順が書いてある(あとで詳しく読んだ)。だけどありとあらゆる落とし穴にはまりたがる自分にとって、「こうすればいいんですよ」とか「こうしてはいけませんよ」いうアドバイスは役に立たないんですな。「要は繰り返し二乗法でしょ」というだけの理解で実装してみて、「あれは良かったここはダメだった」と納得するまでは身にならない。仮にアドバイスのおかげで最初からうまくやれたとしても、それは今回だけのことであり、将来必ず自分の性向に導かれて穴にはまる。早いうちに地図を作っておくべきだ。そうすれば多少は、ね。
最終更新: 2021-06-21T21:06+0900
すごく難しいです。答えの出し方に確証が持てないまま、とりあえずグラフとして解答を書いた。クエリ０に応じて辺を追加する。クエリ１に応じてノードの値を確定しながら X から Y までグラフをたどる。しかし TLE。
次にクエリ０では Y=X+1 だという制約を思い出して、グラフを配列上に配置した。しかしこれでは多少効率が良くなれど TLE は解消しない。制約はノード数(N)、クエリ数(Q)ともに上限が 10 万であり、１つのクエリに答えるのに線形時間をかけることができない。
局所の変更を全体に(対数時間で)波及させるのに BIT がまず浮かぶ。何を記録しようか。階差の累積値かなと思った。つまり、連続する３要素 A,B,C があり、２度のクエリ０によって A+B=S, B+C=T であるとわかっているなら、C-A=T-S から１つおきの２要素の差が直接にわかる。これの累積を記録しておけば、クエリ１で X と Y が 2×k はなれていても直接計算できる。
結局 BIT は使わなかった。クエリへの答え方は階差の累積という点で同じだけど、クエリの先読みをすれば事前に累積値が記録しておける。更新がないなら値の取得に対数時間がかかる BIT よりただの配列の方が良い。Ambiguous と答えるタイミングは Union-Find で管理した。
階差を使う解法は完全に「Y=X+1 (T=0 の場合)」という制約に依存しているので、とっかかりを失って困ってしまった。グラフなら困らないが TLE。階差を封じられてどうすればよいか。
解説が公開された。プラスかマイナスか、そんな単純な関係やったんか。それにしてもそこからさらに(厳しくない方の)制約をクリアさせられることがもうつらい。
Y=X+1 (T=0 のとき) という条件が外れた厳しい方の制約だけど、X から Y へ至る異なるパスがクエリ０によって与えられたときにどうすればいいかわからないでいる。定数時間で答えるためにどのような情報の持ち方をしておけばいいのか(グラフは TLE)。でもプラスかマイナスかという単純な関係なのならば、すべてのパスに関わるノードをまとめて詰め込んでおいて、つじつまが合うのだろうか。
連結なノード間であるノードを基準(たとえばゼロ)にして相対的な値を割り振っておく。ノード間の距離(の偶奇)も記録しておく。迂回路があっても分岐点・合流点のノードが持つ相対値はパスによらず共通だし、パスによって異なる非共通ノードも、ノード数の偶奇はたぶん同じになる。まだよくわからないのは、連結成分ごとに基準となるノードが必要だけど、連結成分同士が連結するたびに基準と相対値のふり直しをして許されるのかというところ。小さい方の連結成分を選ぶようにすればいいのだろうけど。
全部 Union-Find に乗せたいけどうまくいかない。Unite は当然として、Find で集合の代表を書き換えるタイミングでもごにょごにょすると、集合の合体があったとしても偶奇と相対値を適切に(新しい代表を基準にして)更新できると思うんだけど、符号で死ぬほどバグらせる。一見正しい答えに見えても、バグ×バグ=正常だったりする。
自分がやりたいのはたぶんこういうの。やっぱりできるんだね。不可能をやろうとしてるのでないとわかったのは朗報。
ところで、Ruby のようなスクリプト言語と C++ の実行時間が接近しているときは、入出力がネックになって C++ の実行時間が遅くなっている印象がある。C ランタイムとの連携を切ったり、std::endl が引き起こす flush を "\n" で回避したり、いろいろ対処法がある模様。
こっちの見た目すっきりな方はすっきりしすぎてて自分がやりたいことと同じなのかどうかもわからない。
ノード数が 2N あるなあ。前半 N 個と後半 N 個の位置づけとは。
偶数世界と奇数世界？ これはノード番号 X が偶数か奇数かという話ではなく二部グラフの話なのであって、あるノード X を赤色で塗った場合と白色で塗った場合を同時並行で扱っているのではないか、という……あてずっぽうです。
やった！ うんざりするほどバグらせてついに完成した(UnionFind 全乗せ版)。頭が整理されたところでバグまみれを捨ててイチから書き直したのが良かったと思う(それからもバグらせたんだけど)。
D[a] *= D[g] V[a] += D[a]*D[g]*V[g]
↑ここは無駄なことをしてる。修正版はこう↓
V[a] += D[a]*V[g] D[a] *= D[g]
Union-Find でグループの代表とサイズを管理するのはこれまでのおなじみだけど、同時に代表からの相対値を記録するのは考えたこともやったこともなかった。「重み付き UnionFind」というものがあるらしいが、いったい何に使うものなのか。
ノード数が 2N のすっきり解法は遠くから拝むだけにしておきます。
これも重み付き UnionFind。ノード番号の偶奇を利用すれば別途偶奇の管理をする必要がないらしい。クエリへの応答部分でだけ偶奇を気にすればいいというのがよくわからないが、たぶんこれを考えた先に Nachia さんのサイズ 2N のグラフがあると思う。
偶奇を一体でぐちゃぐちゃ扱う(自分)→偶奇に前提をもうけて整理されたグラフを作る(masa_aa さん)→偶奇と奇偶を並行させて偶奇の別を気にしない(Nachia さん)、という違いなのではないか、という印象を持っている。
あ find メソッドで再帰呼び出しをしていない。スタックオーバーフローのおそれがないのはいい。
これだけの学びがあるのは企画の趣旨に照らして(そうでなくても)、すばらしい良問だったのでは？
