2017の15日目の記事として書かれました。空いていたので放っておきます。最近、多忙で競技プログラミングの進捗が埋めていないのですが、取り敢えず2問。それぞれ出てきた2解法ずつ取り上げます。Drug問題概要N種類の薬品を可能な限り混ぜます。M組同時に混ぜてはいけないリストが存在するので、その中で何種類まで混ぜられるか答えてください。AtCoder半分全列挙とか浮かびましたが、上手く組み合わせる方法が思いつかずに死亡しました。コンテスト中はこれはさっさと諦めましたね...解法1取り敢えず枝刈り解。結局はただの最大独立集合なので、指数時間アルゴリズム入門を読むと解法が降ってきます。longの中でビット操作で殴ります。実際の実装で辺を落としたりするのはナンセンスだと思ったので、用いた枝刈りは次数が1以下の頂点は選んでよい(ただし、2頂点からなる木があると死ぬので注意)選ぶ際に周りに選んだ頂点があってはならない(これは、初めにNGリストなるものを作っておき、現在の情報とandを取って確認します)残りの頂点全部を選んでも現在の最適解に届かないなら探索を打ち切るの3つです。Studioを使う人なので、当然__builtin_popcountが使えず、折角なので実装しました。いわれると、ナップザックがイメージできて、左右両側を全パターン列挙して、それを上手くまとめるイメージです。今回は初見のまとめかたでしたね...後半半分は全列挙します。後半部の各パターンに対し、前半部で取れる最大集合(=後半部選ばれた頂点に隣接しないものの中での最大集合)というのが存在します。解法1のNGリストを反転して利用すると一瞬で求まります。前半部に対して「その集合の中で何頂点まで選べるか」というbitDPを用いると、「後半部の選んだ頂点数」+「前半部で選べる最大値」が最大値です。これを後半部全パターンに対して行うことで答えが得られます。bitDPで各パターンについて、1となっているビット1つを0にしたものから遷移していくので、O(n2n/2)というのが時間計算量です。2n/2)であることがTSG内のプロによって指摘されました。Findでくっつけていくのですが、2頂点を指定したQ個のクエリに対して「何回目の操作でその2頂点がくっついたか」を答えてください。AtCoderLCAが浮かんで、2iだけ遡って何とか出来ないかな...なんて考えていたけど、辺に重みを付けるなんて発想もなく、各頂点・各時間についてその際のグループを把握してなきゃ出来ない気がして時間切れでした。辺をつなげる際に「既にその2頂点がくっついているならその辺は追加しない」というルールを加えると、必ず森(閉路が無い)になります。Findを考える上でも不要です。これでLCAが使えます。辺に何回目の操作であるか、という重みをつけてあげると、(x,y)というクエリに対してv=LCA(x,y)の時、パスx->v->yの辺の最大値が答えです。このままでは計算量は落ちません。これは、LCAの先祖を覚える配列の持ち方を流用して「頂点iから2j頂点分上に行く際に通る辺のうち、最大の重み」を記録しておくと、x,yを変えながら上っていく際に情報を落とさずに拾えます。AtCoder解法2これは「なんか面白い解法無いかなー」と探していたら案の定プロがいたので掲載。blogにぶたんを行うことで各クエリに対してO(MlogM)で解くことが出来ます。毎回のシミュレーションで確認するのは1箇所のみでもったいないので、全クエリを並列で行うと、1回のシミュレーションがO(M+Q)で終了するので、セッティング含めてO((N+M+Q)logM)で終わります。...「3月中に毎日1問解いて黄色になろう!」キャンペーン11問目。040久々の更新です。049WAするんじゃないかとヒヤヒヤしながらの提出だった...3完。日)ネットの海に生息するらしいバーチャルグソクムシ。競プロとCTFをメインに、たまにEsolangを混ぜます。(7)月別アーカイブリンクGitHubはてなブログをはじめよう!Hyogaさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。