問題 E: 宝くじ - 東京大学プログラミングコンテスト2014 | AtCoder 解法 yosupo 先生のコードを写経した。Trie 木を作って、その桁で終わるくじの当選金と、その桁より後ろの桁で終わるくじの当選金の最高値をそれぞれのノードに持たせる。 コード #include <bits/stdc++.h></bits/stdc++.h>…

問題 D: 閉路 - AtCoder Beginner Contest 014 | AtCoder 解法 AtCoder Beginner Contest 014 解説LCA のライブラリを蟻本から写経。 コード #include <bits/stdc++.h> using namespace std; typedef signed long long ll; class LCA { private: LCA() {} vector<vector<int>> G; vector<vector<int></vector<int></vector<int></bits/stdc++.h>…

問題 G: ケンドー - 京都大学プログラミングコンテスト2015 | AtCoder 解法 Bは昇順でソートされているので後ろから見ていき、B[i]より大きいAの中で最も右側にあるものをB[i]と戦わせていけば良い。 i を回して、 Priority Queue に毎回 B[i] 以上のA を入…

解法 n=50, m=100000, k=1000000 なので O(nm log(k)) が間に合う。2分探索 -> 貪欲はよく見る気がする。類題: D: 壊れた電車 - CODE FESTIVAL 2015 予選A | AtCoder コード #include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #includ</set></algorithm></iostream></ctime></cstring></cmath></cstdio>…

問題 abc033.contest.atcoder.jp 解法 ある一点 I を決め、その点を原点として他の点を仰角でソートする。I と他の一点 J を選んだ時に、角 KIJ が鋭角となるような点 K はしゃくとり法によって求められる。発想自体はこれに近い気がする↓ kenkoooo.hatenabl…