Jekyll2021-10-28T08:23:34+00:00https://justicehui.github.io/rss/JusticeHui가 PS하는 블로그Let's solve problem with JusticeHui!JusticeHui백준16992 3-SAT2021-09-23T13:26:00+00:002021-09-23T13:26:00+00:00https://justicehui.github.io/ps/2021/09/23/BOJ16992<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/16992</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>Simulated Annealing</li> </ul> <h3 id="풀이">풀이</h3> <p>3-SAT 문제는 NP-Complete에 속하므로 다항 시간 안에 해결하는 알고리즘이 알려져 있지 않습니다. 적절한 휴리스틱을 이용해 문제를 풀어봅시다.</p> <p>제 풀이는 기본적으로 Simulated Annealing을 사용합니다. SA에 대한 설명은 계절학교와 구글 해시코드에서 놀라운 휴리스틱 실력을 보여주었던 Ryute님의 설명으로 대신합니다.</p> <ul> <li><a href="https://ryute.tistory.com/35">PS: 뉴비를 위한 Simulated Annealing 입문 (1)</a></li> <li><a href="https://ryute.tistory.com/36">PS: 뉴비를 위한 Simulated Annealing 입문 (2)</a></li> </ul> <p>제가 처음 시도한 풀이는 다음과 같습니다.</p> <ol> <li>$N, M$이 매우 작으면($M\cdot2^N \leq 3\cdot10^8$정도?) Bruteforcing으로 답을 찾는다.</li> <li>최대한 다양한 상수(랜덤 시드, 볼츠만 상수, 초기 온도, 온도 변화율, 상태 전이 개수 등)를 이용해 Simulated Annealing을 시도한다.</li> <li>맞은 테스트케이스의 합집합이 최대한 많은 부분을 커버하도록 코드를 잘 조합한다.</li> </ol> <p>(3)은 이 문제가 BOJ에서 전체 채점 문제이고 채점 순서가 고정되어 있기 때문에 가능합니다. (3)을 실현하기 위해서는 똑같은 결과를 재현할 수 있어야 하므로, 모든 랜덤 시드는 손으로 직접 입력해야 합니다.</p> <p>여기까지 오면 19x점 정도를 얻을 수 있습니다. 초기 상태를 모두 false으로 지정해서 그런지 성능이 별로 안 좋았습니다. 그래서 초기 상태를 지정하는 것도 여러 가지 방법을 시도해 보았습니다.</p> <ul> <li>모두 false으로 초기화 (<code class="language-plaintext highlighter-rouge">ZeroInitializer</code>)</li> <li>랜덤으로 초기화 (<code class="language-plaintext highlighter-rouge">RandomInitializer</code>)</li> <li>clause에 true로 등장하는 횟수가 많으면 true, false로 등장하는 횟수가 더 많으면 false로 초기화 (<code class="language-plaintext highlighter-rouge">StrangeInitializer</code>)</li> </ul> <p>여러 초기화 전략을 시도하니 200 ~ 203점을 받게 되었습니다. 여기까지 작성한 코드는 다음과 같습니다. 앞서 말한 것처럼, 실행 결과를 재현할 수 있도록 랜덤 시드를 직접 파라미터로 넘깁니다.</p> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cm">/** * SimulatedAnnealing * @param n : number of variables * @param cl : clauses list * @param init : initial state * @param k : Boltzmann constant * @param t : initial temperature * @param delta : delta temperature * @param epoch : number of iterations * @param select : number of changes at one iteration * @param seed : random seed * @return : true if SA find the answer */</span> <span class="kt">bool</span> <span class="nf">SimulatedAnnealing</span><span class="p">(</span><span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="k">const</span> <span class="n">clauses</span> <span class="o">&amp;</span><span class="n">cl</span><span class="p">,</span> <span class="n">State</span> <span class="n">init</span><span class="p">,</span> <span class="kt">double</span> <span class="n">k</span><span class="p">,</span> <span class="kt">double</span> <span class="n">t</span><span class="p">,</span> <span class="kt">double</span> <span class="n">delta</span><span class="p">,</span> <span class="kt">int</span> <span class="n">epoch</span><span class="p">,</span> <span class="kt">int</span> <span class="n">select</span><span class="o">=</span><span class="mi">1</span><span class="p">,</span> <span class="kt">int</span> <span class="n">seed</span><span class="o">=</span><span class="mh">0x917917</span><span class="p">){</span> <span class="n">State</span> <span class="n">now</span> <span class="o">=</span> <span class="n">init</span><span class="p">;</span> <span class="kt">int</span> <span class="n">score</span> <span class="o">=</span> <span class="n">now</span><span class="p">.</span><span class="n">score</span><span class="p">(</span><span class="n">cl</span><span class="p">);</span> <span class="n">Random</span> <span class="n">rnd</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="n">seed</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">iter</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">iter</span><span class="o">&lt;</span><span class="n">epoch</span><span class="p">;</span> <span class="n">iter</span><span class="o">++</span><span class="p">){</span> <span class="n">State</span> <span class="n">nxt</span> <span class="o">=</span> <span class="n">now</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;</span><span class="n">select</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="n">nxt</span><span class="p">.</span><span class="n">flip</span><span class="p">(</span><span class="n">rnd</span><span class="p">);</span> <span class="kt">int</span> <span class="n">nxtScore</span> <span class="o">=</span> <span class="n">nxt</span><span class="p">.</span><span class="n">score</span><span class="p">(</span><span class="n">cl</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">exp</span><span class="p">((</span><span class="kt">double</span><span class="p">)(</span><span class="n">nxtScore</span> <span class="o">-</span> <span class="n">score</span><span class="p">)</span> <span class="o">/</span> <span class="p">(</span><span class="n">k</span> <span class="o">*</span> <span class="n">t</span><span class="p">))</span> <span class="o">&gt;</span> <span class="n">rnd</span><span class="p">.</span><span class="n">next</span><span class="p">()){</span> <span class="n">now</span> <span class="o">=</span> <span class="n">nxt</span><span class="p">;</span> <span class="n">score</span> <span class="o">=</span> <span class="n">nxtScore</span><span class="p">;</span> <span class="p">}</span> <span class="k">if</span><span class="p">(</span><span class="n">score</span> <span class="o">==</span> <span class="n">cl</span><span class="p">.</span><span class="n">size</span><span class="p">()){</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="s">"1</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span> <span class="n">now</span><span class="p">.</span><span class="n">print</span><span class="p">(</span><span class="n">n</span><span class="p">);</span> <span class="k">return</span> <span class="nb">true</span><span class="p">;</span> <span class="p">}</span> <span class="n">t</span> <span class="o">*=</span> <span class="n">delta</span><span class="p">;</span> <span class="p">}</span> <span class="k">return</span> <span class="nb">false</span><span class="p">;</span> <span class="p">}</span> <span class="c1">// 중략</span> <span class="n">Random</span> <span class="nf">R</span><span class="p">(</span><span class="mh">0x917917</span><span class="p">);</span> <span class="c1">// Random Manager class using mt19937</span> <span class="k">if</span><span class="p">(</span><span class="n">SimulatedAnnealing</span><span class="p">(</span><span class="n">N</span><span class="p">,</span> <span class="n">C</span><span class="p">,</span> <span class="n">ZeroInitializer</span><span class="p">(</span><span class="n">N</span><span class="p">)</span> <span class="p">,</span> <span class="mf">1.5</span><span class="p">,</span> <span class="mf">1.0</span><span class="p">,</span> <span class="mf">0.9999</span><span class="p">,</span> <span class="mi">50505</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mh">0x482794</span><span class="p">))</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">SimulatedAnnealing</span><span class="p">(</span><span class="n">N</span><span class="p">,</span> <span class="n">C</span><span class="p">,</span> <span class="n">ZeroInitializer</span><span class="p">(</span><span class="n">N</span><span class="p">)</span> <span class="p">,</span> <span class="mf">1.5</span><span class="p">,</span> <span class="mf">1.0</span><span class="p">,</span> <span class="mf">0.9999</span><span class="p">,</span> <span class="mi">50505</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mh">0x917917</span><span class="p">))</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">SimulatedAnnealing</span><span class="p">(</span><span class="n">N</span><span class="p">,</span> <span class="n">C</span><span class="p">,</span> <span class="n">ZeroInitializer</span><span class="p">(</span><span class="n">N</span><span class="p">)</span> <span class="p">,</span> <span class="mf">2.5</span><span class="p">,</span> <span class="mf">1.0</span><span class="p">,</span> <span class="mf">0.9999</span><span class="p">,</span> <span class="mi">50505</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mh">0x482794</span><span class="p">))</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">SimulatedAnnealing</span><span class="p">(</span><span class="n">N</span><span class="p">,</span> <span class="n">C</span><span class="p">,</span> <span class="n">ZeroInitializer</span><span class="p">(</span><span class="n">N</span><span class="p">)</span> <span class="p">,</span> <span class="mf">1.5</span><span class="p">,</span> <span class="mf">1.0</span><span class="p">,</span> <span class="mf">0.9999</span><span class="p">,</span> <span class="mi">50505</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mh">0x917917</span><span class="p">))</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">SimulatedAnnealing</span><span class="p">(</span><span class="n">N</span><span class="p">,</span> <span class="n">C</span><span class="p">,</span> <span class="n">ZeroInitializer</span><span class="p">(</span><span class="n">N</span><span class="p">)</span> <span class="p">,</span> <span class="mf">1.5</span><span class="p">,</span> <span class="mf">1.0</span><span class="p">,</span> <span class="mf">0.9995</span><span class="p">,</span> <span class="mi">50505</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mh">0x917917</span><span class="p">))</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">SimulatedAnnealing</span><span class="p">(</span><span class="n">N</span><span class="p">,</span> <span class="n">C</span><span class="p">,</span> <span class="n">RandomInitializer</span><span class="p">(</span><span class="n">N</span><span class="p">,</span> <span class="n">R</span><span class="p">)</span> <span class="p">,</span> <span class="mf">1.5</span><span class="p">,</span> <span class="mf">5.0</span><span class="p">,</span> <span class="mf">0.9999</span><span class="p">,</span> <span class="mi">50505</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mh">0x917917</span><span class="p">))</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">SimulatedAnnealing</span><span class="p">(</span><span class="n">N</span><span class="p">,</span> <span class="n">C</span><span class="p">,</span> <span class="n">RandomInitializer</span><span class="p">(</span><span class="n">N</span><span class="p">,</span> <span class="n">R</span><span class="p">)</span> <span class="p">,</span> <span class="mf">1.5</span><span class="p">,</span> <span class="mf">5.0</span><span class="p">,</span> <span class="mf">0.9995</span><span class="p">,</span> <span class="mi">50505</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mh">0x917917</span><span class="p">))</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">SimulatedAnnealing</span><span class="p">(</span><span class="n">N</span><span class="p">,</span> <span class="n">C</span><span class="p">,</span> <span class="n">StrangeInitializer</span><span class="p">(</span><span class="n">N</span><span class="p">,</span> <span class="n">C</span><span class="p">),</span> <span class="mf">1.0</span><span class="p">,</span> <span class="mf">1.5</span><span class="p">,</span> <span class="mf">0.9999</span><span class="p">,</span> <span class="mi">50505</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mh">0x917917</span><span class="p">))</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> </code></pre></div></div> <p>여기까지 오면 보통 28, 41, 128번 테스트케이스 같은 곳에서 한 두 개 정도 틀릴텐데, 이런 부분을 직접 잡는 것은 너무 힘들어서 랜덤을 믿기로 했습니다.<br /><code class="language-plaintext highlighter-rouge">RandomInitializer</code>를 이용해 초기화를 한 뒤, 처음으로 false가 되는 clause에 관여하는 변수 하나를 뒤집는 연산(<code class="language-plaintext highlighter-rouge">flipHeuristic</code>)을 100번 정도 수행하는 것을 시간 제한이 끝나기 직전까지 반복합니다.</p> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="kt">bool</span> <span class="nf">RandomSearch</span><span class="p">(</span><span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="k">const</span> <span class="n">clauses</span> <span class="o">&amp;</span><span class="n">cl</span><span class="p">,</span> <span class="kt">int</span> <span class="n">select</span><span class="p">,</span> <span class="kt">double</span> <span class="n">tl</span><span class="p">,</span> <span class="kt">int</span> <span class="n">seed</span><span class="o">=</span><span class="mh">0x917917</span><span class="p">){</span> <span class="n">Random</span> <span class="n">rnd</span><span class="p">(</span><span class="n">seed</span><span class="p">);</span> <span class="k">while</span><span class="p">(</span><span class="n">clock</span><span class="p">()</span> <span class="o">&lt;</span> <span class="n">tl</span> <span class="o">*</span> <span class="n">CLOCKS_PER_SEC</span><span class="p">){</span> <span class="n">State</span> <span class="n">now</span> <span class="o">=</span> <span class="n">RandomInitializer</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="n">rnd</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">select</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">now</span><span class="p">.</span><span class="n">flipHeuristic</span><span class="p">(</span><span class="n">rnd</span><span class="p">,</span> <span class="n">cl</span><span class="p">)){</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="s">"1</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span> <span class="n">now</span><span class="p">.</span><span class="n">print</span><span class="p">(</span><span class="n">n</span><span class="p">);</span> <span class="k">return</span> <span class="nb">true</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> <span class="p">}</span> <span class="k">return</span> <span class="nb">false</span><span class="p">;</span> <span class="p">}</span> <span class="c1">// 중략</span> <span class="k">if</span><span class="p">(</span><span class="n">RandomSearch</span><span class="p">(</span><span class="n">N</span><span class="p">,</span> <span class="n">C</span><span class="p">,</span> <span class="mi">100</span><span class="p">,</span> <span class="mf">1.5</span><span class="p">,</span> <span class="mh">0x814814</span><span class="p">))</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> </code></pre></div></div> <p><code class="language-plaintext highlighter-rouge">RandomSearch</code>까지 추가했더니 204개의 테스트케이스를 모두 맞을 수 있었습니다.</p> <p>아래 코드는 랜덤 시드가 고정되어있기 때문에, 그대로 제출하면 글을 업로드한 2021년 9월 기준으로 모든 테스트케이스에 대해 올바른 답을 낼 수 있음이 보장됩니다.</p> <h3 id="전체-코드">전체 코드</h3> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">using</span> <span class="n">clause</span> <span class="o">=</span> <span class="n">array</span><span class="o">&lt;</span><span class="kt">int</span><span class="p">,</span><span class="mi">3</span><span class="o">&gt;</span><span class="p">;</span> <span class="k">using</span> <span class="n">clauses</span> <span class="o">=</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">clause</span><span class="o">&gt;</span><span class="p">;</span> <span class="k">struct</span> <span class="nc">Random</span><span class="p">{</span> <span class="n">mt19937</span> <span class="n">gen</span><span class="p">;</span> <span class="n">uniform_int_distribution</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">rnd_int</span><span class="p">;</span> <span class="n">uniform_real_distribution</span><span class="o">&lt;</span><span class="kt">double</span><span class="o">&gt;</span> <span class="n">rnd_real</span><span class="p">;</span> <span class="n">Random</span><span class="p">(</span><span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="kt">int</span> <span class="n">seed</span><span class="o">=</span><span class="mh">0x917917</span><span class="p">)</span> <span class="o">:</span> <span class="n">gen</span><span class="p">(</span><span class="n">seed</span><span class="p">),</span> <span class="n">rnd_int</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="n">n</span><span class="p">),</span> <span class="n">rnd_real</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">1</span><span class="p">)</span> <span class="p">{}</span> <span class="kt">int</span> <span class="n">nextInt</span><span class="p">(){</span> <span class="k">return</span> <span class="n">rnd_int</span><span class="p">(</span><span class="n">gen</span><span class="p">);</span> <span class="p">}</span> <span class="kt">double</span> <span class="n">next</span><span class="p">(){</span> <span class="k">return</span> <span class="n">rnd_real</span><span class="p">(</span><span class="n">gen</span><span class="p">);</span> <span class="p">}</span> <span class="p">};</span> <span class="k">struct</span> <span class="nc">State</span><span class="p">{</span> <span class="n">array</span><span class="o">&lt;</span><span class="kt">int</span><span class="p">,</span> <span class="mi">111</span><span class="o">&gt;</span> <span class="n">a</span><span class="p">;</span> <span class="kt">int</span><span class="o">&amp;</span> <span class="k">operator</span> <span class="p">[]</span> <span class="p">(</span><span class="kt">int</span> <span class="n">idx</span><span class="p">)</span> <span class="p">{</span> <span class="k">return</span> <span class="n">a</span><span class="p">[</span><span class="n">idx</span><span class="p">];</span> <span class="p">}</span> <span class="kt">void</span> <span class="n">flip</span><span class="p">(</span><span class="n">Random</span> <span class="o">&amp;</span><span class="n">rnd</span><span class="p">){</span> <span class="n">a</span><span class="p">[</span><span class="n">rnd</span><span class="p">.</span><span class="n">nextInt</span><span class="p">()]</span> <span class="o">^=</span> <span class="mi">1</span><span class="p">;</span> <span class="p">}</span> <span class="kt">bool</span> <span class="n">flipHeuristic</span><span class="p">(</span><span class="n">Random</span> <span class="o">&amp;</span><span class="n">rnd</span><span class="p">,</span> <span class="k">const</span> <span class="n">clauses</span> <span class="o">&amp;</span><span class="n">cl</span><span class="p">){</span> <span class="k">for</span><span class="p">(</span><span class="k">const</span> <span class="k">auto</span> <span class="o">&amp;</span><span class="p">[</span><span class="n">x</span><span class="p">,</span><span class="n">y</span><span class="p">,</span><span class="n">z</span><span class="p">]</span> <span class="o">:</span> <span class="n">cl</span><span class="p">){</span> <span class="kt">bool</span> <span class="n">now</span> <span class="o">=</span> <span class="nb">false</span><span class="p">;</span> <span class="n">now</span> <span class="o">|=</span> <span class="n">x</span> <span class="o">&gt;</span> <span class="mi">0</span> <span class="o">?</span> <span class="n">a</span><span class="p">[</span><span class="n">x</span><span class="p">]</span> <span class="o">:</span> <span class="o">!</span><span class="n">a</span><span class="p">[</span><span class="o">-</span><span class="n">x</span><span class="p">];</span> <span class="n">now</span> <span class="o">|=</span> <span class="n">y</span> <span class="o">&gt;</span> <span class="mi">0</span> <span class="o">?</span> <span class="n">a</span><span class="p">[</span><span class="n">y</span><span class="p">]</span> <span class="o">:</span> <span class="o">!</span><span class="n">a</span><span class="p">[</span><span class="o">-</span><span class="n">y</span><span class="p">];</span> <span class="n">now</span> <span class="o">|=</span> <span class="n">z</span> <span class="o">&gt;</span> <span class="mi">0</span> <span class="o">?</span> <span class="n">a</span><span class="p">[</span><span class="n">z</span><span class="p">]</span> <span class="o">:</span> <span class="o">!</span><span class="n">a</span><span class="p">[</span><span class="o">-</span><span class="n">z</span><span class="p">];</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">now</span><span class="p">){</span> <span class="kt">int</span> <span class="n">select</span> <span class="o">=</span> <span class="n">rnd</span><span class="p">.</span><span class="n">gen</span><span class="p">()</span> <span class="o">%</span> <span class="mi">3</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">select</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="n">a</span><span class="p">[</span><span class="n">abs</span><span class="p">(</span><span class="n">x</span><span class="p">)]</span> <span class="o">^=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">select</span> <span class="o">==</span> <span class="mi">1</span><span class="p">)</span> <span class="n">a</span><span class="p">[</span><span class="n">abs</span><span class="p">(</span><span class="n">y</span><span class="p">)]</span> <span class="o">^=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">select</span> <span class="o">==</span> <span class="mi">2</span><span class="p">)</span> <span class="n">a</span><span class="p">[</span><span class="n">abs</span><span class="p">(</span><span class="n">z</span><span class="p">)]</span> <span class="o">^=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">return</span> <span class="nb">false</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> <span class="k">return</span> <span class="nb">true</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">score</span><span class="p">(</span><span class="k">const</span> <span class="n">clauses</span> <span class="o">&amp;</span><span class="n">cl</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span> <span class="kt">int</span> <span class="n">ret</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="k">const</span> <span class="k">auto</span> <span class="o">&amp;</span><span class="p">[</span><span class="n">x</span><span class="p">,</span><span class="n">y</span><span class="p">,</span><span class="n">z</span><span class="p">]</span> <span class="o">:</span> <span class="n">cl</span><span class="p">){</span> <span class="kt">bool</span> <span class="n">now</span> <span class="o">=</span> <span class="nb">false</span><span class="p">;</span> <span class="n">now</span> <span class="o">|=</span> <span class="n">x</span> <span class="o">&gt;</span> <span class="mi">0</span> <span class="o">?</span> <span class="n">a</span><span class="p">[</span><span class="n">x</span><span class="p">]</span> <span class="o">:</span> <span class="o">!</span><span class="n">a</span><span class="p">[</span><span class="o">-</span><span class="n">x</span><span class="p">];</span> <span class="n">now</span> <span class="o">|=</span> <span class="n">y</span> <span class="o">&gt;</span> <span class="mi">0</span> <span class="o">?</span> <span class="n">a</span><span class="p">[</span><span class="n">y</span><span class="p">]</span> <span class="o">:</span> <span class="o">!</span><span class="n">a</span><span class="p">[</span><span class="o">-</span><span class="n">y</span><span class="p">];</span> <span class="n">now</span> <span class="o">|=</span> <span class="n">z</span> <span class="o">&gt;</span> <span class="mi">0</span> <span class="o">?</span> <span class="n">a</span><span class="p">[</span><span class="n">z</span><span class="p">]</span> <span class="o">:</span> <span class="o">!</span><span class="n">a</span><span class="p">[</span><span class="o">-</span><span class="n">z</span><span class="p">];</span> <span class="n">ret</span> <span class="o">+=</span> <span class="n">now</span><span class="p">;</span> <span class="p">}</span> <span class="k">return</span> <span class="n">ret</span><span class="p">;</span> <span class="p">}</span> <span class="kt">void</span> <span class="n">print</span><span class="p">(</span><span class="kt">int</span> <span class="n">n</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&lt;&lt;</span> <span class="s">" </span><span class="se">\n</span><span class="s">"</span><span class="p">[</span><span class="n">i</span><span class="o">==</span><span class="n">n</span><span class="p">];</span> <span class="p">}</span> <span class="p">};</span> <span class="n">State</span> <span class="nf">ZeroInitializer</span><span class="p">(</span><span class="kt">int</span> <span class="n">n</span><span class="p">){</span> <span class="n">State</span> <span class="n">ret</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">ret</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">return</span> <span class="n">ret</span><span class="p">;</span> <span class="p">}</span> <span class="n">State</span> <span class="nf">RandomInitializer</span><span class="p">(</span><span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="n">Random</span> <span class="o">&amp;</span><span class="n">rnd</span><span class="p">){</span> <span class="n">State</span> <span class="n">ret</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">ret</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">rnd</span><span class="p">.</span><span class="n">gen</span><span class="p">()</span> <span class="o">&amp;</span> <span class="mi">1</span><span class="p">;</span> <span class="k">return</span> <span class="n">ret</span><span class="p">;</span> <span class="p">}</span> <span class="n">State</span> <span class="nf">StrangeInitializer</span><span class="p">(</span><span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="k">const</span> <span class="n">clauses</span> <span class="o">&amp;</span><span class="n">cl</span><span class="p">){</span> <span class="n">State</span> <span class="n">ret</span><span class="p">;</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">sum</span><span class="p">(</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="k">const</span> <span class="k">auto</span> <span class="o">&amp;</span><span class="n">arr</span> <span class="o">:</span> <span class="n">cl</span><span class="p">){</span> <span class="k">for</span><span class="p">(</span><span class="k">const</span> <span class="k">auto</span> <span class="o">&amp;</span><span class="n">j</span> <span class="o">:</span> <span class="n">arr</span><span class="p">)</span> <span class="n">sum</span><span class="p">[</span><span class="n">abs</span><span class="p">(</span><span class="n">j</span><span class="p">)]</span> <span class="o">+=</span> <span class="n">j</span><span class="p">;</span> <span class="p">}</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">ret</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">sum</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">;</span> <span class="k">return</span> <span class="n">ret</span><span class="p">;</span> <span class="p">}</span> <span class="kt">void</span> <span class="nf">Naive</span><span class="p">(</span><span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="k">const</span> <span class="n">clauses</span> <span class="o">&amp;</span><span class="n">cl</span><span class="p">){</span> <span class="n">State</span> <span class="n">state</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="p">(</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="n">n</span><span class="p">);</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="n">state</span><span class="p">[</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="p">(</span><span class="n">i</span> <span class="o">&amp;</span> <span class="p">(</span><span class="mi">1</span> <span class="o">&lt;&lt;</span> <span class="n">j</span><span class="p">))</span> <span class="o">!=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">state</span><span class="p">.</span><span class="n">score</span><span class="p">(</span><span class="n">cl</span><span class="p">)</span> <span class="o">==</span> <span class="n">cl</span><span class="p">.</span><span class="n">size</span><span class="p">()){</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="s">"1</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span> <span class="n">state</span><span class="p">.</span><span class="n">print</span><span class="p">(</span><span class="n">n</span><span class="p">);</span> <span class="k">return</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="s">"0</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span> <span class="p">}</span> <span class="kt">bool</span> <span class="nf">SimulatedAnnealing</span><span class="p">(</span><span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="k">const</span> <span class="n">clauses</span> <span class="o">&amp;</span><span class="n">cl</span><span class="p">,</span> <span class="n">State</span> <span class="n">init</span><span class="p">,</span> <span class="kt">double</span> <span class="n">k</span><span class="p">,</span> <span class="kt">double</span> <span class="n">t</span><span class="p">,</span> <span class="kt">double</span> <span class="n">delta</span><span class="p">,</span> <span class="kt">int</span> <span class="n">epoch</span><span class="p">,</span> <span class="kt">int</span> <span class="n">select</span><span class="o">=</span><span class="mi">1</span><span class="p">,</span> <span class="kt">int</span> <span class="n">seed</span><span class="o">=</span><span class="mh">0x917917</span><span class="p">){</span> <span class="n">State</span> <span class="n">now</span> <span class="o">=</span> <span class="n">init</span><span class="p">;</span> <span class="kt">int</span> <span class="n">score</span> <span class="o">=</span> <span class="n">now</span><span class="p">.</span><span class="n">score</span><span class="p">(</span><span class="n">cl</span><span class="p">);</span> <span class="n">Random</span> <span class="n">rnd</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="n">seed</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">iter</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">iter</span><span class="o">&lt;</span><span class="n">epoch</span><span class="p">;</span> <span class="n">iter</span><span class="o">++</span><span class="p">){</span> <span class="n">State</span> <span class="n">nxt</span> <span class="o">=</span> <span class="n">now</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;</span><span class="n">select</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="n">nxt</span><span class="p">.</span><span class="n">flip</span><span class="p">(</span><span class="n">rnd</span><span class="p">);</span> <span class="kt">int</span> <span class="n">nxtScore</span> <span class="o">=</span> <span class="n">nxt</span><span class="p">.</span><span class="n">score</span><span class="p">(</span><span class="n">cl</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">exp</span><span class="p">((</span><span class="kt">double</span><span class="p">)(</span><span class="n">nxtScore</span> <span class="o">-</span> <span class="n">score</span><span class="p">)</span> <span class="o">/</span> <span class="p">(</span><span class="n">k</span> <span class="o">*</span> <span class="n">t</span><span class="p">))</span> <span class="o">&gt;</span> <span class="n">rnd</span><span class="p">.</span><span class="n">next</span><span class="p">()){</span> <span class="n">now</span> <span class="o">=</span> <span class="n">nxt</span><span class="p">;</span> <span class="n">score</span> <span class="o">=</span> <span class="n">nxtScore</span><span class="p">;</span> <span class="p">}</span> <span class="k">if</span><span class="p">(</span><span class="n">score</span> <span class="o">==</span> <span class="n">cl</span><span class="p">.</span><span class="n">size</span><span class="p">()){</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="s">"1</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span> <span class="n">now</span><span class="p">.</span><span class="n">print</span><span class="p">(</span><span class="n">n</span><span class="p">);</span> <span class="k">return</span> <span class="nb">true</span><span class="p">;</span> <span class="p">}</span> <span class="n">t</span> <span class="o">*=</span> <span class="n">delta</span><span class="p">;</span> <span class="p">}</span> <span class="k">return</span> <span class="nb">false</span><span class="p">;</span> <span class="p">}</span> <span class="kt">bool</span> <span class="nf">RandomSearch</span><span class="p">(</span><span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="k">const</span> <span class="n">clauses</span> <span class="o">&amp;</span><span class="n">cl</span><span class="p">,</span> <span class="kt">int</span> <span class="n">select</span><span class="p">,</span> <span class="kt">double</span> <span class="n">tl</span><span class="p">,</span> <span class="kt">int</span> <span class="n">seed</span><span class="o">=</span><span class="mh">0x917917</span><span class="p">){</span> <span class="n">Random</span> <span class="n">rnd</span><span class="p">(</span><span class="n">seed</span><span class="p">);</span> <span class="k">while</span><span class="p">(</span><span class="n">clock</span><span class="p">()</span> <span class="o">&lt;</span> <span class="n">tl</span> <span class="o">*</span> <span class="n">CLOCKS_PER_SEC</span><span class="p">){</span> <span class="n">State</span> <span class="n">now</span> <span class="o">=</span> <span class="n">RandomInitializer</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="n">rnd</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">select</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">now</span><span class="p">.</span><span class="n">flipHeuristic</span><span class="p">(</span><span class="n">rnd</span><span class="p">,</span> <span class="n">cl</span><span class="p">)){</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="s">"1</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span> <span class="n">now</span><span class="p">.</span><span class="n">print</span><span class="p">(</span><span class="n">n</span><span class="p">);</span> <span class="k">return</span> <span class="nb">true</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> <span class="p">}</span> <span class="k">return</span> <span class="nb">false</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="kt">int</span> <span class="n">N</span><span class="p">,</span> <span class="n">M</span><span class="p">;</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">N</span> <span class="o">&gt;&gt;</span> <span class="n">M</span><span class="p">;</span> <span class="n">clauses</span> <span class="n">C</span><span class="p">(</span><span class="n">M</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="o">&amp;</span><span class="p">[</span><span class="n">x</span><span class="p">,</span><span class="n">y</span><span class="p">,</span><span class="n">z</span><span class="p">]</span> <span class="o">:</span> <span class="n">C</span><span class="p">)</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">x</span> <span class="o">&gt;&gt;</span> <span class="n">y</span> <span class="o">&gt;&gt;</span> <span class="n">z</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">N</span> <span class="o">&lt;=</span> <span class="mi">20</span> <span class="o">&amp;&amp;</span> <span class="p">(</span><span class="n">M</span> <span class="o">&lt;&lt;</span> <span class="n">N</span><span class="p">)</span> <span class="o">&lt;=</span> <span class="mf">3e8</span><span class="p">){</span> <span class="n">Naive</span><span class="p">(</span><span class="n">N</span><span class="p">,</span> <span class="n">C</span><span class="p">);</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="p">}</span> <span class="n">Random</span> <span class="n">R</span><span class="p">(</span><span class="mh">0x917917</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">SimulatedAnnealing</span><span class="p">(</span><span class="n">N</span><span class="p">,</span> <span class="n">C</span><span class="p">,</span> <span class="n">ZeroInitializer</span><span class="p">(</span><span class="n">N</span><span class="p">)</span> <span class="p">,</span> <span class="mf">1.5</span><span class="p">,</span> <span class="mf">1.0</span><span class="p">,</span> <span class="mf">0.9999</span><span class="p">,</span> <span class="mi">50505</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mh">0x482794</span><span class="p">))</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">SimulatedAnnealing</span><span class="p">(</span><span class="n">N</span><span class="p">,</span> <span class="n">C</span><span class="p">,</span> <span class="n">ZeroInitializer</span><span class="p">(</span><span class="n">N</span><span class="p">)</span> <span class="p">,</span> <span class="mf">1.5</span><span class="p">,</span> <span class="mf">1.0</span><span class="p">,</span> <span class="mf">0.9999</span><span class="p">,</span> <span class="mi">50505</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mh">0x917917</span><span class="p">))</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">SimulatedAnnealing</span><span class="p">(</span><span class="n">N</span><span class="p">,</span> <span class="n">C</span><span class="p">,</span> <span class="n">ZeroInitializer</span><span class="p">(</span><span class="n">N</span><span class="p">)</span> <span class="p">,</span> <span class="mf">2.5</span><span class="p">,</span> <span class="mf">1.0</span><span class="p">,</span> <span class="mf">0.9999</span><span class="p">,</span> <span class="mi">50505</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mh">0x482794</span><span class="p">))</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">SimulatedAnnealing</span><span class="p">(</span><span class="n">N</span><span class="p">,</span> <span class="n">C</span><span class="p">,</span> <span class="n">ZeroInitializer</span><span class="p">(</span><span class="n">N</span><span class="p">)</span> <span class="p">,</span> <span class="mf">1.5</span><span class="p">,</span> <span class="mf">1.0</span><span class="p">,</span> <span class="mf">0.9999</span><span class="p">,</span> <span class="mi">50505</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mh">0x917917</span><span class="p">))</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">SimulatedAnnealing</span><span class="p">(</span><span class="n">N</span><span class="p">,</span> <span class="n">C</span><span class="p">,</span> <span class="n">ZeroInitializer</span><span class="p">(</span><span class="n">N</span><span class="p">)</span> <span class="p">,</span> <span class="mf">1.5</span><span class="p">,</span> <span class="mf">1.0</span><span class="p">,</span> <span class="mf">0.9995</span><span class="p">,</span> <span class="mi">50505</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mh">0x917917</span><span class="p">))</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">SimulatedAnnealing</span><span class="p">(</span><span class="n">N</span><span class="p">,</span> <span class="n">C</span><span class="p">,</span> <span class="n">RandomInitializer</span><span class="p">(</span><span class="n">N</span><span class="p">,</span> <span class="n">R</span><span class="p">)</span> <span class="p">,</span> <span class="mf">1.5</span><span class="p">,</span> <span class="mf">5.0</span><span class="p">,</span> <span class="mf">0.9999</span><span class="p">,</span> <span class="mi">50505</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mh">0x917917</span><span class="p">))</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">SimulatedAnnealing</span><span class="p">(</span><span class="n">N</span><span class="p">,</span> <span class="n">C</span><span class="p">,</span> <span class="n">RandomInitializer</span><span class="p">(</span><span class="n">N</span><span class="p">,</span> <span class="n">R</span><span class="p">)</span> <span class="p">,</span> <span class="mf">1.5</span><span class="p">,</span> <span class="mf">5.0</span><span class="p">,</span> <span class="mf">0.9995</span><span class="p">,</span> <span class="mi">50505</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mh">0x917917</span><span class="p">))</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">SimulatedAnnealing</span><span class="p">(</span><span class="n">N</span><span class="p">,</span> <span class="n">C</span><span class="p">,</span> <span class="n">StrangeInitializer</span><span class="p">(</span><span class="n">N</span><span class="p">,</span> <span class="n">C</span><span class="p">),</span> <span class="mf">1.0</span><span class="p">,</span> <span class="mf">1.5</span><span class="p">,</span> <span class="mf">0.9999</span><span class="p">,</span> <span class="mi">50505</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mh">0x917917</span><span class="p">))</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">RandomSearch</span><span class="p">(</span><span class="n">N</span><span class="p">,</span> <span class="n">C</span><span class="p">,</span> <span class="mi">100</span><span class="p">,</span> <span class="mf">1.5</span><span class="p">,</span> <span class="mh">0x814814</span><span class="p">))</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="s">"0</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/16992백준22990 사이클2021-09-22T13:25:00+00:002021-09-22T13:25:00+00:00https://justicehui.github.io/ps/2021/09/22/BOJ22990<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/22990</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>MCMF</li> </ul> <h3 id="시간복잡도">시간복잡도</h3> <ul> <li>$O(N^4)$</li> </ul> <h3 id="풀이">풀이</h3> <p>문제에서 요구하는 결과를 인접 행렬로 나타내보면, 각 행/열마다 한 칸 선택한 형태가 된다는 것을 알 수 있습니다. 그러므로 이 문제는 이분 그래프에서 최소 가중치 완전 매칭을 구하는 문제로 바꿀 수 있습니다. 헝가리안 알고리즘을 사용하면 $O(N^3)$, MCMF를 사용하면 $O(N^4)$에 문제를 해결할 수 있습니다.</p> <h3 id="전체-코드">전체 코드</h3> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; #define x first #define y second #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) #define IDX(v, x) (lower_bound(all(v), x) - v.begin()) </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">using</span> <span class="n">uint</span> <span class="o">=</span> <span class="kt">unsigned</span><span class="p">;</span> <span class="k">using</span> <span class="n">ll</span> <span class="o">=</span> <span class="kt">long</span> <span class="kt">long</span><span class="p">;</span> <span class="k">using</span> <span class="n">ull</span> <span class="o">=</span> <span class="kt">unsigned</span> <span class="kt">long</span> <span class="kt">long</span><span class="p">;</span> <span class="k">constexpr</span> <span class="kt">int</span> <span class="n">INF32</span> <span class="o">=</span> <span class="mh">0x3f3f3f3f</span><span class="p">;</span> <span class="k">constexpr</span> <span class="n">ll</span> <span class="n">INF64</span> <span class="o">=</span> <span class="mh">0x3f3f3f3f3f3f3f3f</span><span class="p">;</span> <span class="k">struct</span> <span class="nc">Edge</span><span class="p">{</span> <span class="n">ll</span> <span class="n">v</span><span class="p">,</span> <span class="n">c</span><span class="p">,</span> <span class="n">f</span><span class="p">,</span> <span class="n">d</span><span class="p">,</span> <span class="n">r</span><span class="p">;</span> <span class="n">Edge</span><span class="p">()</span> <span class="o">=</span> <span class="k">default</span><span class="p">;</span> <span class="n">Edge</span><span class="p">(</span><span class="n">ll</span> <span class="n">v</span><span class="p">,</span> <span class="n">ll</span> <span class="n">c</span><span class="p">,</span> <span class="n">ll</span> <span class="n">d</span><span class="p">,</span> <span class="n">ll</span> <span class="n">r</span><span class="p">)</span> <span class="o">:</span> <span class="n">v</span><span class="p">(</span><span class="n">v</span><span class="p">),</span> <span class="n">c</span><span class="p">(</span><span class="n">c</span><span class="p">),</span> <span class="n">d</span><span class="p">(</span><span class="n">d</span><span class="p">),</span> <span class="n">r</span><span class="p">(</span><span class="n">r</span><span class="p">),</span> <span class="n">f</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span> <span class="p">{}</span> <span class="p">};</span> <span class="kt">int</span> <span class="n">N</span><span class="p">,</span> <span class="n">M</span><span class="p">,</span> <span class="n">W</span><span class="p">[</span><span class="mi">222</span><span class="p">][</span><span class="mi">222</span><span class="p">];</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">Edge</span><span class="o">&gt;</span> <span class="n">G</span><span class="p">[</span><span class="mi">444</span><span class="p">];</span> <span class="kt">void</span> <span class="nf">AddEdge</span><span class="p">(</span><span class="kt">int</span> <span class="n">s</span><span class="p">,</span> <span class="kt">int</span> <span class="n">e</span><span class="p">,</span> <span class="kt">int</span> <span class="n">c</span><span class="p">,</span> <span class="kt">int</span> <span class="n">d</span><span class="p">){</span> <span class="n">G</span><span class="p">[</span><span class="n">s</span><span class="p">].</span><span class="n">emplace_back</span><span class="p">(</span><span class="n">e</span><span class="p">,</span> <span class="n">c</span><span class="p">,</span> <span class="o">+</span><span class="n">d</span><span class="p">,</span> <span class="p">(</span><span class="kt">int</span><span class="p">)</span><span class="n">G</span><span class="p">[</span><span class="n">e</span><span class="p">].</span><span class="n">size</span><span class="p">());</span> <span class="n">G</span><span class="p">[</span><span class="n">e</span><span class="p">].</span><span class="n">emplace_back</span><span class="p">(</span><span class="n">s</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="o">-</span><span class="n">d</span><span class="p">,</span> <span class="p">(</span><span class="kt">int</span><span class="p">)</span><span class="n">G</span><span class="p">[</span><span class="n">s</span><span class="p">].</span><span class="n">size</span><span class="p">()</span><span class="o">-</span><span class="mi">1</span><span class="p">);</span> <span class="p">}</span> <span class="n">ll</span> <span class="n">D</span><span class="p">[</span><span class="mi">444</span><span class="p">];</span> <span class="kt">int</span> <span class="n">P</span><span class="p">[</span><span class="mi">444</span><span class="p">],</span> <span class="n">I</span><span class="p">[</span><span class="mi">444</span><span class="p">],</span> <span class="n">C</span><span class="p">[</span><span class="mi">444</span><span class="p">];</span> <span class="n">pair</span><span class="o">&lt;</span><span class="n">ll</span><span class="p">,</span> <span class="n">ll</span><span class="o">&gt;</span> <span class="n">Run</span><span class="p">(</span><span class="kt">int</span> <span class="n">S</span><span class="p">,</span> <span class="kt">int</span> <span class="n">T</span><span class="p">){</span> <span class="n">ll</span> <span class="n">flow</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="n">cost</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="nb">true</span><span class="p">){</span> <span class="n">memset</span><span class="p">(</span><span class="n">D</span><span class="p">,</span> <span class="mh">0x3f</span><span class="p">,</span> <span class="k">sizeof</span> <span class="n">D</span><span class="p">);</span> <span class="n">memset</span><span class="p">(</span><span class="n">C</span><span class="p">,</span> <span class="nb">false</span><span class="p">,</span> <span class="k">sizeof</span> <span class="n">C</span><span class="p">);</span> <span class="n">queue</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">q</span><span class="p">;</span> <span class="n">q</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">S</span><span class="p">);</span> <span class="n">D</span><span class="p">[</span><span class="n">S</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">C</span><span class="p">[</span><span class="n">S</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">q</span><span class="p">.</span><span class="n">size</span><span class="p">()){</span> <span class="kt">int</span> <span class="n">v</span> <span class="o">=</span> <span class="n">q</span><span class="p">.</span><span class="n">front</span><span class="p">();</span> <span class="n">q</span><span class="p">.</span><span class="n">pop</span><span class="p">();</span> <span class="n">C</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">G</span><span class="p">[</span><span class="n">v</span><span class="p">].</span><span class="n">size</span><span class="p">();</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="k">const</span> <span class="k">auto</span> <span class="o">&amp;</span><span class="n">e</span> <span class="o">=</span> <span class="n">G</span><span class="p">[</span><span class="n">v</span><span class="p">][</span><span class="n">i</span><span class="p">];</span> <span class="k">if</span><span class="p">(</span><span class="n">e</span><span class="p">.</span><span class="n">c</span> <span class="o">-</span> <span class="n">e</span><span class="p">.</span><span class="n">f</span> <span class="o">&gt;</span> <span class="mi">0</span> <span class="o">&amp;&amp;</span> <span class="n">D</span><span class="p">[</span><span class="n">e</span><span class="p">.</span><span class="n">v</span><span class="p">]</span> <span class="o">&gt;</span> <span class="n">D</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">+</span> <span class="n">e</span><span class="p">.</span><span class="n">d</span><span class="p">){</span> <span class="n">D</span><span class="p">[</span><span class="n">e</span><span class="p">.</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="n">D</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">+</span> <span class="n">e</span><span class="p">.</span><span class="n">d</span><span class="p">;</span> <span class="n">P</span><span class="p">[</span><span class="n">e</span><span class="p">.</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="n">v</span><span class="p">;</span> <span class="n">I</span><span class="p">[</span><span class="n">e</span><span class="p">.</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">C</span><span class="p">[</span><span class="n">e</span><span class="p">.</span><span class="n">v</span><span class="p">])</span> <span class="n">C</span><span class="p">[</span><span class="n">e</span><span class="p">.</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">,</span> <span class="n">q</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">e</span><span class="p">.</span><span class="n">v</span><span class="p">);</span> <span class="p">}</span> <span class="p">}</span> <span class="p">}</span> <span class="k">if</span><span class="p">(</span><span class="n">D</span><span class="p">[</span><span class="n">T</span><span class="p">]</span> <span class="o">==</span> <span class="n">INF64</span><span class="p">)</span> <span class="k">break</span><span class="p">;</span> <span class="n">ll</span> <span class="n">fl</span> <span class="o">=</span> <span class="n">INF64</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="n">T</span><span class="p">;</span> <span class="n">i</span><span class="o">!=</span><span class="n">S</span><span class="p">;</span> <span class="n">i</span><span class="o">=</span><span class="n">P</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="n">fl</span> <span class="o">=</span> <span class="n">min</span><span class="p">(</span><span class="n">fl</span><span class="p">,</span> <span class="n">G</span><span class="p">[</span><span class="n">P</span><span class="p">[</span><span class="n">i</span><span class="p">]][</span><span class="n">I</span><span class="p">[</span><span class="n">i</span><span class="p">]].</span><span class="n">c</span> <span class="o">-</span> <span class="n">G</span><span class="p">[</span><span class="n">P</span><span class="p">[</span><span class="n">i</span><span class="p">]][</span><span class="n">I</span><span class="p">[</span><span class="n">i</span><span class="p">]].</span><span class="n">f</span><span class="p">);</span> <span class="n">flow</span> <span class="o">+=</span> <span class="n">fl</span><span class="p">;</span> <span class="n">cost</span> <span class="o">+=</span> <span class="n">fl</span> <span class="o">*</span> <span class="n">D</span><span class="p">[</span><span class="n">T</span><span class="p">];</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="n">T</span><span class="p">;</span> <span class="n">i</span><span class="o">!=</span><span class="n">S</span><span class="p">;</span> <span class="n">i</span><span class="o">=</span><span class="n">P</span><span class="p">[</span><span class="n">i</span><span class="p">]){</span> <span class="n">G</span><span class="p">[</span><span class="n">P</span><span class="p">[</span><span class="n">i</span><span class="p">]][</span><span class="n">I</span><span class="p">[</span><span class="n">i</span><span class="p">]].</span><span class="n">f</span> <span class="o">+=</span> <span class="n">fl</span><span class="p">;</span> <span class="n">G</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">G</span><span class="p">[</span><span class="n">P</span><span class="p">[</span><span class="n">i</span><span class="p">]][</span><span class="n">I</span><span class="p">[</span><span class="n">i</span><span class="p">]].</span><span class="n">r</span><span class="p">].</span><span class="n">f</span> <span class="o">-=</span> <span class="n">fl</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> <span class="k">return</span> <span class="p">{</span><span class="n">flow</span><span class="p">,</span> <span class="n">cost</span><span class="p">};</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">N</span> <span class="o">&gt;&gt;</span> <span class="n">M</span><span class="p">;</span> <span class="n">memset</span><span class="p">(</span><span class="n">W</span><span class="p">,</span> <span class="mh">0x3f</span><span class="p">,</span> <span class="k">sizeof</span> <span class="n">W</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">,</span><span class="n">s</span><span class="p">,</span><span class="n">e</span><span class="p">,</span><span class="n">x</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">M</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">s</span> <span class="o">&gt;&gt;</span> <span class="n">e</span> <span class="o">&gt;&gt;</span> <span class="n">x</span><span class="p">,</span> <span class="n">W</span><span class="p">[</span><span class="n">s</span><span class="p">][</span><span class="n">e</span><span class="p">]</span> <span class="o">=</span> <span class="n">min</span><span class="p">(</span><span class="n">W</span><span class="p">[</span><span class="n">s</span><span class="p">][</span><span class="n">e</span><span class="p">],</span> <span class="n">x</span><span class="p">);</span> <span class="k">const</span> <span class="kt">int</span> <span class="n">S</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="n">T</span> <span class="o">=</span> <span class="n">N</span> <span class="o">&lt;&lt;</span> <span class="mi">1</span> <span class="o">|</span> <span class="mi">1</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">N</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="n">AddEdge</span><span class="p">(</span><span class="n">S</span><span class="p">,</span> <span class="n">i</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">0</span><span class="p">);</span> <span class="n">AddEdge</span><span class="p">(</span><span class="n">N</span><span class="o">+</span><span class="n">i</span><span class="p">,</span> <span class="n">T</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">0</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;=</span><span class="n">N</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">W</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">!=</span> <span class="n">INF32</span><span class="p">)</span> <span class="n">AddEdge</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">N</span><span class="o">+</span><span class="n">j</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="n">W</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]);</span> <span class="p">}</span> <span class="p">}</span> <span class="k">auto</span> <span class="p">[</span><span class="n">flow</span><span class="p">,</span> <span class="n">cost</span><span class="p">]</span> <span class="o">=</span> <span class="n">Run</span><span class="p">(</span><span class="n">S</span><span class="p">,</span> <span class="n">T</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">flow</span> <span class="o">!=</span> <span class="n">N</span><span class="p">){</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="mi">0</span><span class="p">;</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="p">}</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="s">"1</span><span class="se">\n</span><span class="s">"</span> <span class="o">&lt;&lt;</span> <span class="n">cost</span> <span class="o">&lt;&lt;</span> <span class="s">"</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">N</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="k">for</span><span class="p">(</span><span class="k">const</span> <span class="k">auto</span> <span class="o">&amp;</span><span class="n">e</span> <span class="o">:</span> <span class="n">G</span><span class="p">[</span><span class="n">i</span><span class="p">]){</span> <span class="k">if</span><span class="p">(</span><span class="n">e</span><span class="p">.</span><span class="n">f</span> <span class="o">==</span> <span class="mi">1</span><span class="p">)</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">i</span> <span class="o">&lt;&lt;</span> <span class="s">" "</span> <span class="o">&lt;&lt;</span> <span class="n">e</span><span class="p">.</span><span class="n">v</span><span class="o">-</span><span class="n">N</span> <span class="o">&lt;&lt;</span> <span class="s">"</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/22990백준19851 버거운 버거2021-09-21T13:24:00+00:002021-09-21T13:24:00+00:00https://justicehui.github.io/ps/2021/09/21/BOJ19851<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/19851</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>세그먼트 트리</li> </ul> <h3 id="시간복잡도">시간복잡도</h3> <ul> <li>$O(Q \log N)$</li> </ul> <h3 id="풀이">풀이</h3> <p>구간에 있는 빵을 뒤집는 쿼리가 없는 문제를 먼저 해결해봅시다.</p> <p>구간 $[a,b]$에 최소한의 괄호를 더 추가해서 올바른 괄호 문자열을 만드는 문제고, Prefix Minimum과 Range Sum을 관리해야 한다는 것은 쉽게 알 수 있습니다. 구간의 Prefix Minimum을 $mn$, Range Sum을 $sum$이라고 하면, 우리가 추가해야 하는 괄호의 개수는 $sum + 2\cdot\min(mn, 0)$입니다. 이러한 형태의 값은 세그먼트 트리를 이용해 쉽게 계산할 수 있습니다.</p> <p>구간에 있는 빵을 뒤집는 것은 구간에 있는 모든 원소에 <code class="language-plaintext highlighter-rouge">-1</code>을 곱하는 것과 같습니다. 그러므로 Prefix Minimum 뿐만 아니라 Prefix Maximum도 관리해야 구간에 <code class="language-plaintext highlighter-rouge">-1</code>을 곱하는 쿼리도 올바르게 처리할 수 있습니다. 간단한 Lazy Propagation 문제입니다.</p> <h3 id="전체-코드">전체 코드</h3> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; #define x first #define y second #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) #define IDX(v, x) (lower_bound(all(v), x) - v.begin()) </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">using</span> <span class="n">uint</span> <span class="o">=</span> <span class="kt">unsigned</span><span class="p">;</span> <span class="k">using</span> <span class="n">ll</span> <span class="o">=</span> <span class="kt">long</span> <span class="kt">long</span><span class="p">;</span> <span class="k">using</span> <span class="n">ull</span> <span class="o">=</span> <span class="kt">unsigned</span> <span class="kt">long</span> <span class="kt">long</span><span class="p">;</span> <span class="k">struct</span> <span class="nc">Node</span><span class="p">{</span> <span class="kt">int</span> <span class="n">mn</span><span class="p">,</span> <span class="n">mx</span><span class="p">,</span> <span class="n">sum</span><span class="p">;</span> <span class="n">Node</span><span class="p">()</span> <span class="o">:</span> <span class="n">Node</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span> <span class="p">{}</span> <span class="n">Node</span><span class="p">(</span><span class="kt">int</span> <span class="n">v</span><span class="p">)</span> <span class="o">:</span> <span class="n">Node</span><span class="p">(</span><span class="n">v</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">v</span><span class="p">)</span> <span class="p">{}</span> <span class="n">Node</span><span class="p">(</span><span class="kt">int</span> <span class="n">mn</span><span class="p">,</span> <span class="kt">int</span> <span class="n">mx</span><span class="p">,</span> <span class="kt">int</span> <span class="n">sum</span><span class="p">)</span> <span class="o">:</span> <span class="n">mn</span><span class="p">(</span><span class="n">mn</span><span class="p">),</span> <span class="n">mx</span><span class="p">(</span><span class="n">mx</span><span class="p">),</span> <span class="n">sum</span><span class="p">(</span><span class="n">sum</span><span class="p">)</span> <span class="p">{}</span> <span class="p">}</span> <span class="n">T</span><span class="p">[</span><span class="mi">1</span> <span class="o">&lt;&lt;</span> <span class="mi">21</span><span class="p">];</span> <span class="n">Node</span> <span class="k">operator</span> <span class="o">+</span> <span class="p">(</span><span class="k">const</span> <span class="n">Node</span> <span class="o">&amp;</span><span class="n">a</span><span class="p">,</span> <span class="k">const</span> <span class="n">Node</span> <span class="o">&amp;</span><span class="n">b</span><span class="p">){</span> <span class="k">return</span> <span class="p">{</span> <span class="n">min</span><span class="p">(</span><span class="n">a</span><span class="p">.</span><span class="n">mn</span><span class="p">,</span> <span class="n">a</span><span class="p">.</span><span class="n">sum</span> <span class="o">+</span> <span class="n">b</span><span class="p">.</span><span class="n">mn</span><span class="p">),</span> <span class="n">max</span><span class="p">(</span><span class="n">a</span><span class="p">.</span><span class="n">mx</span><span class="p">,</span> <span class="n">a</span><span class="p">.</span><span class="n">sum</span> <span class="o">+</span> <span class="n">b</span><span class="p">.</span><span class="n">mx</span><span class="p">),</span> <span class="n">a</span><span class="p">.</span><span class="n">sum</span> <span class="o">+</span> <span class="n">b</span><span class="p">.</span><span class="n">sum</span> <span class="p">};</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">N</span><span class="p">,</span> <span class="n">Q</span><span class="p">,</span> <span class="n">L</span><span class="p">[</span><span class="mi">1</span> <span class="o">&lt;&lt;</span> <span class="mi">21</span><span class="p">];</span> <span class="n">string</span> <span class="n">S</span><span class="p">;</span> <span class="kt">void</span> <span class="nf">Push</span><span class="p">(</span><span class="kt">int</span> <span class="n">node</span><span class="p">,</span> <span class="kt">int</span> <span class="n">s</span><span class="p">,</span> <span class="kt">int</span> <span class="n">e</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">L</span><span class="p">[</span><span class="n">node</span><span class="p">])</span> <span class="k">return</span><span class="p">;</span> <span class="n">T</span><span class="p">[</span><span class="n">node</span><span class="p">].</span><span class="n">sum</span> <span class="o">*=</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span> <span class="n">T</span><span class="p">[</span><span class="n">node</span><span class="p">].</span><span class="n">mn</span> <span class="o">*=</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span> <span class="n">T</span><span class="p">[</span><span class="n">node</span><span class="p">].</span><span class="n">mx</span> <span class="o">*=</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span> <span class="n">swap</span><span class="p">(</span><span class="n">T</span><span class="p">[</span><span class="n">node</span><span class="p">].</span><span class="n">mn</span><span class="p">,</span> <span class="n">T</span><span class="p">[</span><span class="n">node</span><span class="p">].</span><span class="n">mx</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">s</span> <span class="o">!=</span> <span class="n">e</span><span class="p">)</span> <span class="n">L</span><span class="p">[</span><span class="n">node</span><span class="o">&lt;&lt;</span><span class="mi">1</span><span class="p">]</span> <span class="o">^=</span> <span class="mi">1</span><span class="p">,</span> <span class="n">L</span><span class="p">[</span><span class="n">node</span><span class="o">&lt;&lt;</span><span class="mi">1</span><span class="o">|</span><span class="mi">1</span><span class="p">]</span> <span class="o">^=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">L</span><span class="p">[</span><span class="n">node</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="p">}</span> <span class="kt">void</span> <span class="nf">Init</span><span class="p">(</span><span class="kt">int</span> <span class="n">node</span><span class="o">=</span><span class="mi">1</span><span class="p">,</span> <span class="kt">int</span> <span class="n">s</span><span class="o">=</span><span class="mi">1</span><span class="p">,</span> <span class="kt">int</span> <span class="n">e</span><span class="o">=</span><span class="n">N</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">s</span> <span class="o">==</span> <span class="n">e</span><span class="p">){</span> <span class="n">T</span><span class="p">[</span><span class="n">node</span><span class="p">]</span> <span class="o">=</span> <span class="n">Node</span><span class="p">(</span><span class="n">S</span><span class="p">[</span><span class="n">s</span><span class="p">]</span> <span class="o">==</span> <span class="sc">'('</span> <span class="o">?</span> <span class="mi">1</span> <span class="o">:</span> <span class="o">-</span><span class="mi">1</span><span class="p">);</span> <span class="k">return</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">m</span> <span class="o">=</span> <span class="n">s</span> <span class="o">+</span> <span class="n">e</span> <span class="o">&gt;&gt;</span> <span class="mi">1</span><span class="p">;</span> <span class="n">Init</span><span class="p">(</span><span class="n">node</span><span class="o">&lt;&lt;</span><span class="mi">1</span><span class="p">,</span> <span class="n">s</span><span class="p">,</span> <span class="n">m</span><span class="p">);</span> <span class="n">Init</span><span class="p">(</span><span class="n">node</span><span class="o">&lt;&lt;</span><span class="mi">1</span><span class="o">|</span><span class="mi">1</span><span class="p">,</span> <span class="n">m</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">e</span><span class="p">);</span> <span class="n">T</span><span class="p">[</span><span class="n">node</span><span class="p">]</span> <span class="o">=</span> <span class="n">T</span><span class="p">[</span><span class="n">node</span><span class="o">&lt;&lt;</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">T</span><span class="p">[</span><span class="n">node</span><span class="o">&lt;&lt;</span><span class="mi">1</span><span class="o">|</span><span class="mi">1</span><span class="p">];</span> <span class="p">}</span> <span class="kt">void</span> <span class="nf">Update</span><span class="p">(</span><span class="kt">int</span> <span class="n">l</span><span class="p">,</span> <span class="kt">int</span> <span class="n">r</span><span class="p">,</span> <span class="kt">int</span> <span class="n">node</span><span class="o">=</span><span class="mi">1</span><span class="p">,</span> <span class="kt">int</span> <span class="n">s</span><span class="o">=</span><span class="mi">1</span><span class="p">,</span> <span class="kt">int</span> <span class="n">e</span><span class="o">=</span><span class="n">N</span><span class="p">){</span> <span class="n">Push</span><span class="p">(</span><span class="n">node</span><span class="p">,</span> <span class="n">s</span><span class="p">,</span> <span class="n">e</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">r</span> <span class="o">&lt;</span> <span class="n">s</span> <span class="o">||</span> <span class="n">e</span> <span class="o">&lt;</span> <span class="n">l</span><span class="p">)</span> <span class="k">return</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">l</span> <span class="o">&lt;=</span> <span class="n">s</span> <span class="o">&amp;&amp;</span> <span class="n">e</span> <span class="o">&lt;=</span> <span class="n">r</span><span class="p">){</span> <span class="n">L</span><span class="p">[</span><span class="n">node</span><span class="p">]</span> <span class="o">^=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">Push</span><span class="p">(</span><span class="n">node</span><span class="p">,</span> <span class="n">s</span><span class="p">,</span> <span class="n">e</span><span class="p">);</span> <span class="k">return</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">m</span> <span class="o">=</span> <span class="n">s</span> <span class="o">+</span> <span class="n">e</span> <span class="o">&gt;&gt;</span> <span class="mi">1</span><span class="p">;</span> <span class="n">Update</span><span class="p">(</span><span class="n">l</span><span class="p">,</span> <span class="n">r</span><span class="p">,</span> <span class="n">node</span><span class="o">&lt;&lt;</span><span class="mi">1</span><span class="p">,</span> <span class="n">s</span><span class="p">,</span> <span class="n">m</span><span class="p">);</span> <span class="n">Update</span><span class="p">(</span><span class="n">l</span><span class="p">,</span> <span class="n">r</span><span class="p">,</span> <span class="n">node</span><span class="o">&lt;&lt;</span><span class="mi">1</span><span class="o">|</span><span class="mi">1</span><span class="p">,</span> <span class="n">m</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">e</span><span class="p">);</span> <span class="n">T</span><span class="p">[</span><span class="n">node</span><span class="p">]</span> <span class="o">=</span> <span class="n">T</span><span class="p">[</span><span class="n">node</span><span class="o">&lt;&lt;</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">T</span><span class="p">[</span><span class="n">node</span><span class="o">&lt;&lt;</span><span class="mi">1</span><span class="o">|</span><span class="mi">1</span><span class="p">];</span> <span class="p">}</span> <span class="n">Node</span> <span class="nf">Query</span><span class="p">(</span><span class="kt">int</span> <span class="n">l</span><span class="p">,</span> <span class="kt">int</span> <span class="n">r</span><span class="p">,</span> <span class="kt">int</span> <span class="n">node</span><span class="o">=</span><span class="mi">1</span><span class="p">,</span> <span class="kt">int</span> <span class="n">s</span><span class="o">=</span><span class="mi">1</span><span class="p">,</span> <span class="kt">int</span> <span class="n">e</span><span class="o">=</span><span class="n">N</span><span class="p">){</span> <span class="n">Push</span><span class="p">(</span><span class="n">node</span><span class="p">,</span> <span class="n">s</span><span class="p">,</span> <span class="n">e</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">r</span> <span class="o">&lt;</span> <span class="n">s</span> <span class="o">||</span> <span class="n">e</span> <span class="o">&lt;</span> <span class="n">l</span><span class="p">)</span> <span class="k">return</span> <span class="n">Node</span><span class="p">();</span> <span class="k">if</span><span class="p">(</span><span class="n">l</span> <span class="o">&lt;=</span> <span class="n">s</span> <span class="o">&amp;&amp;</span> <span class="n">e</span> <span class="o">&lt;=</span> <span class="n">r</span><span class="p">)</span> <span class="k">return</span> <span class="n">T</span><span class="p">[</span><span class="n">node</span><span class="p">];</span> <span class="kt">int</span> <span class="n">m</span> <span class="o">=</span> <span class="n">s</span> <span class="o">+</span> <span class="n">e</span> <span class="o">&gt;&gt;</span> <span class="mi">1</span><span class="p">;</span> <span class="k">return</span> <span class="n">Query</span><span class="p">(</span><span class="n">l</span><span class="p">,</span> <span class="n">r</span><span class="p">,</span> <span class="n">node</span><span class="o">&lt;&lt;</span><span class="mi">1</span><span class="p">,</span> <span class="n">s</span><span class="p">,</span> <span class="n">m</span><span class="p">)</span> <span class="o">+</span> <span class="n">Query</span><span class="p">(</span><span class="n">l</span><span class="p">,</span> <span class="n">r</span><span class="p">,</span> <span class="n">node</span><span class="o">&lt;&lt;</span><span class="mi">1</span><span class="o">|</span><span class="mi">1</span><span class="p">,</span> <span class="n">m</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">e</span><span class="p">);</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">N</span> <span class="o">&gt;&gt;</span> <span class="n">S</span><span class="p">;</span> <span class="n">S</span> <span class="o">=</span> <span class="s">"#"</span> <span class="o">+</span> <span class="n">S</span><span class="p">;</span> <span class="n">Init</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="n">N</span><span class="p">);</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">Q</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">Q</span><span class="o">--</span><span class="p">){</span> <span class="kt">int</span> <span class="n">op</span><span class="p">,</span> <span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">;</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">op</span> <span class="o">&gt;&gt;</span> <span class="n">a</span> <span class="o">&gt;&gt;</span> <span class="n">b</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">op</span> <span class="o">==</span> <span class="mi">1</span><span class="p">)</span> <span class="n">Update</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">);</span> <span class="k">else</span><span class="p">{</span> <span class="k">auto</span> <span class="n">res</span> <span class="o">=</span> <span class="n">Query</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">);</span> <span class="kt">int</span> <span class="n">ans</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">res</span><span class="p">.</span><span class="n">mn</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="p">)</span> <span class="n">ans</span> <span class="o">-=</span> <span class="n">res</span><span class="p">.</span><span class="n">mn</span><span class="p">,</span> <span class="n">res</span><span class="p">.</span><span class="n">sum</span> <span class="o">-=</span> <span class="n">res</span><span class="p">.</span><span class="n">mn</span><span class="p">;</span> <span class="n">ans</span> <span class="o">+=</span> <span class="n">res</span><span class="p">.</span><span class="n">sum</span><span class="p">;</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">ans</span> <span class="o">+</span> <span class="n">b</span> <span class="o">-</span> <span class="n">a</span> <span class="o">+</span> <span class="mi">1</span> <span class="o">&lt;&lt;</span> <span class="s">"</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/19851백준19672 Feast2021-09-20T13:22:00+00:002021-09-20T13:22:00+00:00https://justicehui.github.io/ps/2021/09/20/BOJ19672<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/19672</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>Aliens Trick</li> </ul> <h3 id="시간복잡도">시간복잡도</h3> <ul> <li>$O(N \log X)$</li> </ul> <h3 id="풀이">풀이</h3> <p>구간을 하나 더 선택할 때마다 얻는 이득이 점점 감소한다는 것($K$에 대한 정답이 볼록하다는 것)은 직관적으로 알 수 있습니다. 그러므로 Aliens Trick을 생각해볼 수 있습니다. $K$ 조건을 없애고, 구간을 한 개 선택할 때마다 $c$만큼 패널티가 감소하는 문제를 풀어봅시다.</p> <p>$D(i, 0)$을 $1\cdots i$번째 원소만 고려했을 때, $i$번째 원소는 선택한 구간에 포함하지 않은 최댓값, $D(i, 1)$는 $i$번째 원소를 포함한 최댓값이라고 정의합시다. 상태 전이는 다음과 같습니다.</p> <ul> <li>$D(i, 0) \leftarrow \max\lbrace D(i-1, 0), D(i-1, 1) \rbrace$</li> <li>$D(i, 1) \leftarrow \max\lbrace D(i-1, 0) + A_i - c, D(i-1, 1) + A_i \rbrace$</li> </ul> <p>크기가 0인 구간도 선택할 수 있으므로, 최댓값이 같다면 선택한 구간의 개수는 가장 작은 값을 저장하면 됩니다.</p> <h3 id="전체-코드">전체 코드</h3> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; #define x first #define y second #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) #define IDX(v, x) (lower_bound(all(v), x) - v.begin()) </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">using</span> <span class="n">uint</span> <span class="o">=</span> <span class="kt">unsigned</span><span class="p">;</span> <span class="k">using</span> <span class="n">ll</span> <span class="o">=</span> <span class="kt">long</span> <span class="kt">long</span><span class="p">;</span> <span class="k">using</span> <span class="n">ull</span> <span class="o">=</span> <span class="kt">unsigned</span> <span class="kt">long</span> <span class="kt">long</span><span class="p">;</span> <span class="k">constexpr</span> <span class="n">ll</span> <span class="n">INF</span> <span class="o">=</span> <span class="mh">0x3f3f3f3f3f3f3f3f</span><span class="p">;</span> <span class="k">struct</span> <span class="nc">DP</span><span class="p">{</span> <span class="n">ll</span> <span class="n">v</span><span class="p">,</span> <span class="n">c</span><span class="p">;</span> <span class="n">DP</span><span class="p">()</span> <span class="o">:</span> <span class="n">DP</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span> <span class="p">{}</span> <span class="n">DP</span><span class="p">(</span><span class="n">ll</span> <span class="n">v</span><span class="p">,</span> <span class="n">ll</span> <span class="n">c</span><span class="p">)</span> <span class="o">:</span> <span class="n">v</span><span class="p">(</span><span class="n">v</span><span class="p">),</span> <span class="n">c</span><span class="p">(</span><span class="n">c</span><span class="p">)</span> <span class="p">{}</span> <span class="kt">bool</span> <span class="k">operator</span> <span class="o">&lt;</span> <span class="p">(</span><span class="k">const</span> <span class="n">DP</span> <span class="o">&amp;</span><span class="n">t</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span> <span class="k">return</span> <span class="n">v</span> <span class="o">!=</span> <span class="n">t</span><span class="p">.</span><span class="n">v</span> <span class="o">?</span> <span class="n">v</span> <span class="o">&lt;</span> <span class="n">t</span><span class="p">.</span><span class="n">v</span> <span class="o">:</span> <span class="n">c</span> <span class="o">&gt;</span> <span class="n">t</span><span class="p">.</span><span class="n">c</span><span class="p">;</span> <span class="p">}</span> <span class="n">DP</span> <span class="k">operator</span> <span class="o">+</span> <span class="p">(</span><span class="k">const</span> <span class="n">DP</span> <span class="o">&amp;</span><span class="n">t</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span> <span class="k">return</span> <span class="p">{</span><span class="n">v</span> <span class="o">+</span> <span class="n">t</span><span class="p">.</span><span class="n">v</span><span class="p">,</span> <span class="n">c</span> <span class="o">+</span> <span class="n">t</span><span class="p">.</span><span class="n">c</span><span class="p">};</span> <span class="p">}</span> <span class="p">};</span> <span class="kt">int</span> <span class="n">N</span><span class="p">,</span> <span class="n">K</span><span class="p">;</span> <span class="n">ll</span> <span class="n">A</span><span class="p">[</span><span class="mi">303030</span><span class="p">];</span> <span class="n">DP</span> <span class="n">D</span><span class="p">[</span><span class="mi">303030</span><span class="p">][</span><span class="mi">2</span><span class="p">];</span> <span class="kt">int</span> <span class="nf">Check</span><span class="p">(</span><span class="n">ll</span> <span class="n">c</span><span class="p">){</span> <span class="n">D</span><span class="p">[</span><span class="mi">0</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="p">{</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">};</span> <span class="n">D</span><span class="p">[</span><span class="mi">0</span><span class="p">][</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="p">{</span><span class="o">-</span><span class="n">INF</span><span class="p">,</span> <span class="mi">0</span><span class="p">};</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">N</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="n">max</span><span class="p">(</span><span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="mi">0</span><span class="p">],</span> <span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="mi">1</span><span class="p">]);</span> <span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="n">max</span><span class="p">(</span><span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span> <span class="o">+</span> <span class="n">DP</span><span class="p">(</span><span class="n">A</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">-</span> <span class="n">c</span><span class="p">,</span> <span class="mi">1</span><span class="p">),</span> <span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">DP</span><span class="p">(</span><span class="n">A</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="mi">0</span><span class="p">));</span> <span class="p">}</span> <span class="k">return</span> <span class="n">max</span><span class="p">(</span><span class="n">D</span><span class="p">[</span><span class="n">N</span><span class="p">][</span><span class="mi">0</span><span class="p">],</span> <span class="n">D</span><span class="p">[</span><span class="n">N</span><span class="p">][</span><span class="mi">1</span><span class="p">]).</span><span class="n">c</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">N</span> <span class="o">&gt;&gt;</span> <span class="n">K</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">N</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">A</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> <span class="n">ll</span> <span class="n">l</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="n">r</span> <span class="o">=</span> <span class="n">INF</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">l</span> <span class="o">&lt;</span> <span class="n">r</span><span class="p">){</span> <span class="n">ll</span> <span class="n">m</span> <span class="o">=</span> <span class="n">l</span> <span class="o">+</span> <span class="n">r</span> <span class="o">&gt;&gt;</span> <span class="mi">1</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">Check</span><span class="p">(</span><span class="n">m</span><span class="p">)</span> <span class="o">&lt;=</span> <span class="n">K</span><span class="p">)</span> <span class="n">r</span> <span class="o">=</span> <span class="n">m</span><span class="p">;</span> <span class="k">else</span> <span class="n">l</span> <span class="o">=</span> <span class="n">m</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span> <span class="p">}</span> <span class="n">Check</span><span class="p">(</span><span class="n">r</span><span class="p">);</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">max</span><span class="p">(</span><span class="n">D</span><span class="p">[</span><span class="n">N</span><span class="p">][</span><span class="mi">0</span><span class="p">],</span> <span class="n">D</span><span class="p">[</span><span class="n">N</span><span class="p">][</span><span class="mi">1</span><span class="p">]).</span><span class="n">v</span> <span class="o">+</span> <span class="n">r</span> <span class="o">*</span> <span class="n">K</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/19672백준13165 이것도 해결해 보시지2021-09-19T13:20:00+00:002021-09-19T13:20:00+00:00https://justicehui.github.io/ps/2021/09/19/BOJ13165<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/13165</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>랜덤</li> </ul> <h3 id="시간복잡도">시간복잡도</h3> <ul> <li>$O(N^2M)$</li> </ul> <h3 id="풀이">풀이</h3> <p>두 정사각행렬 $A, B$와 두 행렬을 곱한 결과 $C$가 주어졌을 때 곱셈이 올바르게 수행되었는지 $O(N^2)$ 랜덤 알고리즘은 <a href="https://en.wikipedia.org/wiki/Freivalds%27_algorithm">잘 알려져 있습니다</a>. 알고리즘을 간단하게 요약하자면, 랜덤한 $N\times 1$ 행렬 $V$를 만들어서 $A\times (BV) = CV$인지 확인하면 곱셈을 올바르게 수행했는지 높은 확률로 판별할 수 있습니다.</p> <p>Freivalds’ Algorithm을 알고 있다면, 이 문제는 간단한 그리디로 해결할 수 있는 스케줄링 문제로 바뀌게 됩니다.</p> <p>$N\times N$행렬과 $N\times 1$행렬을 곱하는 부분을 조금 신경써서 구현하면 컴파일러가 SIMD로 최적화를 해주기 때문에 매우 빠르게 동작합니다. 자세한 구현은 아래 코드를 참고해주세요.</p> <h3 id="전체-코드">전체 코드</h3> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#pragma GCC optimize ("O3,unroll-loops") #pragma GCC target ("avx,avx2,fma") #include &lt;bits/stdc++.h&gt; </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">using</span> <span class="n">uint</span> <span class="o">=</span> <span class="kt">unsigned</span> <span class="kt">int</span><span class="p">;</span> <span class="kt">int</span> <span class="n">N</span><span class="p">,</span> <span class="n">M</span><span class="p">;</span> <span class="k">alignas</span><span class="p">(</span><span class="mi">32</span><span class="p">)</span> <span class="n">uint</span> <span class="n">A</span><span class="p">[</span><span class="mi">1024000</span><span class="p">],</span> <span class="n">R1</span><span class="p">[</span><span class="mi">256</span><span class="p">],</span> <span class="n">R2</span><span class="p">[</span><span class="mi">256</span><span class="p">],</span> <span class="n">R3</span><span class="p">[</span><span class="mi">256</span><span class="p">],</span> <span class="n">R</span><span class="p">[</span><span class="mi">256</span><span class="p">];</span> <span class="n">mt19937</span> <span class="nf">Gen</span><span class="p">((</span><span class="kt">unsigned</span><span class="p">)</span><span class="n">chrono</span><span class="o">::</span><span class="n">steady_clock</span><span class="o">::</span><span class="n">now</span><span class="p">().</span><span class="n">time_since_epoch</span><span class="p">().</span><span class="n">count</span><span class="p">());</span> <span class="kt">bool</span> <span class="nf">Test</span><span class="p">(</span><span class="kt">int</span> <span class="n">st</span><span class="p">){</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">N</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="n">R1</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;</span><span class="n">N</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="n">R1</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">+=</span> <span class="n">A</span><span class="p">[</span><span class="n">i</span><span class="o">*</span><span class="n">M</span><span class="o">+</span><span class="n">st</span><span class="o">+</span><span class="n">N</span><span class="o">+</span><span class="n">j</span><span class="p">]</span> <span class="o">*</span> <span class="n">R</span><span class="p">[</span><span class="n">j</span><span class="p">];</span> <span class="p">}</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">N</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="n">R2</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;</span><span class="n">N</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="n">R2</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">+=</span> <span class="n">A</span><span class="p">[</span><span class="n">i</span><span class="o">*</span><span class="n">M</span><span class="o">+</span><span class="n">st</span><span class="o">+</span><span class="n">j</span><span class="p">]</span> <span class="o">*</span> <span class="n">R1</span><span class="p">[</span><span class="n">j</span><span class="p">];</span> <span class="p">}</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">N</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="n">R3</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;</span><span class="n">N</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="n">R3</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">+=</span> <span class="n">A</span><span class="p">[</span><span class="n">i</span><span class="o">*</span><span class="n">M</span><span class="o">+</span><span class="n">st</span><span class="o">+</span><span class="n">N</span><span class="o">+</span><span class="n">N</span><span class="o">+</span><span class="n">j</span><span class="p">]</span> <span class="o">*</span> <span class="n">R</span><span class="p">[</span><span class="n">j</span><span class="p">];</span> <span class="p">}</span> <span class="kt">bool</span> <span class="n">res</span> <span class="o">=</span> <span class="nb">true</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">N</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">res</span> <span class="o">&amp;=</span> <span class="n">R2</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="n">R3</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> <span class="k">return</span> <span class="n">res</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">N</span> <span class="o">&gt;&gt;</span> <span class="n">M</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">N</span><span class="o">*</span><span class="n">M</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">A</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">N</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">R</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">Gen</span><span class="p">()</span> <span class="o">&amp;</span> <span class="mi">65535</span><span class="p">;</span> <span class="kt">int</span> <span class="n">lst</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="n">cnt</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">+</span><span class="n">N</span><span class="o">*</span><span class="mi">3</span><span class="o">&lt;=</span><span class="n">M</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">Test</span><span class="p">(</span><span class="n">i</span><span class="p">))</span> <span class="n">cnt</span><span class="o">++</span><span class="p">,</span> <span class="n">lst</span> <span class="o">=</span> <span class="n">i</span> <span class="o">=</span> <span class="n">i</span> <span class="o">+</span> <span class="n">N</span><span class="o">*</span><span class="mi">3</span> <span class="o">-</span> <span class="mi">1</span><span class="p">;</span> <span class="p">}</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">cnt</span> <span class="o">*</span> <span class="n">N</span> <span class="o">*</span> <span class="n">N</span> <span class="o">*</span> <span class="mi">3</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/13165백준13352 석양이 진다…2021-09-18T13:19:00+00:002021-09-18T13:19:00+00:00https://justicehui.github.io/icpc/2021/09/18/BOJ13352<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/13352</li> </ul> <h3 id="문제-출처">문제 출처</h3> <ul> <li>2016 BAPC 예선 J번</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>랜덤</li> </ul> <h3 id="시간복잡도">시간복잡도</h3> <ul> <li>$O(N \cdot iteration)$</li> </ul> <h3 id="풀이">풀이</h3> <p>두 점을 랜덤으로 선택해서 직선을 하나 만들고, 그 직선에 포함되지 않은 점들을 다른 한 직선으로 커버할 수 있는지 확인하는 랜덤 풀이를 시도해볼 수 있습니다. 점이 $N$개 있고, 두 직선에 점이 각각 $a, b$개($a+b=N$) 포함된다고 하면, 실제로 정답이 존재할 때 정답을 찾지 못할 확률(실패할 확률)은 $\frac{ab}{N\choose 2} \approx \frac{2ab}{N^2}$입니다.</p> <p>$a = b = N/2$일 때 실패할 확률이 최대가 되며, 이때 실패할 확률은 대략 $\frac{2 \cdot \frac{N}{2}\cdot\frac{N}{2}}{N^2} = \frac{1}{2}$입니다. 최악의 경우에도 실패할 확률이 $\frac{1}{2}$보다 크지 않기 때문에 이 풀이를 $K$번 반복해서 수행하면 실패할 확률은 $(\frac{1}{2})^K$이하가 되고, 시간 복잡도는 $O(NK)$입니다.</p> <h3 id="전체-코드">전체 코드</h3> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; #define x first #define y second #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) #define IDX(v, x) (lower_bound(all(v), x) - v.begin()) </span> <span class="k">using</span> <span class="n">uint</span> <span class="o">=</span> <span class="kt">unsigned</span><span class="p">;</span> <span class="k">using</span> <span class="n">ll</span> <span class="o">=</span> <span class="kt">long</span> <span class="kt">long</span><span class="p">;</span> <span class="k">using</span> <span class="n">ull</span> <span class="o">=</span> <span class="kt">unsigned</span> <span class="kt">long</span> <span class="kt">long</span><span class="p">;</span> <span class="k">using</span> <span class="n">coord_t</span> <span class="o">=</span> <span class="n">ll</span><span class="p">;</span> <span class="k">using</span> <span class="n">Point</span> <span class="o">=</span> <span class="n">pair</span><span class="o">&lt;</span><span class="n">coord_t</span><span class="p">,</span> <span class="n">coord_t</span><span class="o">&gt;</span><span class="p">;</span> <span class="n">istream</span><span class="o">&amp;</span> <span class="k">operator</span> <span class="o">&gt;&gt;</span> <span class="p">(</span><span class="n">istream</span> <span class="o">&amp;</span><span class="n">in</span><span class="p">,</span> <span class="n">Point</span> <span class="o">&amp;</span><span class="n">t</span><span class="p">){</span> <span class="n">in</span> <span class="o">&gt;&gt;</span> <span class="n">t</span><span class="p">.</span><span class="n">x</span> <span class="o">&gt;&gt;</span> <span class="n">t</span><span class="p">.</span><span class="n">y</span><span class="p">;</span> <span class="k">return</span> <span class="n">in</span><span class="p">;</span> <span class="p">}</span> <span class="n">Point</span> <span class="k">operator</span> <span class="o">+</span> <span class="p">(</span><span class="n">Point</span> <span class="n">p1</span><span class="p">,</span> <span class="n">Point</span> <span class="n">p2</span><span class="p">){</span> <span class="k">return</span> <span class="p">{</span><span class="n">p1</span><span class="p">.</span><span class="n">x</span><span class="o">+</span><span class="n">p2</span><span class="p">.</span><span class="n">x</span><span class="p">,</span> <span class="n">p1</span><span class="p">.</span><span class="n">y</span><span class="o">+</span><span class="n">p2</span><span class="p">.</span><span class="n">y</span><span class="p">};</span> <span class="p">}</span> <span class="n">Point</span> <span class="k">operator</span> <span class="o">-</span> <span class="p">(</span><span class="n">Point</span> <span class="n">p1</span><span class="p">,</span> <span class="n">Point</span> <span class="n">p2</span><span class="p">){</span> <span class="k">return</span> <span class="p">{</span><span class="n">p1</span><span class="p">.</span><span class="n">x</span><span class="o">-</span><span class="n">p2</span><span class="p">.</span><span class="n">x</span><span class="p">,</span> <span class="n">p1</span><span class="p">.</span><span class="n">y</span><span class="o">-</span><span class="n">p2</span><span class="p">.</span><span class="n">y</span><span class="p">};</span> <span class="p">}</span> <span class="n">coord_t</span> <span class="k">operator</span> <span class="o">*</span> <span class="p">(</span><span class="n">Point</span> <span class="n">p1</span><span class="p">,</span> <span class="n">Point</span> <span class="n">p2</span><span class="p">){</span> <span class="k">return</span> <span class="n">p1</span><span class="p">.</span><span class="n">x</span><span class="o">*</span><span class="n">p2</span><span class="p">.</span><span class="n">x</span> <span class="o">+</span> <span class="n">p1</span><span class="p">.</span><span class="n">y</span><span class="o">*</span><span class="n">p2</span><span class="p">.</span><span class="n">y</span><span class="p">;</span> <span class="p">}</span> <span class="c1">/// dot product</span> <span class="n">coord_t</span> <span class="k">operator</span> <span class="o">/</span> <span class="p">(</span><span class="n">Point</span> <span class="n">p1</span><span class="p">,</span> <span class="n">Point</span> <span class="n">p2</span><span class="p">){</span> <span class="k">return</span> <span class="n">p1</span><span class="p">.</span><span class="n">x</span><span class="o">*</span><span class="n">p2</span><span class="p">.</span><span class="n">y</span> <span class="o">-</span> <span class="n">p2</span><span class="p">.</span><span class="n">x</span><span class="o">*</span><span class="n">p1</span><span class="p">.</span><span class="n">y</span><span class="p">;</span> <span class="p">}</span> <span class="c1">/// cross product</span> <span class="n">coord_t</span> <span class="nf">_CCW</span><span class="p">(</span><span class="k">const</span> <span class="n">Point</span> <span class="o">&amp;</span><span class="n">p1</span><span class="p">,</span> <span class="k">const</span> <span class="n">Point</span> <span class="o">&amp;</span><span class="n">p2</span><span class="p">,</span> <span class="k">const</span> <span class="n">Point</span> <span class="o">&amp;</span><span class="n">p3</span><span class="p">){</span> <span class="k">return</span> <span class="p">(</span><span class="n">p2</span><span class="o">-</span><span class="n">p1</span><span class="p">)</span><span class="o">/</span><span class="p">(</span><span class="n">p3</span><span class="o">-</span><span class="n">p2</span><span class="p">);</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">CCW</span><span class="p">(</span><span class="n">Point</span> <span class="n">p1</span><span class="p">,</span> <span class="n">Point</span> <span class="n">p2</span><span class="p">,</span> <span class="n">Point</span> <span class="n">p3</span><span class="p">){</span> <span class="k">auto</span> <span class="n">res</span> <span class="o">=</span> <span class="n">_CCW</span><span class="p">(</span><span class="n">p1</span><span class="p">,</span> <span class="n">p2</span><span class="p">,</span> <span class="n">p3</span><span class="p">);</span> <span class="k">return</span> <span class="p">(</span><span class="n">res</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">)</span> <span class="o">-</span> <span class="p">(</span><span class="n">res</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="p">);</span> <span class="p">}</span> <span class="n">coord_t</span> <span class="nf">D</span><span class="p">(</span><span class="k">const</span> <span class="n">Point</span> <span class="o">&amp;</span><span class="n">p1</span><span class="p">,</span> <span class="k">const</span> <span class="n">Point</span> <span class="o">&amp;</span><span class="n">p2</span><span class="p">){</span> <span class="k">auto</span> <span class="n">dx</span> <span class="o">=</span> <span class="n">p1</span><span class="p">.</span><span class="n">x</span> <span class="o">-</span> <span class="n">p2</span><span class="p">.</span><span class="n">x</span><span class="p">,</span> <span class="n">dy</span> <span class="o">=</span> <span class="n">p1</span><span class="p">.</span><span class="n">y</span> <span class="o">-</span> <span class="n">p2</span><span class="p">.</span><span class="n">y</span><span class="p">;</span> <span class="k">return</span> <span class="n">dx</span><span class="o">*</span><span class="n">dx</span> <span class="o">+</span> <span class="n">dy</span><span class="o">*</span><span class="n">dy</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">N</span><span class="p">;</span> <span class="n">Point</span> <span class="n">A</span><span class="p">[</span><span class="mi">101010</span><span class="p">];</span> <span class="n">mt19937</span> <span class="nf">rd</span><span class="p">(</span><span class="mh">0x917917</span><span class="p">);</span> <span class="kt">int</span> <span class="nf">rand</span><span class="p">(</span><span class="kt">int</span> <span class="n">l</span><span class="p">,</span> <span class="kt">int</span> <span class="n">r</span><span class="p">){</span> <span class="k">return</span> <span class="n">uniform_int_distribution</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="p">(</span><span class="n">l</span><span class="p">,</span> <span class="n">r</span><span class="p">)(</span><span class="n">rd</span><span class="p">);</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">N</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">N</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">A</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> <span class="k">if</span><span class="p">(</span><span class="n">N</span> <span class="o">&lt;=</span> <span class="mi">2</span><span class="p">){</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="s">"success"</span><span class="p">;</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="p">}</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">iter</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">iter</span><span class="o">&lt;=</span><span class="mi">100</span><span class="p">;</span> <span class="n">iter</span><span class="o">++</span><span class="p">){</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">Point</span><span class="o">&gt;</span> <span class="n">P</span><span class="p">;</span> <span class="kt">int</span> <span class="n">a</span> <span class="o">=</span> <span class="n">rand</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="n">N</span><span class="p">),</span> <span class="n">b</span> <span class="o">=</span> <span class="n">rand</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="n">N</span><span class="p">),</span> <span class="n">flag</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">a</span> <span class="o">==</span> <span class="n">b</span><span class="p">)</span> <span class="n">b</span> <span class="o">=</span> <span class="n">rand</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="n">N</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">N</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="n">CCW</span><span class="p">(</span><span class="n">A</span><span class="p">[</span><span class="n">a</span><span class="p">],</span> <span class="n">A</span><span class="p">[</span><span class="n">b</span><span class="p">],</span> <span class="n">A</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="o">!=</span> <span class="mi">0</span><span class="p">)</span> <span class="n">P</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">A</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">2</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">P</span><span class="p">.</span><span class="n">size</span><span class="p">();</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="n">CCW</span><span class="p">(</span><span class="n">P</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">2</span><span class="p">],</span> <span class="n">P</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">],</span> <span class="n">P</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="o">!=</span> <span class="mi">0</span><span class="p">)</span> <span class="n">flag</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">flag</span><span class="p">){</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="s">"success"</span><span class="p">;</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="s">"failure"</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/13352백준16046 Rainbow Graph2021-09-08T03:52:00+00:002021-09-08T03:52:00+00:00https://justicehui.github.io/icpc/2021/09/08/BOJ16046<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/16046</li> </ul> <h3 id="문제-출처">문제 출처</h3> <ul> <li>2018 NAIPC G번</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>Matroid Intersection</li> </ul> <h3 id="풀이">풀이</h3> <p>무향 연결 그래프 $G(V, E)$에서 $\mathcal{I}_G = \lbrace I : I \subset E, E\setminus I\text{ can connects all vertex in } G \rbrace$라고 정의하면 $\mathcal{M} = (S, \mathcal{I}_G)$는 Matroid입니다.</p> <p>$\mathcal{I}<em>{G}’ = \lbrace I : I \subset E, E\setminus I\text{ can connects all vertex in } G \text{ using edge colored with R or G} \rbrace$, $\mathcal{I}</em>{G}’’ = \lbrace I : I \subset E, E\setminus I\text{ can connects all vertex in } G \text{ using edge colored with G or B} \rbrace$라고 정의합시다. $\mathcal{M}’ = (S, \mathcal{I}_G’)$와 $\mathcal{M}’’ = (S, \mathcal{I}_G’’)$ 역시 Matroid입니다.</p> <p>그러므로 $\mathcal{M}’$과 $\mathcal{M}’‘$의 Cardinality가 $K$인 Maximum Weight Common Independent Set을 구하면 됩니다.</p> <h3 id="전체-코드">전체 코드</h3> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; #define x first #define y second #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) #define IDX(v, x) (lower_bound(all(v), x) - v.begin()) </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">using</span> <span class="n">uint</span> <span class="o">=</span> <span class="kt">unsigned</span><span class="p">;</span> <span class="k">using</span> <span class="n">ll</span> <span class="o">=</span> <span class="kt">long</span> <span class="kt">long</span><span class="p">;</span> <span class="k">using</span> <span class="n">ull</span> <span class="o">=</span> <span class="kt">unsigned</span> <span class="kt">long</span> <span class="kt">long</span><span class="p">;</span> <span class="k">using</span> <span class="n">PII</span> <span class="o">=</span> <span class="n">pair</span><span class="o">&lt;</span><span class="kt">int</span><span class="p">,</span> <span class="kt">int</span><span class="o">&gt;</span><span class="p">;</span> <span class="k">template</span><span class="o">&lt;</span><span class="kt">size_t</span> <span class="n">vertex_cnt</span><span class="p">&gt;</span> <span class="k">struct</span> <span class="nc">UnionFind</span><span class="p">{</span> <span class="n">array</span><span class="o">&lt;</span><span class="kt">int</span><span class="p">,</span> <span class="n">vertex_cnt</span><span class="o">&gt;</span> <span class="n">P</span><span class="p">;</span> <span class="n">UnionFind</span><span class="p">(){</span> <span class="n">clear</span><span class="p">();</span> <span class="p">}</span> <span class="kt">void</span> <span class="n">clear</span><span class="p">(){</span> <span class="n">iota</span><span class="p">(</span><span class="n">all</span><span class="p">(</span><span class="n">P</span><span class="p">),</span> <span class="mi">0</span><span class="p">);</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">find</span><span class="p">(</span><span class="kt">int</span> <span class="n">v</span><span class="p">){</span> <span class="k">return</span> <span class="n">v</span> <span class="o">==</span> <span class="n">P</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">?</span> <span class="n">v</span> <span class="o">:</span> <span class="n">P</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="n">find</span><span class="p">(</span><span class="n">P</span><span class="p">[</span><span class="n">v</span><span class="p">]);</span> <span class="p">}</span> <span class="kt">bool</span> <span class="n">merge</span><span class="p">(</span><span class="kt">int</span> <span class="n">u</span><span class="p">,</span> <span class="kt">int</span> <span class="n">v</span><span class="p">){</span> <span class="n">u</span> <span class="o">=</span> <span class="n">find</span><span class="p">(</span><span class="n">u</span><span class="p">);</span> <span class="n">v</span> <span class="o">=</span> <span class="n">find</span><span class="p">(</span><span class="n">v</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">u</span> <span class="o">==</span> <span class="n">v</span><span class="p">)</span> <span class="k">return</span> <span class="nb">false</span><span class="p">;</span> <span class="n">P</span><span class="p">[</span><span class="n">u</span><span class="p">]</span> <span class="o">=</span> <span class="n">v</span><span class="p">;</span> <span class="k">return</span> <span class="nb">true</span><span class="p">;</span> <span class="p">}</span> <span class="p">};</span> <span class="k">template</span><span class="o">&lt;</span><span class="kt">size_t</span> <span class="n">vertex_cnt</span><span class="p">&gt;</span> <span class="k">struct</span> <span class="nc">GraphicMatroid</span><span class="p">{</span> <span class="n">UnionFind</span><span class="o">&lt;</span><span class="n">vertex_cnt</span><span class="o">&gt;</span> <span class="n">uf</span><span class="p">;</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">PII</span><span class="o">&gt;</span> <span class="n">edges</span><span class="p">;</span> <span class="kt">bool</span> <span class="n">noCycle</span><span class="p">;</span> <span class="n">GraphicMatroid</span><span class="p">(){</span> <span class="n">clear</span><span class="p">();</span> <span class="p">}</span> <span class="n">GraphicMatroid</span><span class="p">(</span><span class="k">const</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">PII</span><span class="o">&gt;</span> <span class="o">&amp;</span><span class="n">edges</span><span class="p">)</span> <span class="o">:</span> <span class="n">edges</span><span class="p">(</span><span class="n">edges</span><span class="p">)</span> <span class="p">{</span> <span class="n">clear</span><span class="p">();</span> <span class="p">}</span> <span class="kt">void</span> <span class="n">clear</span><span class="p">(){</span> <span class="n">uf</span><span class="p">.</span><span class="n">clear</span><span class="p">();</span> <span class="n">noCycle</span> <span class="o">=</span> <span class="nb">true</span><span class="p">;</span> <span class="p">}</span> <span class="kt">bool</span> <span class="n">check</span><span class="p">(){</span> <span class="k">return</span> <span class="n">noCycle</span><span class="p">;</span> <span class="p">}</span> <span class="kt">void</span> <span class="n">add</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="p">){</span> <span class="n">uf</span><span class="p">.</span><span class="n">merge</span><span class="p">(</span><span class="n">edges</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">x</span><span class="p">,</span> <span class="n">edges</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">y</span><span class="p">);</span> <span class="p">}</span> <span class="p">};</span> <span class="k">template</span><span class="o">&lt;</span><span class="kt">size_t</span> <span class="n">vertex_cnt</span><span class="p">&gt;</span> <span class="k">struct</span> <span class="nc">GraphicMatroidDual</span><span class="p">{</span> <span class="kt">int</span> <span class="n">n</span><span class="p">;</span> <span class="c1">// vertex</span> <span class="n">UnionFind</span><span class="o">&lt;</span><span class="n">vertex_cnt</span><span class="o">&gt;</span> <span class="n">uf</span><span class="p">;</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">PII</span><span class="o">&gt;</span> <span class="n">edges</span><span class="p">;</span> <span class="n">GraphicMatroidDual</span><span class="p">(){</span> <span class="n">clear</span><span class="p">();</span> <span class="p">}</span> <span class="n">GraphicMatroidDual</span><span class="p">(</span><span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="k">const</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">PII</span><span class="o">&gt;</span> <span class="o">&amp;</span><span class="n">edges</span><span class="p">)</span> <span class="o">:</span> <span class="n">n</span><span class="p">(</span><span class="n">n</span><span class="p">),</span> <span class="n">edges</span><span class="p">(</span><span class="n">edges</span><span class="p">)</span> <span class="p">{</span> <span class="n">clear</span><span class="p">();</span> <span class="p">}</span> <span class="kt">void</span> <span class="n">clear</span><span class="p">(){</span> <span class="n">uf</span><span class="p">.</span><span class="n">clear</span><span class="p">();</span> <span class="p">}</span> <span class="kt">bool</span> <span class="n">check</span><span class="p">(){</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="n">uf</span><span class="p">.</span><span class="n">find</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span> <span class="o">!=</span> <span class="n">uf</span><span class="p">.</span><span class="n">find</span><span class="p">(</span><span class="n">i</span><span class="p">))</span> <span class="k">return</span> <span class="nb">false</span><span class="p">;</span> <span class="k">return</span> <span class="nb">true</span><span class="p">;</span> <span class="p">}</span> <span class="kt">void</span> <span class="n">add</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="p">){</span> <span class="n">uf</span><span class="p">.</span><span class="n">merge</span><span class="p">(</span><span class="n">edges</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">x</span><span class="p">,</span> <span class="n">edges</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">y</span><span class="p">);</span> <span class="p">}</span> <span class="p">};</span> <span class="k">template</span><span class="o">&lt;</span><span class="k">typename</span> <span class="nc">M1</span><span class="p">,</span> <span class="k">typename</span> <span class="nc">M2</span><span class="p">,</span> <span class="k">typename</span> <span class="nc">weight_t</span><span class="p">,</span> <span class="n">weight_t</span> <span class="n">max_w</span><span class="p">&gt;</span> <span class="k">struct</span> <span class="nc">MatroidIntersection</span><span class="p">{</span> <span class="kt">int</span> <span class="n">n</span><span class="p">;</span> <span class="c1">// 0 ~ n-1 : elements of S, n : source, n+1 : sink</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">char</span><span class="o">&gt;</span> <span class="n">use</span><span class="p">;</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">weight_t</span><span class="o">&gt;</span> <span class="n">w</span><span class="p">;</span> <span class="n">M1</span> <span class="n">m1</span><span class="p">;</span> <span class="n">M2</span> <span class="n">m2</span><span class="p">;</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">vector</span><span class="o">&lt;</span><span class="n">pair</span><span class="o">&lt;</span><span class="kt">int</span><span class="p">,</span> <span class="n">weight_t</span><span class="o">&gt;&gt;&gt;</span> <span class="n">g</span><span class="p">;</span> <span class="n">MatroidIntersection</span><span class="p">()</span> <span class="o">=</span> <span class="k">delete</span><span class="p">;</span> <span class="n">MatroidIntersection</span><span class="p">(</span><span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="n">M1</span> <span class="n">m1</span><span class="p">,</span> <span class="n">M2</span> <span class="n">m2</span><span class="p">,</span> <span class="k">const</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">weight_t</span><span class="o">&gt;</span> <span class="o">&amp;</span><span class="n">w</span><span class="p">)</span> <span class="o">:</span> <span class="n">n</span><span class="p">(</span><span class="n">n</span><span class="p">),</span> <span class="n">m1</span><span class="p">(</span><span class="n">m1</span><span class="p">),</span> <span class="n">m2</span><span class="p">(</span><span class="n">m2</span><span class="p">),</span> <span class="n">w</span><span class="p">(</span><span class="n">w</span><span class="p">),</span> <span class="n">use</span><span class="p">(</span><span class="n">n</span><span class="p">),</span> <span class="n">g</span><span class="p">(</span><span class="n">n</span><span class="o">+</span><span class="mi">2</span><span class="p">)</span> <span class="p">{}</span> <span class="kt">bool</span> <span class="n">SPFA</span><span class="p">(</span><span class="kt">int</span> <span class="n">S</span><span class="p">,</span> <span class="kt">int</span> <span class="n">T</span><span class="p">){</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">char</span><span class="o">&gt;</span> <span class="n">inq</span><span class="p">(</span><span class="n">n</span><span class="o">+</span><span class="mi">2</span><span class="p">,</span> <span class="nb">false</span><span class="p">);</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">prv</span><span class="p">(</span><span class="n">n</span><span class="o">+</span><span class="mi">2</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">);</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">weight_t</span><span class="o">&gt;</span> <span class="n">dst</span><span class="p">(</span><span class="n">n</span><span class="o">+</span><span class="mi">2</span><span class="p">,</span> <span class="n">max_w</span><span class="o">*</span><span class="p">(</span><span class="n">max_w</span><span class="o">+</span><span class="mi">1</span><span class="p">)</span><span class="o">*</span><span class="n">n</span><span class="p">);</span> <span class="n">queue</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">q</span><span class="p">;</span> <span class="n">q</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">S</span><span class="p">);</span> <span class="n">dst</span><span class="p">[</span><span class="n">S</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">inq</span><span class="p">[</span><span class="n">S</span><span class="p">]</span> <span class="o">=</span> <span class="nb">true</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">q</span><span class="p">.</span><span class="n">size</span><span class="p">()){</span> <span class="kt">int</span> <span class="n">v</span> <span class="o">=</span> <span class="n">q</span><span class="p">.</span><span class="n">front</span><span class="p">();</span> <span class="n">q</span><span class="p">.</span><span class="n">pop</span><span class="p">();</span> <span class="n">inq</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="nb">false</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">g</span><span class="p">[</span><span class="n">v</span><span class="p">]){</span> <span class="k">if</span><span class="p">(</span><span class="n">dst</span><span class="p">[</span><span class="n">i</span><span class="p">.</span><span class="n">x</span><span class="p">]</span> <span class="o">&gt;</span> <span class="n">dst</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">+</span> <span class="n">i</span><span class="p">.</span><span class="n">y</span><span class="p">){</span> <span class="n">dst</span><span class="p">[</span><span class="n">i</span><span class="p">.</span><span class="n">x</span><span class="p">]</span> <span class="o">=</span> <span class="n">dst</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">+</span> <span class="n">i</span><span class="p">.</span><span class="n">y</span><span class="p">;</span> <span class="n">prv</span><span class="p">[</span><span class="n">i</span><span class="p">.</span><span class="n">x</span><span class="p">]</span> <span class="o">=</span> <span class="n">v</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">inq</span><span class="p">[</span><span class="n">i</span><span class="p">.</span><span class="n">x</span><span class="p">])</span> <span class="n">inq</span><span class="p">[</span><span class="n">i</span><span class="p">.</span><span class="n">x</span><span class="p">]</span> <span class="o">=</span> <span class="nb">true</span><span class="p">,</span> <span class="n">q</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">i</span><span class="p">.</span><span class="n">x</span><span class="p">);</span> <span class="p">}</span> <span class="p">}</span> <span class="p">}</span> <span class="k">if</span><span class="p">(</span><span class="n">prv</span><span class="p">[</span><span class="n">T</span><span class="p">]</span> <span class="o">==</span> <span class="o">-</span><span class="mi">1</span><span class="p">)</span> <span class="k">return</span> <span class="nb">false</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="n">T</span><span class="p">;</span> <span class="n">i</span><span class="o">!=</span><span class="n">S</span><span class="p">;</span> <span class="n">i</span><span class="o">=</span><span class="n">prv</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="k">if</span><span class="p">(</span><span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span><span class="p">)</span> <span class="n">use</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">^=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">return</span> <span class="nb">true</span><span class="p">;</span> <span class="p">}</span> <span class="kt">bool</span> <span class="n">augmentPath</span><span class="p">(){</span> <span class="k">const</span> <span class="kt">int</span> <span class="n">S</span> <span class="o">=</span> <span class="n">n</span><span class="p">,</span> <span class="n">T</span> <span class="o">=</span> <span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="o">+</span><span class="mi">2</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">g</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">clear</span><span class="p">();</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">use</span><span class="p">[</span><span class="n">i</span><span class="p">]){</span> <span class="n">use</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="nb">true</span><span class="p">;</span> <span class="n">m1</span><span class="p">.</span><span class="n">clear</span><span class="p">();</span> <span class="n">m2</span><span class="p">.</span><span class="n">clear</span><span class="p">();</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">k</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">k</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span> <span class="n">k</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">use</span><span class="p">[</span><span class="n">k</span><span class="p">])</span> <span class="n">m1</span><span class="p">.</span><span class="n">add</span><span class="p">(</span><span class="n">k</span><span class="p">),</span> <span class="n">m2</span><span class="p">.</span><span class="n">add</span><span class="p">(</span><span class="n">k</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">m1</span><span class="p">.</span><span class="n">check</span><span class="p">())</span> <span class="n">g</span><span class="p">[</span><span class="n">S</span><span class="p">].</span><span class="n">emplace_back</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="o">-</span><span class="n">w</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">*</span><span class="n">max_w</span><span class="o">+</span><span class="mi">1</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">m2</span><span class="p">.</span><span class="n">check</span><span class="p">())</span> <span class="n">g</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">emplace_back</span><span class="p">(</span><span class="n">T</span><span class="p">,</span> <span class="mi">1</span><span class="p">);</span> <span class="n">use</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="nb">false</span><span class="p">;</span> <span class="p">}</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">use</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&amp;&amp;</span> <span class="o">!</span><span class="n">use</span><span class="p">[</span><span class="n">j</span><span class="p">]){</span> <span class="n">use</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="nb">false</span><span class="p">;</span> <span class="n">use</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="nb">true</span><span class="p">;</span> <span class="n">m1</span><span class="p">.</span><span class="n">clear</span><span class="p">();</span> <span class="n">m2</span><span class="p">.</span><span class="n">clear</span><span class="p">();</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">k</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">k</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span> <span class="n">k</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">use</span><span class="p">[</span><span class="n">k</span><span class="p">])</span> <span class="n">m1</span><span class="p">.</span><span class="n">add</span><span class="p">(</span><span class="n">k</span><span class="p">),</span> <span class="n">m2</span><span class="p">.</span><span class="n">add</span><span class="p">(</span><span class="n">k</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">m1</span><span class="p">.</span><span class="n">check</span><span class="p">())</span> <span class="n">g</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">emplace_back</span><span class="p">(</span><span class="n">j</span><span class="p">,</span> <span class="o">-</span><span class="n">w</span><span class="p">[</span><span class="n">j</span><span class="p">]</span><span class="o">*</span><span class="n">max_w</span><span class="o">+</span><span class="mi">1</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">m2</span><span class="p">.</span><span class="n">check</span><span class="p">())</span> <span class="n">g</span><span class="p">[</span><span class="n">j</span><span class="p">].</span><span class="n">emplace_back</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">w</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">*</span><span class="n">max_w</span><span class="o">+</span><span class="mi">1</span><span class="p">);</span> <span class="n">use</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="nb">true</span><span class="p">;</span> <span class="n">use</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="nb">false</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> <span class="p">}</span> <span class="k">return</span> <span class="n">SPFA</span><span class="p">(</span><span class="n">S</span><span class="p">,</span> <span class="n">T</span><span class="p">);</span> <span class="p">}</span> <span class="n">tuple</span><span class="o">&lt;</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="p">,</span> <span class="kt">int</span><span class="p">,</span> <span class="n">weight_t</span><span class="o">&gt;</span> <span class="n">solve</span><span class="p">(){</span> <span class="kt">int</span> <span class="n">cardinality</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">weight_t</span> <span class="n">weight</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="n">m1</span><span class="p">.</span><span class="n">check</span><span class="p">(</span><span class="n">i</span><span class="p">)</span> <span class="o">&amp;&amp;</span> <span class="n">m2</span><span class="p">.</span><span class="n">check</span><span class="p">(</span><span class="n">i</span><span class="p">))</span> <span class="n">use</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">,</span> <span class="n">m1</span><span class="p">.</span><span class="n">add</span><span class="p">(</span><span class="n">i</span><span class="p">),</span> <span class="n">m2</span><span class="p">.</span><span class="n">add</span><span class="p">(</span><span class="n">i</span><span class="p">);</span> <span class="k">while</span><span class="p">(</span><span class="n">augmentPath</span><span class="p">())</span> <span class="n">cardinality</span><span class="o">++</span><span class="p">;</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">ans</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="n">use</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="n">ans</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">i</span><span class="p">),</span> <span class="n">weight</span> <span class="o">+=</span> <span class="n">w</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> <span class="k">return</span> <span class="n">make_tuple</span><span class="p">(</span><span class="n">ans</span><span class="p">,</span> <span class="n">cardinality</span><span class="p">,</span> <span class="n">weight</span><span class="p">);</span> <span class="p">}</span> <span class="p">};</span> <span class="k">template</span><span class="o">&lt;</span><span class="kt">size_t</span> <span class="n">vertex_cnt</span><span class="p">&gt;</span> <span class="k">struct</span> <span class="nc">GraphicMatroidDual2</span><span class="p">{</span> <span class="kt">int</span> <span class="n">n</span><span class="p">;</span> <span class="c1">// vertex</span> <span class="n">UnionFind</span><span class="o">&lt;</span><span class="n">vertex_cnt</span><span class="o">&gt;</span> <span class="n">uf</span><span class="p">;</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">PII</span><span class="o">&gt;</span> <span class="n">edges</span><span class="p">;</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">char</span><span class="o">&gt;</span> <span class="n">color</span><span class="p">;</span> <span class="kt">char</span> <span class="n">c1</span><span class="p">,</span> <span class="n">c2</span><span class="p">;</span> <span class="n">GraphicMatroidDual2</span><span class="p">(){</span> <span class="n">clear</span><span class="p">();</span> <span class="p">}</span> <span class="n">GraphicMatroidDual2</span><span class="p">(</span><span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="k">const</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">PII</span><span class="o">&gt;</span> <span class="o">&amp;</span><span class="n">edges</span><span class="p">)</span> <span class="o">:</span> <span class="n">n</span><span class="p">(</span><span class="n">n</span><span class="p">),</span> <span class="n">edges</span><span class="p">(</span><span class="n">edges</span><span class="p">)</span> <span class="p">{</span> <span class="n">clear</span><span class="p">();</span> <span class="p">}</span> <span class="kt">void</span> <span class="n">set</span><span class="p">(</span><span class="kt">char</span> <span class="n">_c1</span><span class="p">,</span> <span class="kt">char</span> <span class="n">_c2</span><span class="p">,</span> <span class="k">const</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">char</span><span class="o">&gt;</span> <span class="n">_color</span><span class="p">){</span> <span class="n">c1</span> <span class="o">=</span> <span class="n">_c1</span><span class="p">;</span> <span class="n">c2</span> <span class="o">=</span> <span class="n">_c2</span><span class="p">;</span> <span class="n">color</span> <span class="o">=</span> <span class="n">_color</span><span class="p">;</span> <span class="p">}</span> <span class="kt">void</span> <span class="n">clear</span><span class="p">(){</span> <span class="n">uf</span><span class="p">.</span><span class="n">clear</span><span class="p">();</span> <span class="p">}</span> <span class="kt">bool</span> <span class="n">check</span><span class="p">(){</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="n">uf</span><span class="p">.</span><span class="n">find</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span> <span class="o">!=</span> <span class="n">uf</span><span class="p">.</span><span class="n">find</span><span class="p">(</span><span class="n">i</span><span class="p">))</span> <span class="k">return</span> <span class="nb">false</span><span class="p">;</span> <span class="k">return</span> <span class="nb">true</span><span class="p">;</span> <span class="p">}</span> <span class="kt">void</span> <span class="n">add</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">color</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="n">c1</span> <span class="o">||</span> <span class="n">color</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="n">c2</span><span class="p">)</span> <span class="n">uf</span><span class="p">.</span><span class="n">merge</span><span class="p">(</span><span class="n">edges</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">x</span><span class="p">,</span> <span class="n">edges</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">y</span><span class="p">);</span> <span class="p">}</span> <span class="p">};</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="kt">int</span> <span class="n">N</span><span class="p">,</span> <span class="n">M</span><span class="p">;</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">N</span> <span class="o">&gt;&gt;</span> <span class="n">M</span><span class="p">;</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">pair</span><span class="o">&lt;</span><span class="kt">int</span><span class="p">,</span> <span class="kt">int</span><span class="o">&gt;&gt;</span> <span class="n">edges</span><span class="p">(</span><span class="n">M</span><span class="p">);</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">w</span><span class="p">(</span><span class="n">M</span><span class="p">);</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">char</span><span class="o">&gt;</span> <span class="n">color</span><span class="p">(</span><span class="n">M</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">M</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">edges</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">x</span> <span class="o">&gt;&gt;</span> <span class="n">edges</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">y</span> <span class="o">&gt;&gt;</span> <span class="n">w</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&gt;&gt;</span> <span class="n">color</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">M</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">edges</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">x</span><span class="o">--</span><span class="p">,</span> <span class="n">edges</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">y</span><span class="o">--</span><span class="p">;</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">res</span><span class="p">(</span><span class="n">M</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">);</span> <span class="n">GraphicMatroidDual2</span><span class="o">&lt;</span><span class="mi">111</span><span class="o">&gt;</span> <span class="n">m1</span><span class="p">(</span><span class="n">N</span><span class="p">,</span> <span class="n">edges</span><span class="p">),</span> <span class="n">m2</span><span class="p">(</span><span class="n">N</span><span class="p">,</span> <span class="n">edges</span><span class="p">);</span> <span class="n">m1</span><span class="p">.</span><span class="n">set</span><span class="p">(</span><span class="sc">'R'</span><span class="p">,</span> <span class="sc">'G'</span><span class="p">,</span> <span class="n">color</span><span class="p">);</span> <span class="n">m2</span><span class="p">.</span><span class="n">set</span><span class="p">(</span><span class="sc">'G'</span><span class="p">,</span> <span class="sc">'B'</span><span class="p">,</span> <span class="n">color</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">M</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">m1</span><span class="p">.</span><span class="n">add</span><span class="p">(</span><span class="n">i</span><span class="p">),</span> <span class="n">m2</span><span class="p">.</span><span class="n">add</span><span class="p">(</span><span class="n">i</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">m1</span><span class="p">.</span><span class="n">check</span><span class="p">()</span> <span class="o">||</span> <span class="o">!</span><span class="n">m2</span><span class="p">.</span><span class="n">check</span><span class="p">()){</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">M</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">res</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&lt;&lt;</span> <span class="s">"</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="p">}</span> <span class="n">MatroidIntersection</span><span class="o">&lt;</span><span class="n">GraphicMatroidDual2</span><span class="o">&lt;</span><span class="mi">111</span><span class="o">&gt;</span><span class="p">,</span> <span class="n">GraphicMatroidDual2</span><span class="o">&lt;</span><span class="mi">111</span><span class="o">&gt;</span><span class="p">,</span> <span class="kt">int</span><span class="p">,</span> <span class="mi">1000</span><span class="o">&gt;</span> <span class="n">mat</span><span class="p">(</span><span class="n">M</span><span class="p">,</span> <span class="n">m1</span><span class="p">,</span> <span class="n">m2</span><span class="p">,</span> <span class="n">w</span><span class="p">);</span> <span class="n">res</span><span class="p">[</span><span class="n">M</span><span class="p">]</span> <span class="o">=</span> <span class="n">accumulate</span><span class="p">(</span><span class="n">all</span><span class="p">(</span><span class="n">w</span><span class="p">),</span> <span class="mi">0</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="n">M</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&gt;=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">--</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">mat</span><span class="p">.</span><span class="n">augmentPath</span><span class="p">())</span> <span class="k">break</span><span class="p">;</span> <span class="n">res</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;</span><span class="n">M</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">mat</span><span class="p">.</span><span class="n">use</span><span class="p">[</span><span class="n">j</span><span class="p">])</span> <span class="n">res</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">+=</span> <span class="n">w</span><span class="p">[</span><span class="n">j</span><span class="p">];</span> <span class="p">}</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">M</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">res</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&lt;&lt;</span> <span class="s">"</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/16046백준21070 Königsberg Bridges2021-09-07T03:32:00+00:002021-09-07T03:32:00+00:00https://justicehui.github.io/ps/2021/09/07/BOJ21070<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/21070</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>BCC</li> </ul> <h3 id="풀이">풀이</h3> <p>단절선만 보면 되므로 BCC를 정점 하나로 압축해서 포레스트로 만듭시다. 트리들을 잘 연결해서 단순 경로로 방문할 수 있는 단절선의 개수를 최대화 해야 합니다.<br /> 잘 생각해보면, 각 트리의 지름들을 쭉 연결하는 것이 최적임을 알 수 있습니다.</p> <h3 id="전체-코드">전체 코드</h3> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; #define x first #define y second #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) #define IDX(v, x) (lower_bound(all(v), x) - v.begin()) </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">using</span> <span class="n">uint</span> <span class="o">=</span> <span class="kt">unsigned</span><span class="p">;</span> <span class="k">using</span> <span class="n">ll</span> <span class="o">=</span> <span class="kt">long</span> <span class="kt">long</span><span class="p">;</span> <span class="k">using</span> <span class="n">ull</span> <span class="o">=</span> <span class="kt">unsigned</span> <span class="kt">long</span> <span class="kt">long</span><span class="p">;</span> <span class="kt">int</span> <span class="n">N</span><span class="p">,</span> <span class="n">M</span><span class="p">,</span> <span class="n">Low</span><span class="p">[</span><span class="mi">1010101</span><span class="p">],</span> <span class="n">In</span><span class="p">[</span><span class="mi">1010101</span><span class="p">],</span> <span class="n">P</span><span class="p">[</span><span class="mi">1010101</span><span class="p">],</span> <span class="n">C</span><span class="p">[</span><span class="mi">1010101</span><span class="p">],</span> <span class="n">D</span><span class="p">[</span><span class="mi">1010101</span><span class="p">],</span> <span class="n">pv</span><span class="p">,</span> <span class="n">col</span><span class="p">,</span> <span class="n">comp</span><span class="p">;</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">G</span><span class="p">[</span><span class="mi">1010101</span><span class="p">],</span> <span class="n">E</span><span class="p">[</span><span class="mi">1010101</span><span class="p">];</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">T</span><span class="p">[</span><span class="mi">1010101</span><span class="p">];</span> <span class="kt">void</span> <span class="nf">Tarjan</span><span class="p">(</span><span class="kt">int</span> <span class="n">v</span><span class="p">,</span> <span class="kt">int</span> <span class="n">b</span><span class="o">=-</span><span class="mi">1</span><span class="p">){</span> <span class="n">In</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="n">Low</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="o">++</span><span class="n">pv</span><span class="p">;</span> <span class="n">P</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="n">b</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">G</span><span class="p">[</span><span class="n">v</span><span class="p">]){</span> <span class="k">if</span><span class="p">(</span><span class="n">i</span> <span class="o">==</span> <span class="n">b</span><span class="p">)</span> <span class="k">continue</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">In</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="n">Low</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="n">min</span><span class="p">(</span><span class="n">Low</span><span class="p">[</span><span class="n">v</span><span class="p">],</span> <span class="n">In</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span> <span class="k">else</span><span class="p">{</span> <span class="n">Tarjan</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">v</span><span class="p">);</span> <span class="n">Low</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="n">min</span><span class="p">(</span><span class="n">Low</span><span class="p">[</span><span class="n">v</span><span class="p">],</span> <span class="n">Low</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span> <span class="k">if</span><span class="p">(</span><span class="n">Low</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&gt;</span> <span class="n">In</span><span class="p">[</span><span class="n">v</span><span class="p">])</span> <span class="n">E</span><span class="p">[</span><span class="n">v</span><span class="p">].</span><span class="n">push_back</span><span class="p">(</span><span class="n">i</span><span class="p">),</span> <span class="n">E</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">push_back</span><span class="p">(</span><span class="n">v</span><span class="p">);</span> <span class="p">}</span> <span class="p">}</span> <span class="p">}</span> <span class="kt">void</span> <span class="nf">DFS</span><span class="p">(</span><span class="kt">int</span> <span class="n">v</span><span class="p">,</span> <span class="kt">int</span> <span class="n">color</span><span class="p">){</span> <span class="n">C</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="n">color</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">G</span><span class="p">[</span><span class="n">v</span><span class="p">]){</span> <span class="k">if</span><span class="p">(</span><span class="n">C</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">||</span> <span class="n">binary_search</span><span class="p">(</span><span class="n">all</span><span class="p">(</span><span class="n">E</span><span class="p">[</span><span class="n">v</span><span class="p">]),</span> <span class="n">i</span><span class="p">))</span> <span class="k">continue</span><span class="p">;</span> <span class="n">DFS</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">color</span><span class="p">);</span> <span class="p">}</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">N</span> <span class="o">&gt;&gt;</span> <span class="n">M</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">M</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="kt">int</span> <span class="n">s</span><span class="p">,</span> <span class="n">e</span><span class="p">;</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">s</span> <span class="o">&gt;&gt;</span> <span class="n">e</span><span class="p">;</span> <span class="n">s</span><span class="o">++</span><span class="p">;</span> <span class="n">e</span><span class="o">++</span><span class="p">;</span> <span class="n">G</span><span class="p">[</span><span class="n">s</span><span class="p">].</span><span class="n">push_back</span><span class="p">(</span><span class="n">e</span><span class="p">);</span> <span class="n">G</span><span class="p">[</span><span class="n">e</span><span class="p">].</span><span class="n">push_back</span><span class="p">(</span><span class="n">s</span><span class="p">);</span> <span class="p">}</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">N</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">In</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="n">Tarjan</span><span class="p">(</span><span class="n">i</span><span class="p">),</span> <span class="n">comp</span><span class="o">++</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">N</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">sort</span><span class="p">(</span><span class="n">all</span><span class="p">(</span><span class="n">E</span><span class="p">[</span><span class="n">i</span><span class="p">]));</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">N</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">C</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="n">DFS</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="o">++</span><span class="n">col</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">N</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">j</span> <span class="o">:</span> <span class="n">E</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="n">T</span><span class="p">[</span><span class="n">C</span><span class="p">[</span><span class="n">i</span><span class="p">]].</span><span class="n">push_back</span><span class="p">(</span><span class="n">C</span><span class="p">[</span><span class="n">j</span><span class="p">]);</span> <span class="p">}</span> <span class="n">memset</span><span class="p">(</span><span class="n">D</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="k">sizeof</span> <span class="n">D</span><span class="p">);</span> <span class="kt">int</span> <span class="n">res</span> <span class="o">=</span> <span class="n">comp</span> <span class="o">-</span> <span class="mi">1</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">s</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">s</span><span class="o">&lt;=</span><span class="n">col</span><span class="p">;</span> <span class="n">s</span><span class="o">++</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">D</span><span class="p">[</span><span class="n">s</span><span class="p">]</span> <span class="o">!=</span> <span class="o">-</span><span class="mi">1</span><span class="p">)</span> <span class="k">continue</span><span class="p">;</span> <span class="n">queue</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">q</span><span class="p">;</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">vec</span><span class="p">;</span> <span class="n">q</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">s</span><span class="p">);</span> <span class="n">D</span><span class="p">[</span><span class="n">s</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">q</span><span class="p">.</span><span class="n">size</span><span class="p">()){</span> <span class="kt">int</span> <span class="n">v</span> <span class="o">=</span> <span class="n">q</span><span class="p">.</span><span class="n">front</span><span class="p">();</span> <span class="n">q</span><span class="p">.</span><span class="n">pop</span><span class="p">();</span> <span class="n">vec</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">v</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">T</span><span class="p">[</span><span class="n">v</span><span class="p">])</span> <span class="k">if</span><span class="p">(</span><span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="o">-</span><span class="mi">1</span><span class="p">)</span> <span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">D</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">+</span> <span class="mi">1</span><span class="p">,</span> <span class="n">q</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">i</span><span class="p">);</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">mx</span> <span class="o">=</span> <span class="n">s</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">vec</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&gt;</span> <span class="n">D</span><span class="p">[</span><span class="n">mx</span><span class="p">])</span> <span class="n">mx</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">vec</span><span class="p">)</span> <span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span> <span class="n">q</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">mx</span><span class="p">);</span> <span class="n">D</span><span class="p">[</span><span class="n">mx</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">q</span><span class="p">.</span><span class="n">size</span><span class="p">()){</span> <span class="kt">int</span> <span class="n">v</span> <span class="o">=</span> <span class="n">q</span><span class="p">.</span><span class="n">front</span><span class="p">();</span> <span class="n">q</span><span class="p">.</span><span class="n">pop</span><span class="p">();</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">T</span><span class="p">[</span><span class="n">v</span><span class="p">])</span> <span class="k">if</span><span class="p">(</span><span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="o">-</span><span class="mi">1</span><span class="p">)</span> <span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">D</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">+</span> <span class="mi">1</span><span class="p">,</span> <span class="n">q</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">i</span><span class="p">);</span> <span class="p">}</span> <span class="n">mx</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">vec</span><span class="p">)</span> <span class="n">mx</span> <span class="o">=</span> <span class="n">max</span><span class="p">(</span><span class="n">mx</span><span class="p">,</span> <span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span> <span class="n">res</span> <span class="o">+=</span> <span class="n">mx</span><span class="p">;</span> <span class="p">}</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">res</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/21070백준16854 편안한 문자열2021-09-06T03:26:00+00:002021-09-06T03:26:00+00:00https://justicehui.github.io/ps/2021/09/06/BOJ16854<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/16854</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>해싱</li> </ul> <h3 id="시간복잡도">시간복잡도</h3> <ul> <li>$O(N^2)$</li> </ul> <h3 id="풀이">풀이</h3> <p>어떤 부분 문자열이 올바른 괄호 문자열인지 판단하는 것은 간단합니다. 대칭 문자열인지 판단하는 방법을 알아봅시다.<br /> 정해는 어떤 똑똑한 방법을 이용하는 것으로 보이지만, 사실 해싱으로 간단하게 판별할 수 있습니다.</p> <p>입력으로 들어온 문자열 $S$와 $S$를 뒤집은 문자열 $S’$의 해시를 전처리하면, 두 문자열의 특정 지점의 부분 문자열이 같은지 확인하는 것으로 대칭 문자열을 판별해낼 수 있습니다. 자세한 방법은 아래 코드를 참고해주세요.</p> <h3 id="전체-코드">전체 코드</h3> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; #define x first #define y second #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) #define IDX(v, x) (lower_bound(all(v), x) - v.begin()) </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">using</span> <span class="n">uint</span> <span class="o">=</span> <span class="kt">unsigned</span><span class="p">;</span> <span class="k">using</span> <span class="n">ll</span> <span class="o">=</span> <span class="kt">long</span> <span class="kt">long</span><span class="p">;</span> <span class="k">using</span> <span class="n">ull</span> <span class="o">=</span> <span class="kt">unsigned</span> <span class="kt">long</span> <span class="kt">long</span><span class="p">;</span> <span class="k">template</span><span class="o">&lt;</span><span class="n">ll</span> <span class="n">P</span><span class="p">,</span> <span class="n">ll</span> <span class="n">M</span><span class="p">&gt;</span> <span class="k">struct</span> <span class="nc">Hashing</span> <span class="p">{</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">ll</span><span class="o">&gt;</span> <span class="n">H</span><span class="p">,</span> <span class="n">B</span><span class="p">;</span> <span class="kt">void</span> <span class="n">build</span><span class="p">(</span><span class="k">const</span> <span class="n">string</span> <span class="o">&amp;</span><span class="n">S</span><span class="p">){</span> <span class="n">H</span><span class="p">.</span><span class="n">resize</span><span class="p">(</span><span class="n">S</span><span class="p">.</span><span class="n">size</span><span class="p">()</span><span class="o">+</span><span class="mi">1</span><span class="p">);</span> <span class="n">B</span><span class="p">.</span><span class="n">resize</span><span class="p">(</span><span class="n">S</span><span class="p">.</span><span class="n">size</span><span class="p">()</span><span class="o">+</span><span class="mi">1</span><span class="p">);</span> <span class="n">B</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">S</span><span class="p">.</span><span class="n">size</span><span class="p">();</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">H</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="p">(</span><span class="n">H</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="o">*</span> <span class="n">P</span> <span class="o">+</span> <span class="n">S</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">])</span> <span class="o">%</span> <span class="n">M</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">S</span><span class="p">.</span><span class="n">size</span><span class="p">();</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">B</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">B</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="o">*</span> <span class="n">P</span> <span class="o">%</span> <span class="n">M</span><span class="p">;</span> <span class="p">}</span> <span class="n">ll</span> <span class="n">get</span><span class="p">(</span><span class="kt">int</span> <span class="n">s</span><span class="p">,</span> <span class="kt">int</span> <span class="n">e</span><span class="p">){</span> <span class="n">ll</span> <span class="n">res</span> <span class="o">=</span> <span class="p">(</span><span class="n">H</span><span class="p">[</span><span class="n">e</span><span class="p">]</span> <span class="o">-</span> <span class="n">H</span><span class="p">[</span><span class="n">s</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="o">*</span> <span class="n">B</span><span class="p">[</span><span class="n">e</span><span class="o">-</span><span class="n">s</span><span class="o">+</span><span class="mi">1</span><span class="p">])</span> <span class="o">%</span> <span class="n">M</span><span class="p">;</span> <span class="k">return</span> <span class="n">res</span> <span class="o">&lt;</span> <span class="mi">0</span> <span class="o">?</span> <span class="n">res</span> <span class="o">+</span> <span class="n">M</span> <span class="o">:</span> <span class="n">res</span><span class="p">;</span> <span class="p">}</span> <span class="p">};</span> <span class="n">Hashing</span><span class="o">&lt;</span><span class="mi">11</span><span class="p">,</span> <span class="mi">998244353</span><span class="o">&gt;</span> <span class="n">H1</span><span class="p">,</span> <span class="n">H3</span><span class="p">;</span> <span class="n">Hashing</span><span class="o">&lt;</span><span class="mi">9</span><span class="p">,</span> <span class="mi">1000000007</span><span class="o">&gt;</span> <span class="n">H2</span><span class="p">,</span> <span class="n">H4</span><span class="p">;</span> <span class="kt">int</span> <span class="n">N</span><span class="p">;</span> <span class="n">string</span> <span class="n">S</span><span class="p">,</span> <span class="n">T</span><span class="p">;</span> <span class="kt">bool</span> <span class="nf">Check</span><span class="p">(</span><span class="kt">int</span> <span class="n">s</span><span class="p">,</span> <span class="kt">int</span> <span class="n">e</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">H1</span><span class="p">.</span><span class="n">get</span><span class="p">(</span><span class="n">s</span><span class="p">,</span> <span class="n">e</span><span class="p">)</span> <span class="o">!=</span> <span class="n">H3</span><span class="p">.</span><span class="n">get</span><span class="p">(</span><span class="n">N</span><span class="o">-</span><span class="n">e</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">N</span><span class="o">-</span><span class="n">s</span><span class="o">+</span><span class="mi">1</span><span class="p">))</span> <span class="k">return</span> <span class="nb">false</span><span class="p">;</span> <span class="k">return</span> <span class="n">H2</span><span class="p">.</span><span class="n">get</span><span class="p">(</span><span class="n">s</span><span class="p">,</span> <span class="n">e</span><span class="p">)</span> <span class="o">==</span> <span class="n">H4</span><span class="p">.</span><span class="n">get</span><span class="p">(</span><span class="n">N</span><span class="o">-</span><span class="n">e</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">N</span><span class="o">-</span><span class="n">s</span><span class="o">+</span><span class="mi">1</span><span class="p">);</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">S</span><span class="p">;</span> <span class="n">T</span> <span class="o">=</span> <span class="n">S</span><span class="p">;</span> <span class="n">N</span> <span class="o">=</span> <span class="n">S</span><span class="p">.</span><span class="n">size</span><span class="p">();</span> <span class="n">H1</span><span class="p">.</span><span class="n">build</span><span class="p">(</span><span class="n">S</span><span class="p">);</span> <span class="n">H2</span><span class="p">.</span><span class="n">build</span><span class="p">(</span><span class="n">S</span><span class="p">);</span> <span class="n">reverse</span><span class="p">(</span><span class="n">all</span><span class="p">(</span><span class="n">T</span><span class="p">));</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="o">&amp;</span><span class="n">c</span> <span class="o">:</span> <span class="n">T</span><span class="p">)</span> <span class="n">c</span> <span class="o">=</span> <span class="n">c</span> <span class="o">==</span> <span class="sc">'('</span> <span class="o">?</span> <span class="sc">')'</span> <span class="o">:</span> <span class="sc">'('</span><span class="p">;</span> <span class="n">H3</span><span class="p">.</span><span class="n">build</span><span class="p">(</span><span class="n">T</span><span class="p">);</span> <span class="n">H4</span><span class="p">.</span><span class="n">build</span><span class="p">(</span><span class="n">T</span><span class="p">);</span> <span class="n">S</span> <span class="o">=</span> <span class="s">"#"</span> <span class="o">+</span> <span class="n">S</span><span class="p">;</span> <span class="kt">int</span> <span class="n">res</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">N</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="kt">int</span> <span class="n">now</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="n">i</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;=</span><span class="n">N</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">S</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">==</span> <span class="sc">'('</span><span class="p">)</span> <span class="n">now</span><span class="o">++</span><span class="p">;</span> <span class="k">else</span> <span class="k">if</span><span class="p">(</span><span class="o">--</span><span class="n">now</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="p">)</span> <span class="k">break</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">now</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="n">res</span> <span class="o">+=</span> <span class="n">Check</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">j</span><span class="p">);</span> <span class="p">}</span> <span class="p">}</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">res</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/16854백준1587 이분 매칭2021-09-05T03:14:00+00:002021-09-05T03:14:00+00:00https://justicehui.github.io/ps/2021/09/05/BOJ1587<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/1587</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>DP</li> <li> <s>General Matching</s> </li> </ul> <h3 id="시간복잡도">시간복잡도</h3> <ul> <li>$O(\vert V \vert)$</li> </ul> <h3 id="풀이">풀이</h3> <p>$D(i, j) := $ 왼쪽 $1\cdots i$번 정점, 오른쪽 $1\cdots j$번 정점만 고려했을 때의 최대 매칭이라고 정의합시다. 상태 전이는 쉽게 구할 수 있습니다.</p> <ul> <li>$i-1, i$ 매칭 : $D(i, j) \leftarrow D(i-2, j) + 1$</li> <li>$j-1, j$ 매칭 : $D(i, j) \leftarrow D(i, j-2) + 1$</li> <li>$i-1, i, j-1, j$ 매칭 : $D(i, j) \leftarrow D(i-2, j-2) + 2$</li> <li>$i, j$ 매칭 : $D(i, j) \leftarrow D(i-1, j-1) + 1$</li> </ul> <p>혹은 그래프의 크기가 작다는 점을 이용해 Blossom Algorithm을 이용해서 General Matching을 구해도 됩니다.</p> <h3 id="전체-코드">전체 코드</h3> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="kt">int</span> <span class="n">N</span><span class="p">,</span> <span class="n">M</span><span class="p">,</span> <span class="n">K</span><span class="p">,</span> <span class="n">G</span><span class="p">[</span><span class="mi">1010</span><span class="p">][</span><span class="mi">1010</span><span class="p">],</span> <span class="n">D</span><span class="p">[</span><span class="mi">1010</span><span class="p">][</span><span class="mi">1010</span><span class="p">],</span> <span class="n">R</span><span class="p">;</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">N</span> <span class="o">&gt;&gt;</span> <span class="n">M</span> <span class="o">&gt;&gt;</span> <span class="n">K</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">,</span><span class="n">s</span><span class="p">,</span><span class="n">e</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">K</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">s</span> <span class="o">&gt;&gt;</span> <span class="n">e</span><span class="p">,</span> <span class="n">G</span><span class="p">[</span><span class="n">s</span><span class="p">][</span><span class="n">e</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">N</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;=</span><span class="n">M</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">i</span> <span class="o">&gt;=</span> <span class="mi">2</span><span class="p">)</span> <span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">max</span><span class="p">(</span><span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">],</span> <span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">2</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">+</span> <span class="mi">1</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">j</span> <span class="o">&gt;=</span> <span class="mi">2</span><span class="p">)</span> <span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">max</span><span class="p">(</span><span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">],</span> <span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="o">-</span><span class="mi">2</span><span class="p">]</span> <span class="o">+</span> <span class="mi">1</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">i</span> <span class="o">&gt;=</span> <span class="mi">2</span> <span class="o">&amp;&amp;</span> <span class="n">j</span> <span class="o">&gt;=</span> <span class="mi">2</span><span class="p">)</span> <span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">max</span><span class="p">(</span><span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">],</span> <span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">2</span><span class="p">][</span><span class="n">j</span><span class="o">-</span><span class="mi">2</span><span class="p">]</span> <span class="o">+</span> <span class="mi">2</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">G</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">])</span> <span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">max</span><span class="p">(</span><span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">],</span> <span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">j</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="mi">1</span><span class="p">);</span> <span class="n">R</span> <span class="o">=</span> <span class="n">max</span><span class="p">(</span><span class="n">R</span><span class="p">,</span> <span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]);</span> <span class="p">}</span> <span class="p">}</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">R</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/1587