A1+A2+...+AN≤8888 があからさまな弱点なので、そのサイズの配列にそって処理を進めることにした。不可能なペアはビットフラグにしてカードごとにまとめた。88 ビットは微妙に大きなサイズだけど気にしない。8888 サイズの配列に組み合わせをたくわえていって、かぶりが出たら答え。88 個の組み合わせの総数が 2^{88}-1 なのでどうなるかと思ったが、通った。提出 #24083340 (AC / 213 ms / 同じ内容) 想定解は組み合わせにどんどんカードを足していく深さ優先探索だったのでちょっと違う。こちらは和が小さくなるものから順番に組み合わせを作っていったのだが、無駄が多かったかもしれない。■今日の１問は「089 - Partitions and Inversions（★7）」。典型知識の組み合わせだからとっかかりのない難しさというのではないが、脳がオーバーフローするややこしさなのがつらい。制約が緩かったら再帰でも配列ナメナメでも理解に沿った素直な実装ができるのだが、それが許されないせいでコードを変形して最後の５、６行に行き着くまで何時間もかかった。AC がすごく嬉しい。■しかし毎日 AC を(１つ)増やしてもラストスパートをかける人が増えているのか日々順位は下がっているのだ。くっそー。俺は凸包の点数はいらねーんだ。２点問題が TLE するからって他の言語を使ったりしねーんだ。……なんて考えでいるあたり、「くっそー」と言いつつ全然悔しくはなさそうである。■明日の１問は 9:00 から 19:00 のあいだに提出しないといけない。家を離れている時間とほぼ重なっているのと、スマホコーディングなんて考えられないオールドタイプなせいで、かなり厳しい。チャンスは２時間。★６★７なら見込み薄。■■■一日経ったので(89 問目)>提出 #24092271 (AC / 932 Byte / 805 ms)。驚いたことに想定解法である>ツイート。６つ７つの典型キーワードが列挙されてるけど、すごい人は意識せず当たり前にそれらの考えを適用しているから逆にキーワードが見えにくかったりするのではないか。そういうことが @evima さんおすすめの書『習得への情熱 ─チェスから武術へ─ 上達するための、僕の意識的学習法』に書いてあったよ。自分は意識して自分のものにすべき段階。■「コードを変形して最後の５、６行に行き着くまで何時間もかかった」 これはつまり、問題を解くのに方程式を解くようなやり方ができていないということ。どういうことか。変数を習う前の小学生は速さを求めるのに距離÷時間を、距離を求めるのに速さ×時間を、時間を求めるのに距離÷速さを考える必要があるけれど、中学で変数と方程式を習えばどれか１つの式に変数と値を割り当てて機械的な変形・展開で解ける。求める対象に変数という形を与えることで掛けたり割ったりの対象にできる。そういう強力な道具を与えられた中学生の方がある意味小学生より楽をしている。中学生になりたい。■最終結果。75/90 問、334/423 点でぴったり 200 位。★別集計>★2(8/10)、★3(20/20)、★4(14/14)、★5(14/17)、★6(12/14)、★7(7/15)。★7は部分点付きなので、なんらかの点を取ったものは 15/17 問であり、点数にすると 67/108 点。require'prime' して K.prime_division をこねくりまわす方針が良くなかった。提出 #24021051 (AC / 121 ms / 同じ内容)■ソースコード共有やツイートを見てると「ポリアの数え上げ定理」や「バーンサイドの(ではない)補題」といった異次元キーワードが目に入る。チョトナニイテルノカワカリマセン。■そして今日の問題「086 - Snuke's Favorite Arrays（★5）」も数え上げ。★５つでは足りないよ。でも ABC-E かというと(最近の ABC-E は緑でも水でもなくて青ときどき黄なので)それほどではない。518 バイトは書きすぎだと思うので無駄に難しくしてる可能性あり。■■■一日経ったので(86問目)>提出 #24040292 (AC / 518 Byte / 217 ms / 同じ内容)。てっきり掃き出し法のように干渉する条件をうまくまとめて数えるのだと思った(結局ビット列を列挙して条件列でテストにかけているあたり、自分がうまくやれているとも言えないが)。最終更新: 2021-07-14T01:38+0900
解説を読めば半分全列挙と同じように、汎用的な手法であるが故に問題から解法を見出そうとしても出てこないタイプの問題と解法だったと言えるのではないか。
以下は解説を読む前の提出。
クエリを先読みして頂点ごとに関連するクエリ番号をためておき、メインループは辺について繰り返すことにした。メインループの中ですることは辺が結ぶ２頂点が持つクエリ番号列のマージ。色の伝播を担うのが辺だということと、現在の色を決めるのは直近のクエリだということに着目した解法。
解説１にも書かれているように、これは特定の頂点に辺とクエリが集中したときに処理時間をオーバーする。とはいえこの提出のマージ部分は不必要に時間をかけている。２つのクエリ番号列の長さの和に比例した時間ではなく、二分探索を繰り返してもう少し(＜コレ)ましな時間にできる。その場合の TLE は(おそらく)４つ(random_challenge のうち２つと random_clique ２つ)>typical90_83_TLE4？.rb27。
この問題の悩みの種は、クエリに応じた色の変化を隣接ノードに「通知する」ことも、逆に隣接ノードに現在の色を「問い合わせる」ことも、制約から許されていないということ。
ここで、親にだけ通知してみるのはどうだろうと考えた。隣接ノードの数は N のオーダーになりかねないとしても、親であれば１つに決めていい。問題は親の決め方で、この問題のグラフは木ではない。
この提出ではノード番号が小さいものを親の側にあるとした。いきなり「親は１つ」ではなくなっているがしかたがない。だからこその TLE×8 なのだ。
所与のノード番号を利用するアイディアはお手軽に過ぎたので、今度はちょっと手間をかけて深さ優先探索で親子関係を決め、閉路が見つかったときに限り余分な親を追加することにした。残る TLE は５つ。
テストケースをダウンロードしたら、TLE になっているのは random_clique と名付けられた全２ケースと random_kill と名付けられた全３ケースの合計５ケースだった。自分の解法に弱点があり、そこを見事に狙い撃ちされたといったところか。定数倍の改善では全然間に合わない。
閉路が見つかったときにどちらをどちらの親にするかは好きに決めていい。親の数を比べて親の数が少ない方に他方を親として追加することにしたら、random_kill と名付けられた３ケースの TLE が解消した。
残るは random_clique が２ケース。random_kill が特定の１、２ノードに辺が集中していたのに対して、この２つのケースはまんべんなく多くの辺が伸びている。クエリに応答する負荷が全体的に底上げされていて逃げ場がない。
クエリの先読みをしたらメインループの前準備で探索のためのスタックがいらなくなった。クエリに関与しない頂点は無視していいし、入力された辺も片方向だけ記憶しておくのでいい。どちらをどちらの親にするかを決める
# P[v].size は親の数。Qn[v] はクエリで参照される回数 if P[a].size*Qn[a] < P[b].size*Qn[b]
という判定はメインループの負荷をよく反映していて気が利いてると思う。すべてクエリ先読みの効果。でもダメ(TLE)です。さっきの TLE×2 からはローカルで 12 秒が 7 秒になったけど、ならジャッジサーバーでは良くて 5 秒だろう。制限は 3 秒。
従来の日本語で「重複」と言うと「１つ以外は無駄」というニュアンスで使われることも多かったため知らないと混乱することがあるが(実際ゲーム関連サイトや攻略本などで逆の意味で使われることもあるようだ)、既にかなり定着しているのでそういうものと割り切るしかないだろう。誤解を招きたくない場合は「重複する」を「重ね掛けできる」等と言い替えることも出来る。」 つまり、「効果が重複する」とは「効果が１つ以外は無駄になる」という意味なんだけどゲーム用語では逆の意味になることも多いから「重ね掛けできる」と言い替えた方がいいかもね、と言っている。■ひとつ疑問があります。自分に言わせればトンデモな内容のスクリーンショット(文章)のソースが、検索では見つけられなかった。見つけたら是非、「重ね掛けできる」という用語をゲーム以外のどの界隈で使用するつもりなのか知りたかった。だってゲーム用語としての重複は(そして自分に言わせれば伝統的な日本語としての重複は)もう「
既にかなり定着しているのでそういうものと割り切るしかない」と書かれているのだ。誤解のおそれはない。なら誤解を避けるために「重ね掛けできる」と言い替えた方がいいのは、どの界隈の話なのか。俺はゲーム業界の中のさらに狭いジャンルの中で広まりつつある誤用だと思ってる。課金のように。■たぶんまとめ方が恣意的だっただけで、コメント欄が“そこそこ”まともなことに救いを感じてる。■あ、
ユースケースのコードをオブジェクトよりも上のレイヤーに取り出す、ということをやってみましょう。今、ユースケースのコードは、オブジェクトのクラスの中にあります。このユースケースの部分を、クラスの外側に出すのです。そうすると、オブジェクトの方は基本的なクラスのインスタンスのままなので、とても単純です。しかし、これらは実際のところユースケースの一部にはなりません。では、ユースケースの部品は何でしょうか？ ロールですね。ユースケースの部品は、ロールの中にあります。開発者は、このようなロールの中からいくつかを選んでまとめます。このまとまりを、コンテキストと呼びます。 つまり、コンテキストがユースケースに相当します。」■ゲームの造りにこれと似た構造があるという話。世界があってプレイヤーキャラクターがいて、プレイヤーははしごを登ったり椅子に座ったり運転席に乗り込んだりする。ゲームの造りとしての話だけど、プレイヤーが世界中のあらゆるオブジェクトに対してどう振る舞えばいいのか何が起こるのかを知っているのではなく、逆にインタラクティブオブジェクトの方がプレイヤーキャラクターの動きをプログラムして操っているのだとか。なんか似てない？
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 が多少冗長ではあるがコストの順に並んでいて総合的には得するだとか(少なくともローカルでは)。しかし、点を一列に並べて端っこから２番目の点を無き者にしてループの指数を１減らす試みは失敗した。