Pure全体感想62分6完(1ペナルティ)で88位でした。先週から、大体わかってから詰め切るまでの手際の良さを重視して練習していますが、なかなか。Fのサイクル検出などは有名アルゴリズムだと思うのですが、考えながら初実装する形だとどうにもある程度時間がかかってしまいますね。何はともあれ、十分時間を余して6完できたので良かったです。最近、大きな後悔を残すコンテストが多かったので。iter)とbool値のsumでOKです(sumをとるときにintにキャストされる)。地味に最近まで意識していなかった。通りくらいしかないので、この状態に対して何かを計算すると考えます。それぞれの状態から、宝箱1つ追加したときの遷移を考えると、dp更新していけます。dpなどと呼ぶようです。np困難(numpyで簡潔に書きにくい)ことが多いです。上手く扱っている人が居たら真似をしたいなあ。dp[n]+A)と書きたい感じですが、複数箇所を並列更新するときに同一箇所を参照しているとうまく対応してくれないんですよね。Pure誘導部分グラフとか難しそうなことを言い出しいて、手が出ない層も多いのかなと思っていましたが、正解者数が最近の問題Fの中では最多ですか?予想よりもだいぶ正解者が多かったです。手に入れたいものはサイクルであることが分かります。サイクルの関係者に制限した誘導部分グラフが条件を満たすとは限りません。全ての頂点を選んだ場合がそのような例になっています。このような場合には、頂点が全てサイクルの一部になっていることを利用すると、条件を満たしていない場合にはより小さなサイクルが見つかります。1つのサイクルから初めて、「サイクルと関係のない辺があればサイクルを小さくする」を繰り返します。「サイクルが条件を満たしていないなら必ず行ってサイクルを小さくできる」ことから、この操作をやりきった時点で所望のサイクルが手に入ります。実装のための課題は以下の通りです。少なくとも1つのサイクルがあるかどうかを判定する。存在する場合には具体的に見つける。サイクルに余分な辺がある限り、上述の通りサイクルを小さくする。アルゴリズム」くらいでググるといくらでも出てくる有名アルゴリズムです。向かう辺も合わせて消して、次数を更新)。