脳log[20230814]

2023年08月14日 (月) [AtCoder] 精進１。昨日あった AGC064(不参加)-A「i i's」。最初は昇って降りる階段を作ればいいのかと思った。1234444332 みたいなのを。WA です。問題をよく読んでほしいんだけど、隣接項の差の絶対値は１か２でなければいけない。ゼロではいけない。せっかくなのでこの階段からスワップを繰り返して答えが作れないかと考えてみたがうまくできなかった。ステップ１。N=5 だとして 545454545 みたいにして５と４のノルマを消費したい。ステップ２。同じようにして 32323 を使って２と３のノルマを消費したいが、54...45 の隣に並べてしまうのは良くない。２個までなら並べられるけど、３回以上並べると第 L 項と第１項の差が４、６、８……と拡大し続けてしまう。５と４のあいだに埋め込むのが正解。１になるまで再帰的に埋め込みます。提出 #44571247 (AC / 461 Byte / 125 ms)。あ、また忘れてた。隣接２項の差がゼロではいけないから、両端が５ではいけないから、１回だけ横に並べたあとで再帰的に埋め込みをします。N が３以上なので必ず１度は横に並べられます。■■■精進２。同じ AGC064-B「Red and Blue Spanning Tree」。初手はひらめきです(初手でひらめいたということではなく、有効な初手をひらめくまであれこれ考えたという意味)。辺を３種類に分類した。すなわち、両端の頂点の色と辺の色が一致している辺、片方だけが一致している辺、両方ともが異なっている辺の３種類。両端が一致している辺はどんどん無条件に使用して良さそうな雰囲気がある。それから。大きさが２以上の連結成分に属する頂点についてはすでに条件を満足している。いまだ孤立している頂点をなんとかしたい。端点の片方だけ色が一致している辺を使ってなんとかしたい。その結果孤立頂点がなくなったなら、あとは使える辺をすべて使って全域木を構成する。もし孤立頂点が残ってしまったなら、答えは No。■WA×33、WA×8、WA×2、WA×21 のち AC。ステップ２で孤立頂点を解消する手順がずっとバグっていた。孤立頂点からすでに充足している大きな連結成分へと優先して辺を引っぱらなければいけなかった。まかり間違っても孤立頂点と孤立頂点を片方だけしか満足させられない辺で結んではいけない。■いやね、その場合でも孤立→孤立→大きな連結成分みたいにして最後に大きな連結成分に行き着くのなら問題がない。でも行き着かないケースもある。それが WA×2 の原因となった cycle と名のつくケースだと思う。手元で作った最小ケースはこんなの 4 4／1 2 R／4 3 B／4 1 B／3 4 R／RRRB。１と２の頂点は１番の辺で両方とも満足している。３番の頂点を満足させられるのは４番の辺だけ。４番の頂点を満足させられるのは２番と３番の辺だけど、２番の辺を使ってしまうと３番の頂点を満足させる方法がなくなってしまう。２番の辺と４番の辺は同じ２頂点を結んでいてそれぞれ異なる側を満足させる対称的な辺だけど、これに正しい優先順位を付けて使用しなければ答えを誤る。