くぷらーと

くぷらーと

ABC355 D-Intersecting Intervals (C++)

検討解説を見ながら書いたはいいものの、WA*18が消えず沼り散らかしたので覚書です。 以下はWAのコードですが、Nがint型なので、Nが大きいと N * (N - 1) がオーバーフローします。 #include <bits/stdc++.h>using namespace std;int main() { int N; cin >> N; vector<int> l(N); vector<int> r(N); for (int i = 0; i <

くぷらーと

    • ABC367 C-Enumerate Sequences (C++)

      検討コンテスト中は再帰で書こうとしましたがぐちゃぐちゃになり2完で終わりました。再帰の模範解答は公式解説に譲るとして、コンテスト後に自力で解いた解法は6進数に変換して数列を列挙する方法です。 回答#include <bits/stdc++.h>using namespace std;// 10→6進数変換string t_to_s (int n) { string n_s = ""; while (n > 0) { n_s += to_string

      くぷらーと

      • ABC304 C-Virus (C++)

        検討人1の感染者から距離D以内にいる人は感染し、そして感染した人の距離D以内にいる人にまた感染します。人1からの深さ優先探索で解きました。 回答#include <bits/stdc++.h>using namespace std;set<int> searched;void DFS (vector<vector<int>> &branch, int now) { searched.insert(now); for (auto b : branch[now])

        くぷらーと

        • ABC362 D-Shortest Path 3 (C++)

          検討DFSとかで書けないかなといじいじしたもののさっぱり分からず、解説を読んでダイクストラ法の存在を知りました。回答に当たっては下記サイトを大いに参考にさせていただきました。 回答#include <bits/stdc++.h>using namespace std;struct p { int dest; int val;};int main() { int N, M; cin >> N >> M; vector<int> vertex(N+1);

          くぷらーと

        ABC355 D-Intersecting Intervals (C++)

        くぷらーと

          ABC311 C-Find it! (C++)

          検討ありうる経路について考えていたところ、制約から「すべての条件に行先が存在する」、すなわち、「行き止まりが無い」ことに気付きました。つまりどの頂点から出発してもいずれはループ（問題文でいう有向閉路）にたどり着くので、「(1)適当な頂点から出発して、(2)経路を記録していって、(3)ループに突入した時点で処理を打ち切って、(4)ループ部を出力する」といった構成にしようと考えました。 回答#include <bits/stdc++.h>using namespace std;

          くぷらーと

          ABC311 C-Find it! (C++)

          くぷらーと