/ 最近 .rdf 追記 編集 設定 本棚

脳log[20210704] 競プロ典型 90 問/083 - Colorful Graph(★6)



2021年07月04日 (日) プレイ中。アルノサージュの世界はわかりやすい。巨乳は敵! 巨乳は敵! しかしイオンちゃんはそれなりに……。イオンちゃんは敵?(わかりやすくバカなのはお前だ)■アルノサージュは実質的にアルトネリコ4だと評するコメントがあった。アルトネリコの3は発売前から悪ノリが目に余って回避したが、1と2はプレイした。アルトネリコの1と2と4はおすすめできる。再発売される Legend of Mana の横に並べてもいい。特に1がおすすめです。あんなにプレイヤーをやきもきさせる心配なヒロインは初めてでした。■■■「「聖剣伝説 レジェンド オブ マナ」のHDリマスターを遊んだら軽く感情が暴走したので全力でお勧めする:今日書きたいことはこれくらい(1/2 ページ) - ねとらぼ」■■■「『聖剣伝説 レジェンド オブ マナ』HDリマスター版発売を機に、石井浩一氏&高井浩氏にインタビュー。オリジナル版開発秘話を訊く - ファミ通.com

最終更新: 2021-07-14T01:38+0900

[AtCoder] 競プロ典型 90 問/083 - Colorful Graph(★6)

たいへん厳しい。解説1解説2解説3解説4

解説を読めば半分全列挙と同じように、汎用的な手法であるが故に問題から解法を見出そうとしても出てこないタイプの問題と解法だったと言えるのではないか。

以下は解説を読む前の提出。

 提出 #23928493 (TLE×9 / 同じ内容) ※TLE×4 に改善できる

クエリを先読みして頂点ごとに関連するクエリ番号をためておき、メインループは辺について繰り返すことにした。メインループの中ですることは辺が結ぶ2頂点が持つクエリ番号列のマージ。色の伝播を担うのが辺だということと、現在の色を決めるのは直近のクエリだということに着目した解法。

解説1にも書かれているように、これは特定の頂点に辺とクエリが集中したときに処理時間をオーバーする。とはいえこの提出のマージ部分は不必要に時間をかけている。2つのクエリ番号列の長さの和に比例した時間ではなく、二分探索を繰り返してもう少し(<コレ)ましな時間にできる。その場合の TLE は(おそらく)4つ(random_challenge のうち2つと random_clique 2つ)>typical90_83_TLE4?.rb27

 提出 #23932276 (TLE×8 / 同じ内容)

この問題の悩みの種は、クエリに応じた色の変化を隣接ノードに「通知する」ことも、逆に隣接ノードに現在の色を「問い合わせる」ことも、制約から許されていないということ。

ここで、親にだけ通知してみるのはどうだろうと考えた。隣接ノードの数は N のオーダーになりかねないとしても、親であれば1つに決めていい。問題は親の決め方で、この問題のグラフは木ではない。

この提出ではノード番号が小さいものを親の側にあるとした。いきなり「親は1つ」ではなくなっているがしかたがない。だからこその TLE×8 なのだ。

 提出 #23933074 (TLE×5 / 同じ内容)

所与のノード番号を利用するアイディアはお手軽に過ぎたので、今度はちょっと手間をかけて深さ優先探索で親子関係を決め、閉路が見つかったときに限り余分な親を追加することにした。残る TLE は5つ。

テストケースをダウンロードしたら、TLE になっているのは random_clique と名付けられた全2ケースと random_kill と名付けられた全3ケースの合計5ケースだった。自分の解法に弱点があり、そこを見事に狙い撃ちされたといったところか。定数倍の改善では全然間に合わない。

 提出 #23996165 (TLE×2 / 同じ内容)

閉路が見つかったときにどちらをどちらの親にするかは好きに決めていい。親の数を比べて親の数が少ない方に他方を親として追加することにしたら、random_kill と名付けられた3ケースの TLE が解消した。

残るは random_clique が2ケース。random_kill が特定の1、2ノードに辺が集中していたのに対して、この2つのケースはまんべんなく多くの辺が伸びている。クエリに応答する負荷が全体的に底上げされていて逃げ場がない。

 提出 #24004617 (TLE×2 / 同じ内容)

クエリの先読みをしたらメインループの前準備で探索のためのスタックがいらなくなった。クエリに関与しない頂点は無視していいし、入力された辺も片方向だけ記憶しておくのでいい。どちらをどちらの親にするかを決める

# P[v].size は親の数。Qn[v] はクエリで参照される回数
if P[a].size*Qn[a] < P[b].size*Qn[b]

という判定はメインループの負荷をよく反映していて気が利いてると思う。すべてクエリ先読みの効果。でもダメ(TLE)です。さっきの TLE×2 からはローカルで 12 秒が 7 秒になったけど、ならジャッジサーバーでは良くて 5 秒だろう。制限は 3 秒。